1358：中缀表达式值(expr)-阿里云开发者社区

1358：中缀表达式值(expr)

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

输入一个中缀表达式（由0-9组成的运算数、加+减-乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。

注意：必须用栈操作，不能直接输出表达式的值。

【输入】

一行为一个以@结束的字符串。

【输出】

如果表达式不合法，请输出“NO”，要求大写。

如果表达式合法，请输出计算结果。

【输入样例】

1+2*8-9@

【输出样例】

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()-1;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. bool judge_(string s)
91. {
92.   string t;
93.   int n=0;
94.   string ops1="+*/";
95.   string ops2="+-*/";
96.   if(ops1.find(s[0])!=string::npos) return false;
97.   if(ops2.find(s[s.size()-2])!=string::npos) return false;
98.   for(int i=0;i<s.size()-1;i++){
99.     if(s[i]=='(') n++;
100.    else if(s[i]==')') n--;
101.    else t+=s[i];
102.  }
103.  if(n) return false;
104.  for(int i=1;i<t.size();i++){
105.    if((ops1.find(t[i])!=string::npos)&&(ops2.find(t[i-1])!=string::npos))
106.      return false;
107.  }
108.  return true;
109. } 
110. int main(int argc, char *argv[])
111. {
112.  string st;
113.  getline(cin,st);//读取字符串 
114.  if(!judge_(st)){ cout<<"NO"<<endl;return 0;}
115.  vector<string> vs=scaner(st);//将字符串解析到vector 
116.  vs=infix_suffix(vs);//中缀表达式转后缀表达式 
117.  cout<<suffix_calc(vs)<<endl;//输出后缀表达式计算结果 
118.  return 0;
119. }

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

1358：中缀表达式值(expr)

热门文章

最新文章

相关电子书