题目1358中缀表达式值(expr)题目描述输入一个中缀表达式由0-9组成的运算数、加减-乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志表达式以“”作为结束符判断表达式是否合法如果不合法请输出“NO”否则请把表达式转换成后缀形式再求出后缀表达式的值并输出。注意必须用栈操作不能直接输出表达式的值。输入一行为一个以结束的字符串。输出如果表达式不合法请输出“NO”要求大写。如果表达式合法请输出计算结果。时空限制1s / 64MB样例输入12*8-9样例输出8代码#includebits/stdc.husingnamespacestd;constintN5010;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];intttc0;for(inti0;is.size();i){if(s[i]()stkc[ttc]s[i];elseif(s[i])){if(ttc0)ttc--;elsereturnfalse;}}if(ttc0)returnfalse;// 处理负号:将-x变为(0-x)for(inti0;is.size();i)if(s[i]-(!i||isop(s[i-1])s[i-1]!))){intji1;while(js.size()isdigit(s[j]))j;string ts.substr(i,j-i);s.replace(i,j-i,(0t));}// 只有(可以作为开头,只有)可以作为结尾if(isop(s.front())s.front()!()returnfalse;if(isop(s.back())s.back()))returnfalse;// 连续两个运算符 )后不为(是合法的, (前不为)是合法的其余均是不合法的for(inti1;is.size();i)if(isop(s[i-1])isop(s[i]))if(!(s[i-1])s[i]!(||s[i-1]!)s[i]())returnfalse;returntrue;}intmain(){cins;s.pop_back();//判断s是否合法if(!isvalid())puts(NO);else{// 将中缀表达式转为后缀表达式s);ffalse;for(inti0;is.size();i){if(s[i]0s[i]9){sumsum*10(s[i]-0);ftrue;}else{if(f){h[k].nsum;sum0;ffalse;}while(!(tt0||pri(stk[tt])pri(s[i])||stk[tt]()){h[k].cstk[tt];tt--;}if(tt0s[i]))tt--;elsestk[tt]s[i];}}for(inti1;ik;i){if(h[i].c){intbstk2[tt2];tt2--;intastk2[tt2];tt2--;switch(h[i].c){case:stk2[tt2]ab;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;}}coutstk2[tt2];}return0;}结果参考https://blog.csdn.net/lq1990717/article/details/123860584
【题解-信息学奥赛一本通】1358：中缀表达式值(expr)
题目1358中缀表达式值(expr)题目描述输入一个中缀表达式由0-9组成的运算数、加减-乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志表达式以“”作为结束符判断表达式是否合法如果不合法请输出“NO”否则请把表达式转换成后缀形式再求出后缀表达式的值并输出。注意必须用栈操作不能直接输出表达式的值。输入一行为一个以结束的字符串。输出如果表达式不合法请输出“NO”要求大写。如果表达式合法请输出计算结果。时空限制1s / 64MB样例输入12*8-9样例输出8代码#includebits/stdc.husingnamespacestd;constintN5010;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];intttc0;for(inti0;is.size();i){if(s[i]()stkc[ttc]s[i];elseif(s[i])){if(ttc0)ttc--;elsereturnfalse;}}if(ttc0)returnfalse;// 处理负号:将-x变为(0-x)for(inti0;is.size();i)if(s[i]-(!i||isop(s[i-1])s[i-1]!))){intji1;while(js.size()isdigit(s[j]))j;string ts.substr(i,j-i);s.replace(i,j-i,(0t));}// 只有(可以作为开头,只有)可以作为结尾if(isop(s.front())s.front()!()returnfalse;if(isop(s.back())s.back()))returnfalse;// 连续两个运算符 )后不为(是合法的, (前不为)是合法的其余均是不合法的for(inti1;is.size();i)if(isop(s[i-1])isop(s[i]))if(!(s[i-1])s[i]!(||s[i-1]!)s[i]())returnfalse;returntrue;}intmain(){cins;s.pop_back();//判断s是否合法if(!isvalid())puts(NO);else{// 将中缀表达式转为后缀表达式s);ffalse;for(inti0;is.size();i){if(s[i]0s[i]9){sumsum*10(s[i]-0);ftrue;}else{if(f){h[k].nsum;sum0;ffalse;}while(!(tt0||pri(stk[tt])pri(s[i])||stk[tt]()){h[k].cstk[tt];tt--;}if(tt0s[i]))tt--;elsestk[tt]s[i];}}for(inti1;ik;i){if(h[i].c){intbstk2[tt2];tt2--;intastk2[tt2];tt2--;switch(h[i].c){case:stk2[tt2]ab;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;}}coutstk2[tt2];}return0;}结果参考https://blog.csdn.net/lq1990717/article/details/123860584
