Posts Tagged 栈

TOJ 2919 Alphanumeric Expression

Posted by twcai in ACM/ICPC on September 11, 2008

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

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4. #define MAX 200
  5. int ops[MAX];
  6. int nos[MAX];
  7. char fom[MAX];
  8. int top,tno,ind,len;
  9.  
  10. inline void dfs(int &index)
  11. {
  12.     bool enflag=0;
  13.     bool nflag;
  14.     int ortop,ortno;
  15.     int nop,op;
  16.     int no1,no2;
  17.     int t1;
  18.     ortop=top;ortno=tno;ind++;
  19.     while(!enflag)
  20.     {
  21.         if(fom[index]==')') {nflag=1;enflag=1;ind++;}
  22.         else if(fom[ind]>='0' && fom[ind]<='9')
  23.         {
  24.             t1=fom[ind++]-'0';
  25.             while(fom[ind]>='0' && fom[ind]<='9')
  26.             {
  27.                 t1*=10;
  28.                 t1+=fom[ind++]-'0';
  29.             }
  30.             if(t1>26) t1%=26;
  31.             nos[tno++]=t1;nflag=1;
  32.         }
  33.         else if(fom[ind]>='A' && fom[ind]<='Z')
  34.         {nos[tno++]=fom[ind++]-'A'+1;nflag=1;}
  35.         else if(fom[ind]=='(')
  36.         {dfs(ind);nflag=1;}
  37.         else if(fom[ind]=='+')
  38.         {ops[top++]=0;ind++;nflag=0;}
  39.         else if(fom[ind]=='-')
  40.         {ops[top++]=1;ind++;nflag=0;}
  41.         else if(fom[ind]=='*')
  42.         {ops[top++]=2;ind++;nflag=0;}
  43.         else if(fom[ind]=='/')
  44.         {ops[top++]=3;ind++;nflag=0;}
  45.         else {ind++;continue;}
  46.         while(tno>=ortno+2 && top>=ortop+1)
  47.         {
  48.             if(!nflag) break;
  49.             switch(fom[ind])
  50.             {
  51.             case '+':nop=0;break;
  52.             case '-':nop=1;break;
  53.             case '*':nop=2;break;
  54.             case '/':nop=3;break;
  55.             default:nop=0;break;
  56.             }
  57.             op=ops[top-1];
  58.             if((op/2)>=(nop/2))
  59.             {
  60.                 top--;
  61.                 no2=nos[--tno];
  62.                 no1=nos[--tno];
  63.                 switch(op)
  64.                 {
  65.                 case 0:no1=no1+no2;break;
  66.                 case 1:no1=no1-no2;break;
  67.                 case 2:no1=no1*no2;break;
  68.                 case 3:no1=no1/no2;break;
  69.                 }
  70.                 if(no1>26) no1%=26;
  71.                 nos[tno++]=no1;
  72.             }
  73.             else nflag=0;
  74.         }
  75.     }
  76. }
  77.  
  78. int main()
  79. {
  80.     int nop,op;
  81.     int no1,no2;
  82.     int t1,ret;
  83.     bool nflag;
  84.     while(gets(fom))
  85.     {
  86.         len=strlen(fom);
  87.         ind=0;top=0;tno=0;
  88.         while(ind<=len)
  89.         {
  90.             if(ind==len) {nflag=1;ind++;}
  91.             else if(fom[ind]>='0' && fom[ind]<='9')
  92.             {
  93.                 t1=fom[ind++]-'0';
  94.                 while(fom[ind]>='0' && fom[ind]<='9')
  95.                 {
  96.                     t1*=10;
  97.                     t1+=fom[ind++]-'0';
  98.                 }
  99.                 nos[tno++]=t1;nflag=1;
  100.             }
  101.             else if(fom[ind]>='A' && fom[ind]<='Z')
  102.             {nos[tno++]=fom[ind++]-'A'+1;nflag=1;}
  103.             else if(fom[ind]=='(')
  104.             {dfs(ind);nflag=1;}
  105.             else if(fom[ind]=='+')
  106.             {ops[top++]=0;ind++;nflag=0;}
  107.             else if(fom[ind]=='-')
  108.             {ops[top++]=1;ind++;nflag=0;}
  109.             else if(fom[ind]=='*')
  110.             {ops[top++]=2;ind++;nflag=0;}
  111.             else if(fom[ind]=='/')
  112.             {ops[top++]=3;ind++;nflag=0;}
  113.             else {ind++;continue;}
  114.             while(tno>=2 && top>=1)
  115.             {
  116.                 if(!nflag) break;
  117.                 switch(fom[ind])
  118.                 {
  119.                 case '+':nop=0;break;
  120.                 case '-':nop=1;break;
  121.                 case '*':nop=2;break;
  122.                 case '/':nop=3;break;
  123.                 default:nop=0;break;
  124.                 }
  125.                 op=ops[top-1];
  126.                 if((op/2)>=(nop/2))
  127.                 {
  128.                     top--;
  129.                     no2=nos[--tno];
  130.                     no1=nos[--tno];
  131.                     switch(op)
  132.                     {
  133.                     case 0:no1=no1+no2;break;
  134.                     case 1:no1=no1-no2;break;
  135.                     case 2:no1=no1*no2;break;
  136.                     case 3:no1=no1/no2;break;
  137.                     }
  138.                     if(no1>25) no1%=26;
  139.                     nos[tno++]=no1;
  140.                 }
  141.                 else nflag=0;
  142.             }
  143.         }
  144.         ret=nos[tno-1];
  145.         if(ret>26) ret%=26;
  146.         if(ret==0) ret=26;
  147.         printf("%s",fom);
  148.         printf("=%cn",'A'+ret-1);
  149.     }
  150.     return 0;
  151. }
  152. /*
  153. (A+1)+(A+2)*(D/2)
  154. (A+B*(C+D)-E+9)
  155. */

,

1 Comment