POJ 2106-Boolean Expressions，雙棧運用類似表達式求值！

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Boolean Expressions

? ?首先聲明此題后臺可能極水（畢竟這種數據不好造！）。昨天寫了一天卻總是找不到bug，討論區各種數據都過了，甚至懷疑輸入有問題，但看到gets也可以過，難道是思路錯了？

? ? 題意：V表示ture，F表示false，然后有三種位運算符‘！’、‘&’、'|'。其中'!'的優先級最高，‘|’的優先級最低。即優先級關系：！ > & > | 。給你一串包含這些運算符的表達式當然了還有括號，要你判斷最終結果是VorF。

? ? 先說說我的思路吧：符號棧和數值棧肯定是前提（數組模擬也無所謂）。由于‘！’和‘&’的運算等級較高，于是我們可以先把所有的‘！’和‘&’先進行運算，最后運算或（掃一遍無先后）。當然了，括號的優先級最最高，我們特判括號的情況。你可能要問‘！’和’&‘的優先級有大小，怎么判斷先后呢，我們發現’！‘一般是在一個數值前面，當存入一個數值的時候可以直接運算，’&‘在兩個數值之間，也是直接取數值棧頂的兩個元素直接運算再入棧。就是因為’！‘只能在一個數值前或者括號前（括號內最終也會化為一個數值），所以如果’！‘和’&‘都出現了肯定會將’！‘先運算完再’&‘運算，本來也符合題意優先級之分。但為什么會wa這么多遍呢，next....

? ? 現在來說說括號怎么判，我們如果是出現'('的話直接先入符號棧，然后數值和符號也是直接入相應的棧再判斷運算。但當’）‘出現意味著肯定有一個最近的’（‘與其配對，我們這時就要把括號里的先運算完對吧，但上述提到’！‘和’&‘都是一出現就直接運算了，所以這時的括號內只能是單個數值或很多’|‘，還是直接運算，到’（‘就截止了嘛。最后彈出’（‘。好像看起來沒毛病，又是WA。原因為何？next.....

? ? 最后看其他人提交的代碼結果發現他們根本沒有判優先級，三種符號出現都是從左往右掃，這樣也過？’！‘的情況肯定沒問題，但’&‘和’|‘總得有個先后，一學弟給出一幅圖畫出單個’&‘和單個’|‘的所有情況讓我猜想這樣依次運算是否和先后運算的結果一樣？草草的證明了一下貌似真的可以（急功近利），然后仿照這大家的思路做了做終于發現自己的問題出在哪了，原來在進行’！‘和’&‘運算的時候沒有判斷到’（‘應截止。還有在’（‘應當出棧的時候沒有判斷棧頂元素是否為’（‘。也是神奇，我的正確思路居然被這種樣例hackde。這時仍接受著依次運算和先后運算的結果一樣的觀點，回到宿舍學姐再討論群里提出這樣一組數據：1|0&0 即 V|F&F。這樣明顯打破上述觀點，然后用兩種代碼都試了試果然依次運算的結果是F,正解應該是V。不得不說自己沒有仔細證明為了A題草草下定結論，不過所幸自己的代碼是沒有問題的。可能大家讀題題意沒有明確，卻陰差陽錯，集訓隊的讀題能力貌似一直處于迷離狀態。。。。

? ? 重（ji）點（tang）：研究性學習真的是讓人很興奮，充分鍛煉一個人的耐心與思維，在結論成果得出的那一刻仿佛即將升天般的快感，這種學習方式也值得我們利用，當前學習狀態不禁讓我想起了快餐文化這一概念，急功近利總不得有好的結果，沉心靜氣淡泊名利才能走的更遠。不惜花了這么大的篇幅來引出這段話，就算個人體驗了，不喜勿噴。

? ? 回到原題，下面給出三種代碼：

?思路1：WA。未正確判斷好括號關系。

const int N=1e6+10;
stack<char>q1;
stack<int>q2;
char s[150];
void ch(char c)
{if(c=='!'){int x1=q2.top();q2.pop();x1=!x1;q2.push(x1);}else if(c=='&'){int x1=q2.top();q2.pop();int x2=q2.top();q2.pop(); q2.push(x1&x2);}else if(c=='|'){int x1=q2.top();  q2.pop();int x2=q2.top();  q2.pop();q2.push(x1|x2);}q1.pop();
}
int main()
{int t=1;char c;while(1){c=getchar();if(c==' ') continue;if(c=='\n'||c==EOF){while(!q1.empty()){if(q1.top()!='(') ch(q1.top());else q1.pop();}printf("Expression %d: ",t++);if(q2.top()==1) puts("V");else puts("F");while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();if(c==EOF) break;else continue;}if(c==')'){while(!q1.empty()&&q1.top()!='(') ch(q1.top());q1.pop();//本意是刪去‘（’,但應該判斷是否為空且棧頂是否為‘（’}else{if(c!='V'&&c!='F') q1.push(c);else{if(c=='V') q2.push(1);else q2.push(0);while(!q1.empty())//應該判斷‘（’截止{if(q1.top()!='!'&&q1.top()!='&') break;//‘!’和'&'優先ch(q1.top());}}}}return 0;
}

? 代碼二：AC。

const int N=1e6+10;
stack<char>q1;
stack<int>q2;
char s[N];
void ch(char c)
{if(c=='!'){int x=q2.top();q2.pop();q2.push(!x);}else if(c=='&'){int x1=q2.top();q2.pop();int x2=q2.top();q2.pop();q2.push(x1&x2);}else if(c=='|'){int x1=q2.top();q2.pop();int x2=q2.top();q2.pop();q2.push(x1|x2);}q1.pop();
}
int main()
{int t=1;while(gets(s)){while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();int len=strlen(s);for(int i=0; i<len; i++){if(s[i]==' ') continue;if(s[i]==')'){while(!q1.empty()&&q1.top()!='(')  ch(q1.top());if(!q1.empty()&&q1.top()=='(') q1.pop();//刪去左括號}else{if(s[i]!='F'&&s[i]!='V') q1.push(s[i]);else{if(s[i]=='F') q2.push(0);else q2.push(1);while(!q1.empty()&&q1.top()!='('){if(q1.top()!='&'&&q1.top()!='!') break;ch(q1.top());}if(!q1.empty()&&q1.top()=='(') q1.pop();}}}printf("Expression %d: ",t++);while(!q1.empty()) ch(q1.top());if(q2.top()==1) puts("V");else puts("F");}return 0;
}

? 代碼三：hacked ? V|F&F

const int N=1e3+10;
stack<char>q1;
stack<int>q2;
char s[N];
void deal(char tmp)
{if(tmp==')') q1.pop();else{if(tmp=='V') q2.push(1);else q2.push(0);}while(!q1.empty()&&q1.top()!='('){char c=q1.top();q1.pop();if(c=='!'&&!q2.empty()){int x=q2.top();q2.pop();q2.push(!x);}else if(c=='&'&&q2.size()>1){int x1=q2.top();q2.pop();int x2=q2.top();q2.pop();q2.push(x1&x2);}else if(c=='|'&&q2.size()>1){int x1=q2.top();q2.pop();int x2=q2.top();q2.pop();q2.push(x1|x2);}}
}
int main()
{int t=1;while(gets(s)){while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();int len=strlen(s);for(int i=0; i<len; i++){if(s[i]==' ') continue;if(s[i]=='F'||s[i]=='V'||s[i]==')') deal(s[i]);else q1.push(s[i]);}printf("Expression %d: ",t++);if(!q1.empty()) deal(q1.top());if(q2.top()==1) puts("V");else puts("F");}return 0;
}