ACM ICPC Asia Regional 2011 Kuala Lumpur C题

看了逆波兰表达式之后，发现真是强悍的数据结构，栈的应用怎么感觉一辈子也学不完了呢

后缀表达式即逆波兰表达式，就是将所有的运算符按照一定的等级全部都安排到数字的后面去，实现正确的运算法则。

OK，代码要自己好好看，理解了自然就很简单。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<time.h>
  6 using namespace std;
  7 int const N = 200;
  8 int hash[N];
  9 char exp1[N],exp2[N],a1[N],a2[N],stack1[N];
 10 int stack2[N];
 11 int cal(char exp[],char a[],int len,char stack[])
 12 {
 13      int topa=0,tops=0;
 14      for(int i=0;i<len;i++)
 15      {
 16          if((exp[i]<='9'&&exp[i]>='0')||(exp[i]<='Z'&&exp[i]>='A')||(exp[i]<='z'&&exp[i]>='a'))
 17          a[topa++]=exp[i];
 18          else
 19          {
 20            if(exp[i]=='+'||exp[i]=='-')
 21            {
 22               while(tops>0&&stack[tops-1]!='(')
 23                     a[topa++]=stack[--tops];
 24               stack[tops++]=exp[i];
 25            }
 26            else
 27              if(exp[i]=='*')
 28              {
 29                 while(tops>0&&stack[tops-1]!='('&&stack[tops-1]!='+'&&stack[tops-1]!='-')
 30                       a[topa++]=stack[--tops];
 31                 stack[tops++]=exp[i];
 32              }
 33              else
 34                if(exp[i]==')')
 35                {
 36                   while(stack[tops-1]!='(')
 37                         a[topa++]=stack[--tops];
 38                   tops--;
 39                }
 40                else
 41                  if(exp[i]=='(')
 42                     stack[tops++]=exp[i];
 43          }
 44      }
 45      while(tops>0)
 46            a[topa++]=stack[--tops];
 47      return topa;
 48 }
 49 int Count(char a[],int len,int stack[])
 50 {
 51     int tops=0;
 52     for(int i=0;i<len;i++)
 53     {
 54         if(a[i]>='0'&&a[i]<='9')
 55            stack[tops++]=a[i]-'0';
 56         else
 57           if((a[i]>='A'&&a[i]<='Z')||(a[i]>='a'&&a[i]<='z'))
 58              stack[tops++]=hash[a[i]];
 59           else
 60           {
 61              if(a[i]=='*')
 62                 stack[tops-2]=stack[tops-1]*stack[tops-2];
 63              else
 64                if(a[i]=='-')
 65                 stack[tops-2]=stack[tops-2]-stack[tops-1];
 66                else
 67                  if(a[i]=='+')
 68                     stack[tops-2]=stack[tops-2]+stack[tops-1];
 69              tops--;
 70           }
 71     }
 72     return stack[0];
 73 }
 74 int main()
 75 {
 76     srand(time(0));
 77     int T;
 78     cin>>T;
 79     gets(exp1);
 80     while(T--)
 81     {
 82           gets(exp1);
 83           gets(exp2);
 84           int len1=strlen(exp1);
 85           int len2=strlen(exp2);
 86           len1=cal(exp1,a1,len1,stack1);
 87           len2=cal(exp2,a2,len2,stack1);
 88           int f=1;
 89           for(int i=1;i<10;i++)
 90           {
 91               for(int j=1;j<150;j++)
 92                   hash[j]=rand()%3000;
 93               int ans1=Count(a1,len1,stack2);
 94               int ans2=Count(a2,len2,stack2);
 95               if(ans1!=ans2)
 96               {
 97                  f=0;break;
 98               }
 99           }
100           if(f)printf("YES
");
101           else printf("NO
");
102     }
103     return 0;
104 }

View Code