B - 2.Boolean Expressions

樣例

題目大意：F表示0，V表示1摊沉。通過邏輯運算得出最后答案是真還是假狐史，真輸出V，假輸出F说墨。
思路：通過棧骏全，將原式處理為后綴表達式，然后進行計算婉刀。

后綴表達式又叫逆波蘭表達式：

百度百科

這里可以通過優(yōu)先級不同來構(gòu)建一個后綴表達式吟温。
將'！'的優(yōu)先級定為3級突颊，'&'定為2級鲁豪，'|'定為1級（級別越大潘悼，優(yōu)先級越高）
寫入的時候用queue構(gòu)建一個后綴表達式。用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| (后綴表達式構(gòu)建完成)

構(gòu)建后綴表達式

第二步：用stack計算后綴表達式
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)建后綴表達式：
①對于字母：直接推入queue
②對于運算符：
Ⅰ.按照運算符的高低級 由低到高推入stack
Ⅱ.若不滿足就從stack依次取出最后一個運算符沥阳，并推入queue，直到滿足運算符的高低級順序自点，再將此時的運算符推入stack

計算后綴表達式：
從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;
}