題目大意：F表示0，V表示1。通過邏輯運算得出最后答案是真還是假，真輸出V，假輸出F。
思路：通過棧，將原式處理為后綴表達(dá)式，然后進(jìn)行計算。
后綴表達(dá)式又叫逆波蘭表達(dá)式：
這里可以通過優(yōu)先級不同來構(gòu)建一個后綴表達(dá)式。
將'！'的優(yōu)先級定為3級，'&'定為2級，'|'定為1級（級別越大，優(yōu)先級越高）
寫入的時候用queue構(gòu)建一個后綴表達(dá)式。用stack暫時存儲運算符號。
對于F和V直接存入queue
對于符號：
stack存儲原則：按照優(yōu)先級從低到高放入，如果下一個將要放入的符號的優(yōu)先級低于最后一個存入stack的符號的優(yōu)先級，那么就將stack存入的符號依次取出并存入queue，直到滿足優(yōu)先級從低到高排列。
例如：
V|V|V&F&!V|F&V&V|F
1：V
將V存入queue
queue：V
stack：
2：|
將|存入stack
queue：V
stack：|
3：V
將V存入queue
queue：VV
stack：|
4：|
由于stack的優(yōu)先級不滿足，將stack的|取出放入queue（此時stack已空），將此時的|放入stack
queue：VV|
stack：|
5：V
將V存入queue
queue：VV|V
stack：|
6：&
將&存入stack(&的優(yōu)先級高于|)
queue：VV|V
stack：|&
7：F
將F存入queue
queue：VV|VF
stack：|&
8：&
將stack的&取出并放入queue，然后滿足優(yōu)先級低高順序，再將現(xiàn)在的&放入stack
queue：VV|VF&
stack：|&
9：！
將！放入stack（！的優(yōu)先級高于&）
queue：VV|VF&
stack：|&！
10：V
將V存入queue
queue：VV|VF&V
stack：|&！
11：|
由于|優(yōu)先級低于！且低于&且低于|
queue：VV|VF&V！&|
stack：|
…………
最后可以得到：
VV|VF&V!&|FV&V&|F| (后綴表達(dá)式構(gòu)建完成)
第二步：用stack計算后綴表達(dá)式
push（V）
stack:V
push（V）
stack:VV
x=pop（）且y=pop（） res=x||y 將res換成V（F）再push(res)
stack:(V||V)
push（V）
stack:(V||V)V
push（F）
stack:(V||V)VF
x=pop（）且y=pop（） res=x&&y 將res換成V（F）再push(res)
stack:(V||V)(V&&F)
push（V）
stack:(V||V)(V&&F)V
x=pop（） res=!x 將res換成V（F）再push(res)
stack:(V||V)(V&&F)(!V)
x=pop（）且y=pop（） res=x&&y 將res換成V（F）再push(res)
stack:(V||V)((V&&F)&&(!V))
x=pop（）且y=pop（） res=x||y 將res換成V（F）再push(res)
stack:((V||V)||((V&&F)&&(!V)))
push（F）
stack:((V||V)||((V&&F)&&(!V)))F
push（V）
stack:((V||V)||((V&&F)&&(!V)))FV
x=pop（）且y=pop（） res=x&&y 將res換成V（F）再push(res)
stack:((V||V)||((V&&F)&&(!V)))(F&&V)
push（V）
stack:((V||V)||((V&&F)&&(!V)))(F&&V)V
x=pop（）且y=pop（） res=x&&y 將res換成V（F）再push(res)
stack:((V||V)||((V&&F)&&(!V)))((F&&V)&&V)
x=pop（）且y=pop（） res=x||y 將res換成V（F）再push(res)
stack:((V||V)||(((V&&F)&&(!V)))||((F&&V)&&V))
push（F）
stack:((V||V)||(((V&&F)&&(!V)))||((F&&V)&&V))F
x=pop（）且y=pop（） res=x||y 將res換成V（F）再push(res)
stack:((V||V)||(((V&&F)&&(!V)))||((F&&V)&&V))||F
最后對比下V|V|V&F&!V|F&V&V|F會發(fā)現(xiàn)結(jié)果和預(yù)期一樣
總結(jié)：
構(gòu)建后綴表達(dá)式：
①對于字母：直接推入queue
②對于運算符：
Ⅰ.按照運算符的高低級 由低到高推入stack
Ⅱ.若不滿足就從stack依次取出最后一個運算符，并推入queue，直到滿足運算符的高低級順序，再將此時的運算符推入stack
計算后綴表達(dá)式：
從queue依次取出：
①如果為字母，直接推入stack
②如果為運算符：
Ⅰ.運算符為！，則從stack取出最后一個字母，計算！x后，再推入stack
Ⅱ.運算符為|或&，則從stack取出最后兩個字母，計算x&&y后，再推入stack
對于此題，比較后會發(fā)現(xiàn)，此題多了個'（'和'）'
于是再加一個判別條件：
當(dāng)此時a[i]=')'時，取出存儲運算符的stack的最后一個運算符并存入queue，依次重復(fù)本操作，直到遇見'('
if(a[i]==')')
{
while(s.top()!='(')
{
q.push(s.top());
s.pop();
}
s.pop();
}
此題完整代碼：
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;
char a[10010];
stack<char> s;//save operation symbol
queue<char> q;//suffix expression
int f(char x)//'V'or'F'?
{
if(x=='V') return 1;
else return 0;
}
int op(char c)//priority
{
if(c=='(') return 4;
if(c=='!') return 3;
if(c=='&') return 2;
if(c=='|') return 1;
}
void Clear()
{
while(s.size())
{
s.pop();
}
}
void init(int len)
{
int i;
Clear();
for(i=0; i<len; i++)
{
if(a[i]!=' ')
{
if(a[i]=='F' || a[i]=='V') q.push(a[i]);
else if(a[i]=='!' && s.size() && s.top()=='!') s.pop(); //Two '!'
else if(!s.size()) s.push(a[i]);
else if(a[i]==')')
{
while(s.top()!='(')
{
q.push(s.top());
s.pop();
}
s.pop();
}
else if(op(s.top())==4 || (op(a[i])>op(s.top()))) s.push(a[i]);//'(' is first input last output
else if(op(s.top())!=4 && (op(a[i])<=op(s.top())))
{
q.push(s.top());
s.pop();
while(s.size() && op(s.top())!=4 && op(a[i])<=op(s.top()))
{
q.push(s.top());
s.pop();
}
s.push(a[i]);
}
}
}
while(s.size())
{
q.push(s.top());
s.pop();
}
}
void sum()
{
char x, y, temp;
bool res=1;
while(q.size())
{
temp=q.front();
if(temp=='V' || temp=='F')
{
s.push(temp);
q.pop();
}
else if(temp=='&')
{
x=s.top();
s.pop();
y=s.top();
s.pop();
res=f(x)&&f(y);
if(res==1) s.push('V');
else s.push('F');
q.pop();
}
else if(temp=='|')
{
x=s.top();
s.pop();
y=s.top();
s.pop();
res=f(x)||f(y);
if(res==1) s.push('V');
else s.push('F');
q.pop();
}
else if(temp=='!')
{
x=s.top();
s.pop();
if(f(x)==1) s.push('F');
else s.push('V');
q.pop();
}
}
}
int main()
{
int cnt=1, len;
while(gets(a)!=NULL)
{
len=strlen(a);
init(len);
sum();
printf("Expression %d: %c\n", cnt++, s.top());
}
return 0;
}
