3606 - 中缀表达式求值
时间限制 : 1 秒
内存限制 : 128 MB
输入一表达式，将其求值后输出。
题目输入
输入一表达式，最后以输入@结束
题目输出
输出一个数表示该表达式的值
输入/输出样例
输入格式
3*(2+5)@
输出格式
21
C语言解答
#include<stdio.h> #include<math.h> #define maxn 101 int push1(int n,double *p,double v) { n++; p[n]=v; return n; } double pop1(int n,double *p) { return p[n]; } int push2(int n,char *p,char v) { n++; p[n]=v; return n; } int main() { char str[maxn],stackope[maxn],op; int nn=0,np=0,i; double stacknum[maxn],sec,fir; scanf("%s",str); for(i=0;str[i]!='@';i++) { if(str[i]>='0'&&str[i]<='9') nn=push1(nn,stacknum,(str[i]-'0')*1.00); else { if(np==0) np=push2(np,stackope,str[i]); else if(str[i]=='(') np=push2(np,stackope,str[i]); else if(str[i]==stackope[np]) { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; if(str[i]=='+') { nn=push1(nn,stacknum,fir+sec);} if(str[i]=='-') { nn=push1(nn,stacknum,fir-sec);} if(str[i]=='*') { nn=push1(nn,stacknum,fir*sec);} if(str[i]=='/') { nn=push1(nn,stacknum,fir/sec);} } else if(str[i]=='+') { if(stackope[np]=='*') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,fir*sec);np--; np=push2(np,stackope,str[i]); } else if(stackope[np]=='/') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,fir/sec);np--; np=push2(np,stackope,str[i]); } else if(stackope[np]=='-') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,fir-sec);np--; np=push2(np,stackope,str[i]); } else np=push2(np,stackope,str[i]); } else if(str[i]=='-') { if(stackope[np]=='*') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,fir*sec);np--; np=push2(np,stackope,str[i]); } else if(stackope[np]=='/') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,fir/sec);np--; np=push2(np,stackope,str[i]); } else if(stackope[np]=='+') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,fir+sec);np--; np=push2(np,stackope,str[i]); } else np=push2(np,stackope,str[i]); } else if(str[i]=='*'||str[i]=='/') { if(stackope[np]=='*') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,fir*sec);np--; np=push2(np,stackope,str[i]); } else if(stackope[np]=='/') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,fir/sec);np--; np=push2(np,stackope,str[i]); } else np=push2(np,stackope,str[i]); } else if(str[i]=='^') { sec=pop1(nn,stacknum);nn--; nn=push1(nn,stacknum,pow(sec,(str[i+1]-'0'))); i=i+1; continue; } else { while(stackope[np]!='(') { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; op=stackope[np]; if(op=='+') nn=push1(nn,stacknum,fir+sec); if(op=='-') nn=push1(nn,stacknum,fir-sec); if(op=='*') nn=push1(nn,stacknum,fir*sec); if(op=='/') nn=push1(nn,stacknum,fir/sec); np--; } np--; } } } while(np!=0) { sec=pop1(nn,stacknum);nn--; fir=pop1(nn,stacknum);nn--; op=stackope[np]; if(op=='+') nn=push1(nn,stacknum,fir+sec); if(op=='-') nn=push1(nn,stacknum,fir-sec); if(op=='*') nn=push1(nn,stacknum,fir*sec); if(op=='/') nn=push1(nn,stacknum,fir/sec); np--; } printf("%d",(int)stacknum[nn]); return 0; }
C++解答
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<string> using namespace std; int a[101],i=0,p=1; char sy[101],t[256]; string s; void push() { sy[++p]=s[i]; } void pop() { switch(sy[p--]) { case '+': a[p]+=a[p+1]; break; case '-': a[p]-=a[p+1]; break; case '*': a[p]*=a[p+1]; break; case '/': a[p]/=a[p+1]; break; } } bool can() { if((s[i]=='+'||s[i]=='-')&&sy[p]!='(') return 1; if((s[i]=='*'||s[i]=='/')&&(sy[p]=='*'||sy[p]=='/')) return 1; return 0; } int main() { cin>>s; s[s.length()-1]=')'; sy[p]='('; while(i<s.length()) { while(s[i]=='(') { push(); i++; } int x=0; while(s[i]>='0'&&s[i]<='9') x=x*10+s[i++]-'0'; a[p]=x; do { if(s[i]==')') { while(sy[p]!='(') pop(); a[--p]=a[p+1]; } else { while(can()) pop(); push(); } i++; }while(i<s.length()&&s[i-1]==')'); } cout<<a[0]; return 0; }