利用逆波蘭表達(dá)式解決簡(jiǎn)單的&|表達(dá)式求解

題目描述

1祷膳，‘0’和‘1’是兩種合法表達(dá)式祭衩。
2浴井，!0 = 1,!1 = 0.

輸入描述:

輸入的第一行為一個(gè)正整數(shù)T谆扎，表示測(cè)試數(shù)據(jù)組數(shù)。 接下來(lái)有T組數(shù)據(jù)浙于。每組數(shù)據(jù)為一個(gè)表達(dá)式字符串(無(wú)空格)

輸出描述:

對(duì)于每一組數(shù)據(jù)护盈，輸出一行，包含一個(gè)整數(shù)羞酗，為表達(dá)式的解

輸入例子1:

3
!0
(0|(1&))
(0|(1&(!0)))

輸出例子1:

1
0
1

#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
#include<stack>
using namespace std;



int main() {
    int t = 0; 
    cin >> t;
    for (int tt = 0; tt < t; tt++) {
        string s = "";
        cin >> s;
        stack<char> nums;
        stack<char> ccc;
        for (int i = 0; i < s.size(); i++) {
            switch (s[i])
            {
            case '!':
                ccc.push('!');
                break;
            case '|':
                if (ccc.top() == '!') {
                    while (ccc.top() != '!') {
                        nums.push(ccc.top());
                        ccc.pop();
                    }
                }
                else {
                    ccc.push('|');
                }
                break;
            case '&':
                if (ccc.top() == '!') {
                    while (ccc.top() != '!') {
                        nums.push(ccc.top());
                        ccc.pop();
                    }
                }
                else {
                    ccc.push('&');
                }
                break;
            case '(':
                ccc.push('(');
                break;
            case ')':
                while (ccc.top() != '(') {
                    nums.push(ccc.top());
                    ccc.pop();
                }
                ccc.pop();
                break;
            default:
                nums.push(s[i]);
                break;
            }
        }//nums棧最后保存了中綴表達(dá)式轉(zhuǎn)換后的逆波蘭表達(dá)式



        stack<char> anss;
        while (!nums.empty()) {
            anss.push(nums.top());
            nums.pop();
        }//倒置腐宋，轉(zhuǎn)換成字符串也行，懶得換了

        stack<char> ans;
        while (!anss.empty()) {
            if (anss.top() == '!') {
                ans.top() = ans.top() == '0' ? '1' : '0';
                anss.pop();
            }
            else if (anss.top() == '|') {
                char a = ans.top();
                ans.pop();
                char b = ans.top();
                ans.pop();

                if (a == '1' || b == '1') {
                    ans.push('1');
                }
                else {
                    ans.push('0');
                }
                anss.pop();
            }
            else if (anss.top() == '&') {
                char a = ans.top();
                ans.pop();
                char b = ans.top();
                ans.pop();

                if (a == '1' && b == '1') {
                    ans.push('1');
                }
                else {
                    ans.push('0');
                }
                anss.pop();
            }
            else {
                ans.push(anss.top());
                anss.pop();
            }
        }

        cout << ans.top() << endl;
        
    }
    return 0;
    //(0|(1&(!0)))
}