1 template <class T> 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 };
括号匹配:
1 #include <iostream> 2 #include <cstdio> 3 #include <malloc.h> 4 #include <cstring> 5 using namespace std; 6 int arr[128]; 7 char str[10000]; 8 9 template <class T> struct Stack { 10 #define maxn 10000 11 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<char> 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 }
表达式求值：
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <malloc.h> 5 #include <cstring> 6 using namespace std; 7 int arr[128]; 8 template <class T> 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<Node> 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 }