資料結構--棧 codevs 1107 等價表達式

codevs 1107 等價表達式

2005年NOIP全國聯賽提高組

 時間限制: 1 s

 空間限制: 128000 KB

 題目等級 : 鑽石 Diamond

題目描述 Description

明明進了中學之後，學到了代數表達式。有一天，他碰到一個很麻煩的選擇題。這個題目的題幹中首先給出了一個代數表達式，然後列出了若幹選項，每個選項也是一個代數表達式，題目的要求是判斷選項中哪些代數表達式是和題幹中的表達式等價的。

這個題目手算很麻煩，因為明明對計算機程式設計很感興趣，是以他想是不是可以用計算機來解決這個問題。假設你是明明，能完成這個任務嗎？

這個選擇題中的每個表達式都滿足下面的性質：

1．表達式隻可能包含一個變量‘a’。

2．表達式中出現的數都是正整數，而且都小于10000。

3．表達式中可以包括四種運算‘+’（加），‘-’（減），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的優先級最高，其次是‘^’，然後是‘*’，最後是‘+’和‘-’。‘+’和‘-’的優先級是相同的。相同優先級的運算從左到右進行。（注意：運算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字元）

4．幂指數隻可能是1到10之間的正整數（包括1和10）。

5．表達式内部，頭部或者尾部都可能有一些多餘的空格。

下面是一些合理的表達式的例子：

((a^1)^2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1+(a-1)^3，1^10^9……

輸入描述 Input Description

輸入第一行給出的是題幹中的表達式。第二行是一個整數n（2<=n<=26），表示選項的個數。後面n行，每行包括一個選項中的表達式。這n個選項的标号分别是A，B，C，D……

輸入中的表達式的長度都不超過50個字元，而且保證選項中總有表達式和題幹中的表達式是等價的。

輸出描述 Output Description

輸出包括一行，這一行包括一系列選項的标号，表示哪些選項是和題幹中的表達式等價的。選項的标号按照字母順序排列，而且之間沒有空格。

樣例輸入 Sample Input

(a+1)^2

3

(a-1)^2+4*a

a+1+a

a^2+2*a*1+1^2+10-10+a-a

樣例輸出 Sample Output

AC

資料範圍及提示 Data Size & Hint

【資料規模】

對于30%的資料，表達式中隻可能出現兩種運算符‘+’和‘-’；

對于其它的資料，四種運算符‘+’，‘-’，‘*’，‘^’在表達式中都可能出現。

對于全部的資料，表達式中都可能出現小括号‘(’和‘)’。

1 /*
  2 機智的方法：給a代入特殊值。不要代入0，1，-1這樣的數。最好代質數。
  3 隻代入一個數還是很有可能出現兩個不等的式子算出來結果相等。
  4 多代幾個數
  5 還有一個問題，代數的話，計算結果可能會超過long long範圍。
  6 計算的時候記得模一個大質數
  7 因為我們取了若幹個數代進去，是以即使模了一個數沖突的幾率也很小
  8 下面進入正題：如何計算表達式的值？
  9 我們需要開兩個棧：一個用來存儲數字，一個用來存儲符号。
 10 讀入數字時，壓入數字棧
 11 讀入符号時：
 12 1.如果是運算符，目前棧頂的運算符優先級大于等于新運算符，則将棧頂運算符彈出，并将目前數字棧頂的兩個數進行相應運算，彈出舊數，壓入新結果。不停循環，直到棧裡面沒有符号或符号優先級低于目前新運算符。
 13 2.如果是(，直接壓入棧。
 14 3.如果是），則依次将棧裡面的符号彈出，并計算。直到遇到一個（。
 15 
 16 */
 17 #include<cstring>
 18 #include<iostream>
 19 using namespace std;
 20 #include<cstdio>
 21 #define mod 32767
 22 #define max_len 10
 23 #define L 55
 24 char s[L],b[L],n;
 25 int ans[max_len+5];
 26 int sumstack[L],fhstack[L];
 27 int len1=0,len2=0;
 28 int quick_mod(int x,int y)//x^y
 29 {
 30     int ret=1;
 31     while(y)
 32     {
 33         if(y&1)
 34         {
 35             ret*=x;
 36             ret%=mod;
 37         }
 38         y>>=1;x*=x;
 39         x%=mod;
 40     }
 41     return ret;
 42 }
 43 void multi()
 44 {
 45     switch(fhstack[len2])
 46     {
 47         case 1:sumstack[len1-1]+=sumstack[len1];
 48                sumstack[len1-1]%=mod;
 49                break;
 50         case 2:sumstack[len1-1]-=sumstack[len1];
 51                sumstack[len1-1]%=mod;
 52                break;
 53         case 3:sumstack[len1-1]*=sumstack[len1];
 54                sumstack[len1-1]%=mod;
 55                break;
 56         case 4:sumstack[len1-1]=quick_mod(sumstack[len1-1],sumstack[len1]);
 57                sumstack[len1-1]%=mod;
 58                break;
 59         case 5:len2--; return;/*遇到左括号，直接跳過，是符号棧指針--*/
 60     }
 61     len1--;len2--;
 62 }
 63 int js(char s1[],int k)
 64 {
 65     memset(sumstack,0,sizeof(sumstack));
 66     memset(fhstack,0,sizeof(fhstack));
 67     sumstack[1]=0;len1=1;
 68     len2=0;
 69     int len=strlen(s1);
 70     for(int i=0;i<len;++i)
 71     {
 72         if(s1[i]==' ') continue;
 73         if(s1[i]=='a')
 74         {
 75             sumstack[++len1]=k;
 76             continue;
 77         }
 78         if(s1[i]>='0'&&s1[i]<='9')
 79         {
 80             sumstack[++len1]=s1[i]-'0';
 81             while(s1[i+1]>='0'&&s1[i+1]<='9')
 82             {
 83                 sumstack[len1]=sumstack[len1]*10+s1[i+1]-'0';
 84                 sumstack[len1]%=mod;
 85                 i++;
 86             }
 87             continue;
 88         }
 89         switch(s1[i])
 90         {
 91             case '(': fhstack[++len2]=5;break;
 92             case '+':while(len2>0&&fhstack[len2]>0&&fhstack[len2]<5) multi();
 93                      fhstack[++len2]=1;
 94                      break;
 95 /*注意這裡的是while，不是if，就是如果滿足條件的話，就把前面的一直算*/
 96             case '-':while(len2>0&&fhstack[len2]>0&&fhstack[len2]<5) multi();
 97                      fhstack[++len2]=2;
 98                      break;
 99             case '*':while(len2>0&&fhstack[len2]>2&&fhstack[len2]<5) multi();
100                      fhstack[++len2]=3;
101                      break;
102             case '^':while(len2>0&&fhstack[len2]>3&&fhstack[len2]<5) multi();
103                      fhstack[++len2]=4;
104                      break;
105             case ')':while(len2>0&&fhstack[len2]<5) multi();
106                      if(fhstack[len2]==5) len2--;
107                      break;
108         }
109     }
110     while(len2) multi();
111     if(len1==1) return (sumstack[1]+mod)%mod;
112     return (sumstack[2]+mod)%mod;
113 }
114 int main()
115 {
116     gets(s);
117     for(int i=1;i<max_len;++i)
118       ans[i]=js(s,i);
119     scanf("%d\n",&n);
120     for(int i=1;i<=n;++i)
121     {
122         gets(b);
123         bool flag=true;
124         for(int i=1;i<max_len;++i)
125         {
126             int x=js(b,i);
127             if(x!=ans[i])
128             {
129                 flag=false;
130                 break;
131             }
132         }
133         if(flag) 
134           printf("%c",'A'-1+i);
135     }
136     return 0;
137 }