【题解-信息学奥赛一本通】1358：中缀表达式值(expr)
题目：1358：中缀表达式值(expr)
题目描述
输入一个中缀表达式（由0-9组成的运算数、加+减-乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。
注意：必须用栈操作，不能直接输出表达式的值。
输入
一行为一个以@结束的字符串。
输出
如果表达式不合法，请输出“NO”，要求大写。
如果表达式合法，请输出计算结果。
时空限制
1s / 64MB
样例输入
1+2*8-9@样例输出
8代码
#include<bits/stdc++.h>usingnamespacestd;constintN=50+10;string s;structnode{intn;charc;}h[N];intsum;intk;inttt;charstk[N];boolf;intstk2[N],tt2;intpri(charx){switch(x){case'(':return4;case'*':return3;case'/':return3;case'+':return2;case'-':return2;case')':return1;}}boolisop(charc){if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')')returntrue;returnfalse;}boolisvalid(){// 括号匹配charstkc[N];intttc=0;for(inti=0;i<s.size();i++){if(s[i]=='(')stkc[++ttc]=s[i];elseif(s[i]==')'){if(ttc>0)ttc--;elsereturnfalse;}}if(ttc>0)returnfalse;// 处理负号:将-x变为(0-x)for(inti=0;i<s.size();i++)if(s[i]=='-'&&(!i||isop(s[i-1])&&s[i-1]!=')')){intj=i+1;while(j<s.size()&&isdigit(s[j]))j++;string t=s.substr(i,j-i);s.replace(i,j-i,"(0"+t+")");}// 只有(可以作为开头,只有)可以作为结尾if(isop(s.front())&&s.front()!='(')returnfalse;if(isop(s.back())&&s.back()==')')returnfalse;// 连续两个运算符 )后不为(是合法的, (前不为)是合法的，其余均是不合法的for(inti=1;i<s.size();i++)if(isop(s[i-1])&&isop(s[i]))if(!(s[i-1]==')'&&s[i]!='('||s[i-1]!=')'&&s[i]=='('))returnfalse;returntrue;}intmain(){cin>>s;s.pop_back();//判断s是否合法if(!isvalid())puts("NO");else{// 将中缀表达式转为后缀表达式s+=')';f=false;for(inti=0;i<s.size();i++){if(s[i]>='0'&&s[i]<='9'){sum=sum*10+(s[i]-'0');f=true;}else{if(f){h[++k].n=sum;sum=0;f=false;}while(!(tt<=0||pri(stk[tt])<pri(s[i])||stk[tt]=='(')){h[++k].c=stk[tt];tt--;}if(tt>0&&s[i]==')')tt--;elsestk[++tt]=s[i];}}for(inti=1;i<=k;i++){if(h[i].c){intb=stk2[tt2];tt2--;inta=stk2[tt2];tt2--;switch(h[i].c){case'+':stk2[++tt2]=a+b;break;case'-':stk2[++tt2]=a-b;break;case'*':stk2[++tt2]=a*b;break;case'/':stk2[++tt2]=a/b;break;}}else{stk2[++tt2]=h[i].n;}}cout<<stk2[tt2];}return0;}结果
参考
https://blog.csdn.net/lq1990717/article/details/123860584