hihoCoder 简单计算器

数据结构的入门题，理解倒是不复杂，用两个栈就行（一个存数字一个存符号）。对于我这样的弱弱没事练练编码能力还是不错的。
注意运算优先级即可。（过两天回科大了，下次再做题也不知道何时，ACM生涯两铜收场orz）
题目链接：
http://hihocoder.com/contest/hihointerview11/problem/3
代码：
  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 typedef long long int64;
  5 
  6 stack<int64> sn;
  7 stack<char> sc;
  8 
  9 const int maxn = 100 + 10;
 10 char str[maxn];
 11 
 12 char op[] = { '+', '-', '*', '/', '(', ')', '#' };
 13 
 14 int getOpId(char op){
 15       if(op == '+')
 16             return -1;
 17       else if(op == '-')
 18             return -2;
 19       else if(op == '*')
 20             return -3;
 21       else if(op == '/')
 22             return -4;
 23       else if(op == '(' )
 24             return -5;
 25       else if(op == ')' )
 26             return -6;
 27       else if(op == '#')
 28             return -7;
 29       else if(op == '&')
 30             return -8;
 31 }
 32 
 33 vector<int64> v;
 34 
 35 int getPrio(char op){
 36       switch(op){
 37             case '+': return 3;
 38             case '-': return 3;
 39             case '*': return 4;
 40             case '/': return 4;
 41             case '(': return 2;
 42             case '&': return 0;
 43             default: return 1;
 44       }
 45 }
 46 
 47 int64 cal(int64 a, int64 b, char opt){
 48       if(opt == '+'){
 49             return a+b;
 50       }else if(opt == '-'){
 51             return a-b;
 52       }else if(opt == '*'){
 53             return a*b;
 54       }else if(opt == '/'){
 55             return a/b;
 56       }
 57 }
 58 
 59 int main(void){
 60       scanf("%s", str);
 61       int len = strlen(str);
 62       str[len++] = '#';
 63 
 64       for(int i = 0; i < len; ++i){
 65             if('0' <= str[i] && str[i] <= '9'){
 66                   int64 t = 0;
 67                   while('0' <= str[i] && str[i] <= '9'){
 68                         t = t * 10 + (str[i] - '0');
 69                         i++;
 70                   }
 71                   i--;
 72                   v.push_back(t);
 73             }else{
 74                   v.push_back(getOpId(str[i]));
 75             }
 76             //cout << v.back() << " ";
 77       }
 78       //cout << endl;
 79 
 80       int sz = v.size();
 81       sc.push('&');
 82       for(int i = 0; i < sz; ++i){
 83             if(v[i] >= 0){
 84                   sn.push(v[i]);
 85                   //cout << "push  " << v[i] << endl;
 86             }else{
 87                   char c = op[-v[i]-1];
 88                   if(c == '('){
 89                         sc.push('(');
 90                         //cout << "push  " << '(' << endl;
 91                   }else if(c == ')'){
 92                         while(sc.top() != '('){
 93                               int64 b = sn.top(); sn.pop();
 94                               int64 a = sn.top(); sn.pop();
 95                               char opt = sc.top(); sc.pop();
 96                               sn.push(cal(a, b, opt));
 97                               //cout << "cal  " << a << " " << opt << " " << b << endl;
 98                         }
 99                         sc.pop();
100                         //cout << "pop  " << '(' << endl;
101                   }else{
102                         int prio1 = getPrio(c);
103                         int prio2;
104 
105                         while(prio1 <= (prio2 = getPrio(sc.top()))){
106                               //cout << "prio1: " << prio1 << "    prio2: " << prio2 << endl;
107                               int64 b = sn.top(); sn.pop();
108                               int64 a = sn.top(); sn.pop();
109                               char opt = sc.top(); sc.pop();
110                               sn.push(cal(a, b, opt));
111                               //cout << "cal  " << a << " " << opt << " " << b << endl;
112                         }
113                         sc.push(c);
114                         //cout << "push  " << c << endl;
115                   }
116             }
117       }
118 
119       //cout << "haha" << endl;
120       printf("%lld
", sn.top());
121 
122       return 0;
123 }
124 
125 /**
126 5*(3+8*2)-(5+6*2-7)*2
127 100*(2+12)-(20/3)*2
128 (8+2*3/4-4)*(3-2+5/2*3)*(3-4+3)/6
129 */
View Code