1358：中缀表达式值(expr)
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
输入一个中缀表达式（由0-9组成的运算数、加+减-乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。
注意：必须用栈操作，不能直接输出表达式的值。
【输入】
一行为一个以@结束的字符串。
【输出】
如果表达式不合法，请输出“NO”，要求大写。
如果表达式合法，请输出计算结果。
【输入样例】
1+2*8-9@
【输出样例】
8
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. }
