codevs 1107 等價表達式
2005年NOIP全國聯賽提高組
明明進了中學之后，學到了代數表達式。有一天，他碰到一個很麻煩的選擇題。這個題目的題干中首先給出了一個代數表達式，然后列出了若干選項，每個選項也是一個代數表達式，題目的要求是判斷選項中哪些代數表達式是和題干中的表達式等價的。
這個題目手算很麻煩，因為明明對計算機編程很感興趣，所以他想是不是可以用計算機來解決這個問題。假設你是明明，能完成這個任務嗎？
這個選擇題中的每個表達式都滿足下面的性質：
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……
輸入第一行給出的是題干中的表達式。第二行是一個整數n（2<=n<=26），表示選項的個數。后面n行，每行包括一個選項中的表達式。這n個選項的標號分別是A，B，C，D……
輸入中的表達式的長度都不超過50個字符，而且保證選項中總有表達式和題干中的表達式是等價的。
輸出包括一行，這一行包括一系列選項的標號，表示哪些選項是和題干中的表達式等價的。選項的標號按照字母順序排列，而且之間沒有空格。
(a+1)^2
3
(a-1)^2+4*a
a+1+a
a^2+2*a*1+1^2+10-10+a-a
AC
【數據規模】
對于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 }
?
![[Ajax]ajax學習與理解](http://pic.xiahunao.cn/[Ajax]ajax學習與理解)
)
