1356：计算(calc)

1. //注意测试点有 +-*/^()0~9 以外的字符 
2. #include <iostream>
3. #include <cstdio>
4. #include <cstring>
5. #include <string>
6. #include <stack>
7. #include <cmath>
8. #include <cstdlib>
9. #include <vector>
10. using namespace std;
11. int get_fast(string op)//运算符的优先级 
12. {
13.   int ans=-1;
14.   switch(op[0]){
15.     case '+':case '-': ans=1;break;
16.     case '*':case '/': ans=2;break;
17.     case '^': ans=3;break;  
18.   }
19.   return ans;
20. }
21. vector<string> scaner(string s)//将字符串解析到vector 
22. {
23.   vector<string> ans;
24.   string ops="+-*/^()";
25.   string t="";
26.   for(int i=0;i<s.size();i++){
27.     if(s[i]>='0'&&s[i]<='9') t+=s[i];
28.     else if(ops.find(s[i])!=string::npos) {//注意有特殊字符 
29.       if(t.size()>0)ans.push_back(t);
30.       t=s[i];
31.       ans.push_back(t);
32.       t="";
33.     }
34.   }
35.   if(t.size())ans.push_back(t);//将最后一个数字放入vector 
36.   //for(int i=0;i<ans.size();i++)cout<<ans[i];
37.   //cout<<endl; 
38.   return ans;
39. }
40. vector<string> infix_suffix(vector<string> exp)//中缀表达式转后缀表达式 
41. {
42.   vector<string> ans;
43.   stack<string> st;
44.   string ops="+-*/^";
45.   for(int i=0;i<exp.size();i++){
46.     if(exp[i]=="(")//1、"("直接进栈 
47.       st.push(exp[i]);
48.     else if(exp[i]==")"){//2、")"在找到"("之前连续出栈运算符  
49.       while(st.top()!="("){
50.         ans.push_back(st.top());
51.         st.pop();
52.       }
53.       st.pop();//弹出"("  
54.     }
55.     else if(ops.find(exp[i])!=string::npos){//3、确定是运算符 
56.       while(st.size()&&get_fast(exp[i])<=get_fast(st.top())){
57.         ans.push_back(st.top());
58.         st.pop();//如果栈顶的运算符优先级大于等于当前运算符 栈顶的运算符被连续弹出 
59.       }
60.       st.push(exp[i]);//当前运算符进栈 
61.     }
62.     else ans.push_back(exp[i]);//4、数字直接进栈 
63. 
64.   }
65.   while(st.size()) {ans.push_back(st.top());st.pop();}//5、栈内剩余运算符被连续弹出 
66.   //for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl;
67.   return ans;
68. }
69. int suffix_calc(vector<string> exp)//后缀表达式计算结果 
70. {
71.   stack<int> num;
72.   string ops="+-*/^";
73.   for(int i=0;i<exp.size();i++){
74.     if(ops.find(exp[i])!=string::npos){//是运算符，弹出两个数字运算并入栈 
75.       int a=num.top();num.pop();
76.       int b=num.top();num.pop();
77.       if(exp[i]=="+") num.push(b+a);
78.       else if(exp[i]=="-") num.push(b-a);
79.       else if(exp[i]=="*") num.push(b*a);
80.       else if(exp[i]=="/") num.push(b/a);
81.       else if(exp[i]=="^") num.push(pow(b*1.0,a));
82.     }
83.     else {//字符串是数字，转换成整数并入栈 
84.       num.push(atoi(exp[i].c_str()));
85.     }
86.   }
87.   //cout<<num.top()<<endl;
88.   return num.top();
89. }
90. int main(int argc, char *argv[])
91. {
92.   string st;
93.   getline(cin,st);//读取字符串 
94.   vector<string> vs=scaner(st);//将字符串解析到vector 
95.   vs=infix_suffix(vs);//中缀表达式转后缀表达式 
96.   cout<<suffix_calc(vs)<<endl;//输出后缀表达式计算结果 
97.   return 0;
98. }

1. #include <iostream>
2. #include <cmath>
3. #include <cctype>
4. #include <string>
5. #include <vector>
6. #include <stack>
7. #include <cstdio>
8. #include <cstdlib>
9. using namespace std;
10. int get_level(char op)
11. {
12.   int ans=-1;
13.   switch(op){
14.     case '+':case '-': ans=1;break; 
15.     case '*':case '/': ans=2;break;
16.     case '^': ans=3;break;
17.   }
18.   return ans;
19. }
20. int calc_value(int a,int b,char op)
21. {
22.   int ans;
23.   switch(op){
24.     case '+': ans=a+b;break;
25.     case '-': ans=a-b;break;
26.     case '*': ans=a*b;break;
27.     case '/': ans=a/b;break;
28.     case '^': ans=(int)pow(1.0*a,b);break;
29.   }
30.   return ans;
31. }
32. vector<string> scanner(string exp,char end_ch='\0')
33. {
34.   unsigned int i=0;
35.   vector<string> ans;
36.   string num;
37.   string ops="+-*/^()";
38.   while(exp[i]!=end_ch && i<exp.size()){
39.     if(num.size()==0 && exp[i]=='-' && (i==0 || exp[i-1]!=')')) num+="-";
40.     else if(isdigit(exp[i])) num+=exp[i];
41.     else if(ops.find(exp[i])!=string::npos){
42.       if(num.size()){
43.         ans.push_back(num);num="";
44.       }
45.       ans.push_back(string(1,exp[i]));
46.     }
47.     i++;
48.   }
49.   if(num.size()) ans.push_back(num);
50.   return ans;
51. }
52. vector<string> infix_to_suffix(const vector<string> &exp)
53. {
54.   stack<string> stk;
55.   vector<string> ans;
56.   string ops="+-*/^()";
57.   for(unsigned int i=0;i<exp.size();i++){
58.     if(exp[i]=="(") stk.push(exp[i]);
59.     else if(exp[i]==")"){
60.       while(stk.size()&&stk.top()!="("){
61.         ans.push_back(stk.top());stk.pop();
62.       }
63.       stk.pop();
64.     }
65.     else{
66.       if(exp[i].size()==1 && ops.find(exp[i])!=string::npos){
67.         while(stk.size() && get_level(stk.top()[0])>=get_level(exp[i][0])){
68.           ans.push_back(stk.top());stk.pop();
69.         }
70.         stk.push(exp[i]);
71.       }
72.       else ans.push_back(exp[i]);
73.     }
74.   } 
75.   while(stk.size()){
76.     ans.push_back(stk.top());stk.pop(); 
77.   }
78.   return ans;
79. }
80. int calc_suffix(const vector<string> &exp)
81. {
82.   int ans,a,b;
83.   stack<int> stk;
84.   string ops="+-*/^()";
85.   for(unsigned int i=0;i<exp.size();i++){
86.     if(exp[i].size()==1 && ops.find(exp[i])!=string::npos){
87.       b=stk.top();stk.pop();
88.       a=stk.top();stk.pop();
89.       ans=calc_value(a,b,exp[i][0]);
90.       stk.push(ans);
91.     }
92.     else stk.push(atoi(exp[i].c_str()));
93.   }
94.   return stk.top();
95. }
96. int main(int argc, char *argv[])
97. {
98.   vector<string> vs,ans;
99.   string exp;
100.  int ret;
101.  cin>>exp;
102.  vs=scanner(exp);
103.  ans=infix_to_suffix(vs);
104.  ret=calc_suffix(ans);
105.  cout<<ret<<endl;  
106.  return 0;
107. }