台湾菜

TOJ 2919 Alphanumeric Expression

twcai • acm/icpc

用栈模拟下,数据结构课上王立波老师讲过思想,就是把一个可以计算的表达式 a (op) b ,拆成操作数和操作符分别入栈,如果表达式中的下一个操作符的优先级比栈顶的操作符高,则继续入栈,否则计算栈顶的两个操作数和操作符,再把结果压入操作数的栈中,碰到括号,我就用dfs来求括号中的子表达式。
第一次写,还是在比赛中写,居然就过了,还是蛮高兴的。由于题目说在中间过程中不会出现负数的情况,因此这个代码并没有对负数的处理。^ ^
#include
#include
using namespace std;
#define MAX 200
int ops[MAX];
int nos[MAX];
char fom[MAX];
int top,tno,ind,len;

inline void dfs(int &index)
{
bool enflag=0;
bool nflag;
int ortop,ortno;
int nop,op;
int no1,no2;
int t1;
ortop=top;ortno=tno;ind++;
while(!enflag)
{
if(fom[index]==')') {nflag=1;enflag=1;ind++;}
else if(fom[ind]>='0' && fom[ind]<='9')
{
t1=fom[ind++]-'0';
while(fom[ind]>='0' && fom[ind]<='9')
{
t1*=10;
t1+=fom[ind++]-'0';
}
if(t1>26) t1%=26;
nos[tno++]=t1;nflag=1;
}
else if(fom[ind]>='A' && fom[ind]<='Z')
{nos[tno++]=fom[ind++]-'A'+1;nflag=1;}
else if(fom[ind]=='(')
{dfs(ind);nflag=1;}
else if(fom[ind]=='+')
{ops[top++]=0;ind++;nflag=0;}
else if(fom[ind]=='-')
{ops[top++]=1;ind++;nflag=0;}
else if(fom[ind]=='*')
{ops[top++]=2;ind++;nflag=0;}
else if(fom[ind]=='/')
{ops[top++]=3;ind++;nflag=0;}
else {ind++;continue;}
while(tno>=ortno+2 && top>=ortop+1)
{
if(!nflag) break;
switch(fom[ind])
{
case '+':nop=0;break;
case '-':nop=1;break;
case '*':nop=2;break;
case '/':nop=3;break;
default:nop=0;break;
}
op=ops[top-1];
if((op/2)>=(nop/2))
{
top--;
no2=nos[--tno];
no1=nos[--tno];
switch(op)
{
case 0:no1=no1+no2;break;
case 1:no1=no1-no2;break;
case 2:no1=no1*no2;break;
case 3:no1=no1/no2;break;
}
if(no1>26) no1%=26;
nos[tno++]=no1;
}
else nflag=0;
}
}
}

int main()
{
int nop,op;
int no1,no2;
int t1,ret;
bool nflag;
while(gets(fom))
{
len=strlen(fom);
ind=0;top=0;tno=0;
while(ind<=len)
{
if(ind==len) {nflag=1;ind++;}
else if(fom[ind]>='0' && fom[ind]<='9')
{
t1=fom[ind++]-'0';
while(fom[ind]>='0' && fom[ind]<='9')
{
t1*=10;
t1+=fom[ind++]-'0';
}
nos[tno++]=t1;nflag=1;
}
else if(fom[ind]>='A' && fom[ind]<='Z')
{nos[tno++]=fom[ind++]-'A'+1;nflag=1;}
else if(fom[ind]=='(')
{dfs(ind);nflag=1;}
else if(fom[ind]=='+')
{ops[top++]=0;ind++;nflag=0;}
else if(fom[ind]=='-')
{ops[top++]=1;ind++;nflag=0;}
else if(fom[ind]=='*')
{ops[top++]=2;ind++;nflag=0;}
else if(fom[ind]=='/')
{ops[top++]=3;ind++;nflag=0;}
else {ind++;continue;}
while(tno>=2 && top>=1)
{
if(!nflag) break;
switch(fom[ind])
{
case '+':nop=0;break;
case '-':nop=1;break;
case '*':nop=2;break;
case '/':nop=3;break;
default:nop=0;break;
}
op=ops[top-1];
if((op/2)>=(nop/2))
{
top--;
no2=nos[--tno];
no1=nos[--tno];
switch(op)
{
case 0:no1=no1+no2;break;
case 1:no1=no1-no2;break;
case 2:no1=no1*no2;break;
case 3:no1=no1/no2;break;
}
if(no1>25) no1%=26;
nos[tno++]=no1;
}
else nflag=0;
}
}
ret=nos[tno-1];
if(ret>26) ret%=26;
if(ret==0) ret=26;
printf("%s",fom);
printf("=%cn",'A'+ret-1);
}
return 0;
}
/*
(A+1)+(A+2)*(D/2)
(A+B*(C+D)-E+9)
*/

comments powered by Disqus