【题目描述】

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

【输入】

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

【输出】

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

【输入样例】

1+2*8-9

【输出样例】

8

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define LL long long const int MOD=1000000007; const int N=10000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std;int n,m; stack<int> s1;//操作数栈 stack<char> s2;//运算符栈int lev(char x)//运算符优先级 {if(x=='+'||x=='-')return 1;if(x=='*'||x=='/')return 2;if(x=='^')return 3;return 0; }void calculate(stack<int> &s1,stack<char> &s2)//弹出栈顶元素并计算 {/*取出后弹出栈*/int y=s1.top();s1.pop();int x=s1.top();s1.pop();char z=s2.top();s2.pop();/*根据运算符计算,并压入栈*/if(z=='+')s1.push(x+y);if(z=='-')s1.push(x-y);if(z=='*')s1.push(x*y);if(z=='/')s1.push(x/y);if(z=='^')s1.push(pow(x,y)); }int c(int x) {return x!=0; } char str[1000000]; int sum[1000000];int main(){scanf("%s",str+1);n=strlen(str+1)-1;//忽略掉@的字符串长度for(int i=1;i<=n;i++)//检查匹配{sum[i]+=sum[i-1];if(str[i]=='(')sum[i]++;if(str[i]==')')sum[i]--;}bool out=false;for(int i=2;i<=n;i++)if( c(lev(str[i])) && c(lev(str[i-1])) ){out=1;break;}if( ( n==1 && c(lev(str[1])) )||sum[n]||out )//表达式不合法{cout<<"NO"<<endl;return 0;}stack<int> s1;stack<char> s2;int temp=0;bool flag=false;for(int i=1;i<=n;i++){if('0'<=str[i]&&str[i]<='9')//判断当前字符是否为数字{temp=(temp<<3)+(temp<<1)+str[i]-'0';flag=true;}else{if(flag){s1.push(temp);temp=0;flag=false;}if(str[i]=='('){s2.push(str[i]);continue;}if(str[i]==')'){while(s2.top()!='(')calculate(s1,s2);s2.pop();continue;}while(!s2.empty()&&lev(s2.top())>=lev(str[i]))//优先级判断calculate(s1,s2);s2.push(str[i]);//运算符入栈}}if(flag){s1.push(temp);temp=0;flag=false;}while(!s2.empty())calculate(s1,s2);cout<<s1.top()<<endl;return 0; }

 

总结

以上是生活随笔为你收集整理的中缀表达式值（信息学奥赛一本通-T1358）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。