[栈]-白红宇

[栈]

阅读量：5167 次

发布时间：2019-06-13

本文共 7530 字，大约阅读时间需要 25 分钟。

1 template 
      
        struct Stack { 2         #define maxn 10000 3         int p; 4         T stk[maxn]; 5         Stack() { 6                 p = 0; 7                 memset(stk, 0, sizeof(stk)); 8         } 9         void push(T x) {10                 if(p == maxn) puts("stack has been full!");11                 else stk[p++] = x;12         }13         void pop() {14                 if(p == 0) puts("stack is empty!");15                 else p--;16         }17         bool empty() {18                 return p == 0;19         }20         T top() {21                 return stk[p - 1];22         }23         int size() {24                 return p;25         }26 };

View Code

括号匹配:

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 int arr[128]; 7 char str[10000]; 8  9 template 
          
            struct Stack {10         #define maxn 1000011         int p;12         T stk[maxn];13         Stack() {14                 p = 0;15                 memset(stk, 0, sizeof(stk));16         }17         void push(T x) {18                 if(p == maxn) puts("stack has been full!");19                 else stk[p++] = x;20         }21         void pop() {22                 if(p == 0) puts("stack is empty!");23                 else p--;24         }25         bool empty() {26                 return p == 0;27         }28         T top() {29                 return stk[p - 1];30         }31         int size() {32                 return p;33         }34         void clear() {35                 p = 0;36         }37 };38 Stack
           
             stk;39 bool isCorrect(char str[])40 {41 for(int i = 0; str[i]; i++) {42 int val = arr[str[i]];43 if(val) {44 if(val > 0) {45 if(stk.empty()) return false;46 if(arr[stk.top()] + val == 0) stk.pop();47 else return false;48 }49 else stk.push(str[i]);50 }51 }52 if(!stk.empty()) return false;53 return true;54 }55 void init()56 {57 arr['('] = -1;58 arr['['] = -2;59 arr['{ '] = -3;60 arr[')'] = 1;61 arr[']'] = 2;62 arr['}'] = 3;63 }64 65 int main()66 {67 init();68 while(1) {69 printf("input:");70 gets(str);71 if(strlen(str) == 1 && str[0] == '#') break;72 stk.clear();73 if(isCorrect(str)) puts("correct!");74 else puts("error!");75 }76 return 0;77 }

View Code

表达式求值：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 using namespace std;  7 int arr[128];  8 template 
           
             struct Stack { 9 #define maxn 10000 10 int p; 11 T stk[maxn]; 12 Stack() { 13 p = 0; 14 memset(stk, 0, sizeof(stk)); 15 } 16 T & operator [] (int t) { 17 return stk[t]; 18 } 19 void push(T x) { 20 if(p == maxn) puts("stack has been full!"); 21 else stk[p++] = x; 22 } 23 void pop() { 24 if(p == 0) puts("stack is empty!"); 25 else p--; 26 } 27 bool empty() { 28 return p == 0; 29 } 30 T top() { 31 return stk[p - 1]; 32 } 33 int size() { 34 return p; 35 } 36 void clear() { 37 p = 0; 38 } 39 }; 40 struct Node { 41 int type; 42 int int_val; 43 double double_val; 44 char op; 45 46 double f0() { 47 if(type == 1) return (double)int_val; 48 else return double_val; 49 } 50 bool operator != (double x) { 51 return fabs(this->f0() - x) > 0.0000001; 52 } 53 Node operator + (Node b) { 54 Node res; 55 if(type == 2 || b.type == 2) { 56 res.type = 2; 57 res.double_val = this->f0() + b.f0(); 58 } 59 else { 60 res.type = 1; 61 res.int_val = int_val + b.int_val; 62 } 63 return res; 64 } 65 Node operator - (Node b) { 66 Node res; 67 if(type == 2 || b.type == 2) { 68 res.type = 2; 69 res.double_val = this->f0() - b.f0(); 70 } 71 else { 72 res.type = 1; 73 res.int_val = int_val - b.int_val; 74 } 75 return res; 76 } 77 Node operator * (Node b) { 78 Node res; 79 if(type == 2 || b.type == 2) { 80 res.type = 2; 81 res.double_val = this->f0() * b.f0(); 82 } 83 else { 84 res.type = 1; 85 res.int_val = int_val * b.int_val; 86 } 87 return res; 88 } 89 Node operator / (Node b) { 90 Node res; 91 res.type = 2; 92 res.double_val = this->f0() / b.f0(); 93 return res; 94 } 95 bool num() { 96 return type == 1 || type == 2; 97 } 98 bool ch_one() { 99 return type == 3;100 }101 bool ch_two() {102 return type == 4;103 }104 bool LB() {105 return type == 5;106 }107 bool RB() {108 return type == 6;109 }110 void outp() {111 if(type == 1) cout<< int_val;112 if(type == 2) cout<< double_val;113 if(type >= 3) putchar(op);114 }115 };116 Stack
            
              infix, sufix, tmp_stack, ans;117 char str[10000], tmp[10000];118 void getInfix()119 {120 infix.clear();121 int p = 0;122 for(int i = 0; str[i]; i++) {123 if(str[i] != ' ') tmp[p++] = str[i];124 }125 tmp[p] = 0;126 strcpy(str, tmp);127 for(int i = 0; str[i]; ) {128 if(arr[str[i]] >= 1 && arr[str[i]] <= 4) {129 Node tmp;130 tmp.type = 2 + arr[str[i]];131 tmp.op = str[i];132 infix.push(tmp);133 i++;134 }135 if(arr[str[i]] == -1) {136 int db = -1, tmp = i;137 while(arr[str[i]] == - 1) {138 if(str[i] == '.') db = i;139 i++;140 }141 if(~db) {142 double ans = 0;143 int INT = 0;144 for(int j = i - 1; j > db; j--) {145 ans = (ans + str[j] - '0') / 10;146 }147 for(int j = tmp; j < db; j++) {148 INT = INT * 10 + str[j] - '0';149 }150 ans += INT;151 Node temp;152 temp.type = 2;153 temp.double_val = ans;154 infix.push(temp);155 }156 else {157 int INT = 0;158 for(int j = tmp; j < i; j++) {159 INT = INT * 10 + str[j] - '0';160 }161 Node temp;162 temp.type = 1;163 temp.int_val = INT;164 infix.push(temp);165 }166 }167 }168 }169 170 void toSufix()171 {172 sufix.clear();173 for(int i = 0; i < infix.size(); i++) {174 Node val = infix[i];175 if(val.num()) sufix.push(val);176 if(val.ch_one()) {177 while(!tmp_stack.empty() && !tmp_stack.top().LB()) {178 sufix.push(tmp_stack.top());179 tmp_stack.pop();180 }181 tmp_stack.push(val);182 }183 if(val.ch_two()) {184 while(tmp_stack.top().ch_two()) {185 sufix.push(tmp_stack.top());186 tmp_stack.pop();187 }188 tmp_stack.push(val);189 }190 if(val.LB()) {191 tmp_stack.push(val);192 }193 if(val.RB()) {194 while(!tmp_stack.top().LB()) {195 sufix.push(tmp_stack.top());196 tmp_stack.pop();197 }198 tmp_stack.pop();199 }200 }201 while(!tmp_stack.empty()) {202 sufix.push(tmp_stack.top());203 tmp_stack.pop();204 }205 printf("该中缀表达式转换成的后缀表达式为：");206 for(int i = 0; i < sufix.size(); i++) {207 sufix[i].outp();208 cout<< " ";209 }210 cout<< endl;211 }212 Node calc(Node a, Node b, Node op)213 {214 if(op.op == '+') return a + b;215 if(op.op == '-') return a - b;216 if(op.op == '*') return a * b;217 if(op.op == '/') {218 if(b != 0)return a / b;219 puts("div by 0!");220 Node tmp;221 tmp.type = 1;222 tmp.int_val = 0;223 return tmp;224 }225 }226 void getRes()227 {228 ans.clear();229 for(int i = 0; i < sufix.size(); i++) {230 if(!sufix[i].num()) {231 Node b = ans.top();232 ans.pop();233 Node a = ans.top();234 ans.pop();235 ans.push(calc(a, b, sufix[i]));236 }237 else ans.push(sufix[i]);238 }239 printf("该表达式的结果为：");240 ans.top().outp();241 cout<< endl;242 }243 void init()244 {245 arr['.'] = -1;246 arr['+'] = arr['-'] = 1;247 arr['*'] = arr['/'] = 2;248 arr['('] = 3;249 arr[')'] = 4;250 for(char i = '0'; i <= '9'; i++) arr[i] = -1;251 }252 int main()253 {254 init();255 while(1) {256 puts("请输入一个表达式：");257 gets(str);258 if(strlen(str) == 0) continue;259 getInfix();260 toSufix();261 getRes();262 puts("是否继续？(y/n)");263 char ch = getchar();264 if(ch == 'n') break;265 ch = getchar();266 }267 return 0;268 }