利用逆波兰表达式解决简单的&|表达式求解

题目描述

1，‘0’和‘1’是两种合法表达式。
2，!0 = 1,!1 = 0.

输入描述:

输入的第一行为一个正整数T，表示测试数据组数。 接下来有T组数据。每组数据为一个表达式字符串(无空格)

输出描述:

对于每一组数据，输出一行，包含一个整数，为表达式的解

输入例子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栈最后保存了中缀表达式转换后的逆波兰表达式



        stack<char> anss;
        while (!nums.empty()) {
            anss.push(nums.top());
            nums.pop();
        }//倒置，转换成字符串也行，懒得换了

        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)))
}