题意分析

题目要求解析并计算给定的布尔表达式，其中：

$V$ 表示 $True$，$F$ 表示 $False$。

运算符包括 $!$（非）、&（与）、$|$（或）。

表达式可能包含括号，用于改变运算优先级。

输入多行表达式，每行长度不超过 $1000$ 字符，需处理空格和嵌套括号。

解题思路

​$1$. 双栈法​：

​操作数栈$（val）$​​：存储布尔值（$0$ 或 $1$）。

​运算符栈$（op）$​​：存储运算符（!、&、|）和括号。

​优先级处理​：$! >$ &$> |$，括号内优先计算。

$2$. ​核心逻辑​： ​ 遍历字符​：跳过空格，根据字符类型处理： ​V/F​：转换为 1/0，处理前置 ! 后压入 val。 ​ (​：直接压入 op。 ​ )：弹出 op 栈顶运算符直到 (，计算括号内表达式。 ​ 运算符​：处理栈顶更高优先级的运算符，再压入当前运算符。 ​ $3$. 特殊处理​：

​$!$ 运算符​：单目运算，直接修改栈顶布尔值。

​括号嵌套​：递归处理括号内表达式，注意括号前的 $!$（如 $!(...)）$。

$4$. ​最终计算​：

遍历结束后，清空 $op$栈，完成剩余运算，输出 $val$ 栈顶结果。

标程

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

int main()
{
    char s[1025];
    int casei = 1;
    while (cin.getline(s, 1025))
    {
        stack<int> val;
        stack<char> op;
        int len = strlen(s);
        for (int i = 0; i < len; i++)
        {
            if (s[i] == ' ')
                continue;
            else if (s[i] == '(')
                op.push(s[i]);
            else if (s[i] == 'F' || s[i] == 'V')
            {
                int t = (s[i] == 'F' ? 0 : 1);
                while (!op.empty() && op.top() == '!')
                {
                    t = !t;
                    op.pop();
                }
                val.push(t);
            }
            else if (s[i] == '|')
            {
                if (!op.empty() && (op.top() == '&' || op.top() == '|'))
                {
                    int a = val.top();
                    val.pop();
                    int b = val.top();
                    val.pop();
                    if (op.top() == '&')
                        val.push(a & b);
                    else
                        val.push(a | b);
                    op.pop();
                    while (!op.empty() && op.top() == '!')
                    {
                        int a = val.top();
                        val.pop();
                        val.push(!a);
                        op.pop();
                    }
                }
                while (!op.empty() && op.top() == '!')
                {
                    int a = val.top();
                    val.pop();
                    val.push(!a);
                    op.pop();
                }
                
                op.push(s[i]);
            }
            else if (s[i] == '&')
            {
                if (!op.empty() && (op.top() == '&'))
                {
                    int a = val.top();
                    val.pop();
                    int b = val.top();
                    val.pop();
                    val.push(a & b);
                    op.pop();
                    while (!op.empty() && op.top() == '!')
                    {
                        int a = val.top();
                        val.pop();
                        val.push(!a);
                        op.pop();
                    }
                    
                }
                while (!op.empty() && op.top() == '!')
                {
                    int a = val.top();
                    val.pop();
                    val.push(!a);
                    op.pop();
                }
                op.push(s[i]);
            }
            else if (s[i] == ')')
            {
                while (!op.empty() && op.top() != '(')
                {
                    if (op.top() == '&' || op.top() == '|')
                    {
                        int a = val.top();
                        val.pop();
                        int b = val.top();
                        val.pop();
                        if (op.top() == '&')
                            val.push(a & b);
                        else
                            val.push(a | b);
                        op.pop();
                        while (!op.empty() && op.top() == '!')
                        {
                            int a = val.top();
                            val.pop();
                            val.push(!a);
                            op.pop();
                        }
                    }
                    else if (op.top() == '!')
                    {
                        int a = val.top();
                        val.pop();
                        val.push(!a);
                        op.pop();
                    }
                }
                op.pop();
                while (!op.empty() && op.top() == '!')           
                {
                    int a = val.top();
                    val.pop();
                    val.push(!a);
                    op.pop();
                }
            }
            else if (s[i] == '!')
                op.push(s[i]);
        }
        while (!op.empty())
        {
            if (op.top() == '&' || op.top() == '|')
            {
                int a = val.top();
                val.pop();
                int b = val.top();
                val.pop();
                if (op.top() == '&')
                    val.push(a & b);
                else
                    val.push(a | b);
                op.pop();
                while (!op.empty() && op.top() == '!')
                {
                    int a = val.top();
                    val.pop();
                    val.push(!a);
                    op.pop();
                }
            }
            else if (op.top() == '!')
            {
                int a = val.top();
                val.pop();
                val.push(!a);
                op.pop();
            }
        }
        printf("Expression %d: %c\n", casei++, val.top() == 1 ? 'V' : 'F');
    }
    return 0;
}