codevs 1107 等價(jià)表達(dá)式

2005年NOIP全國聯(lián)賽提高組

?時(shí)間限制: 1 s ?空間限制: 128000 KB ?題目等級(jí) : 鉆石 Diamond 題目描述?Description

明明進(jìn)了中學(xué)之后，學(xué)到了代數(shù)表達(dá)式。有一天，他碰到一個(gè)很麻煩的選擇題。這個(gè)題目的題干中首先給出了一個(gè)代數(shù)表達(dá)式，然后列出了若干選項(xiàng)，每個(gè)選項(xiàng)也是一個(gè)代數(shù)表達(dá)式，題目的要求是判斷選項(xiàng)中哪些代數(shù)表達(dá)式是和題干中的表達(dá)式等價(jià)的。

這個(gè)題目手算很麻煩，因?yàn)槊髅鲗?duì)計(jì)算機(jī)編程很感興趣，所以他想是不是可以用計(jì)算機(jī)來解決這個(gè)問題。假設(shè)你是明明，能完成這個(gè)任務(wù)嗎？

這個(gè)選擇題中的每個(gè)表達(dá)式都滿足下面的性質(zhì)：
1．表達(dá)式只可能包含一個(gè)變量‘a(chǎn)’。
2．表達(dá)式中出現(xiàn)的數(shù)都是正整數(shù)，而且都小于10000。
3．表達(dá)式中可以包括四種運(yùn)算‘+’（加），‘-’（減），‘*’（乘），‘^’（乘冪），以及小括號(hào)‘(’，‘)’。小括號(hào)的優(yōu)先級(jí)最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的優(yōu)先級(jí)是相同的。相同優(yōu)先級(jí)的運(yùn)算從左到右進(jìn)行。（注意：運(yùn)算符‘+’，‘-’，‘*’，‘^’以及小括號(hào)‘(’，‘)’都是英文字符）
4．冪指數(shù)只可能是1到10之間的正整數(shù)（包括1和10）。
5．表達(dá)式內(nèi)部，頭部或者尾部都可能有一些多余的空格。
下面是一些合理的表達(dá)式的例子：
((a^1)^2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1+(a-1)^3，1^10^9……

輸入描述?Input Description

輸入第一行給出的是題干中的表達(dá)式。第二行是一個(gè)整數(shù)n（2<=n<=26），表示選項(xiàng)的個(gè)數(shù)。后面n行，每行包括一個(gè)選項(xiàng)中的表達(dá)式。這n個(gè)選項(xiàng)的標(biāo)號(hào)分別是A，B，C，D……

輸入中的表達(dá)式的長度都不超過50個(gè)字符，而且保證選項(xiàng)中總有表達(dá)式和題干中的表達(dá)式是等價(jià)的。

輸出描述?Output Description

輸出包括一行，這一行包括一系列選項(xiàng)的標(biāo)號(hào)，表示哪些選項(xiàng)是和題干中的表達(dá)式等價(jià)的。選項(xiàng)的標(biāo)號(hào)按照字母順序排列，而且之間沒有空格。

樣例輸入?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

數(shù)據(jù)范圍及提示?Data Size & Hint

【數(shù)據(jù)規(guī)模】
對(duì)于30%的數(shù)據(jù)，表達(dá)式中只可能出現(xiàn)兩種運(yùn)算符‘+’和‘-’；
對(duì)于其它的數(shù)據(jù)，四種運(yùn)算符‘+’，‘-’，‘*’，‘^’在表達(dá)式中都可能出現(xiàn)。
對(duì)于全部的數(shù)據(jù)，表達(dá)式中都可能出現(xiàn)小括號(hào)‘(’和‘)’。

1 /* 2 機(jī)智的方法：給a代入特殊值。不要代入0，1，-1這樣的數(shù)。最好代質(zhì)數(shù)。 3 只代入一個(gè)數(shù)還是很有可能出現(xiàn)兩個(gè)不等的式子算出來結(jié)果相等。 4 多代幾個(gè)數(shù) 5 還有一個(gè)問題，代數(shù)的話，計(jì)算結(jié)果可能會(huì)超過long long范圍。 6 計(jì)算的時(shí)候記得模一個(gè)大質(zhì)數(shù) 7 因?yàn)槲覀內(nèi)×巳舾蓚€(gè)數(shù)代進(jìn)去，所以即使模了一個(gè)數(shù)沖突的幾率也很小 8 下面進(jìn)入正題：如何計(jì)算表達(dá)式的值？ 9 我們需要開兩個(gè)棧：一個(gè)用來存儲(chǔ)數(shù)字，一個(gè)用來存儲(chǔ)符號(hào)。 10 讀入數(shù)字時(shí)，壓入數(shù)字棧 11 讀入符號(hào)時(shí)： 12 1.如果是運(yùn)算符，當(dāng)前棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)大于等于新運(yùn)算符，則將棧頂運(yùn)算符彈出，并將當(dāng)前數(shù)字棧頂?shù)膬蓚€(gè)數(shù)進(jìn)行相應(yīng)運(yùn)算，彈出舊數(shù)，壓入新結(jié)果。不停循環(huán)，直到棧里面沒有符號(hào)或符號(hào)優(yōu)先級(jí)低于當(dāng)前新運(yùn)算符。 13 2.如果是(，直接壓入棧。 14 3.如果是），則依次將棧里面的符號(hào)彈出，并計(jì)算。直到遇到一個(gè)（。 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;/*遇到左括號(hào)，直接跳過，是符號(hào)棧指針--*/ 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/c1299401227/p/5767231.html

總結(jié)

以上是生活随笔為你收集整理的数据结构--栈 codevs 1107 等价表达式的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。