力扣(LeetCode)1106. 解析布尔表达式(C++)

栈模拟

名为困难，实为编译原理基础题，科班玩家觉得简单。
编译器，最常见的数据结构是栈和二叉树。纯表达式的题目，用栈就可以了。

栈模拟 : 遍历 $expression$ 的所有字符，记作 $x$ 。 $x$ 不是 ${}^{\prime }{)}^{\prime }$ 则压栈 $x$ ； $x$ 是 ${}^{\prime }{)}^{\prime }$ , 则匹配栈顶的字符，匹配一个字符，弹栈一个，直到栈顶为 ${}^{\prime }{(}^{\prime }$ 停止匹配。特别的，$x$ 遇到 ${}^{\prime }{,}^{\prime }$ 不压栈，$continue$ 即可。

代码展示

class Solution {
public:
    bool parseBoolExpr(string expression) {
        //使用栈存储，模拟
        stack<char> stk;
        for(auto x:expression){
            if(','==x) continue;//不用管','
            else if(')'==x){//进行运算'
                int cntF = 0;//统计'F'出现的次数
                int cntT = 0;//统计'T'出现的次数
                while(stk.top()!='('){//只要没遇到'(',继续运算
                    if('f'==stk.top()) cntF++;//遇到F
                    else cntT++;//'t'==stk.top()
                    stk.pop();
                }
                stk.pop();//弹出'('
                char tmp = stk.top();//暂存操作符
                stk.pop();//弹出操作符
                if('!'==tmp) stk.push(1==cntT?'f':'t');//压入相反字符
                else if('|'==tmp) stk.push(cntT>0?'t':'f');
                else stk.push(cntF>0?'f':'t');//'&'==tmp
            }else{
                stk.push(x);//除了')'的字符，全部压栈
            }
        }
        return 't'==stk.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度:$O(n)$， $n$ 是 $expression$ 的长度。一次遍历 $expression$ 的时间复杂度是$O(n)$。
2. 空间复杂度:$O(n)$。字符栈 $stk$ 最多压栈 $n$ 个元素，最坏空间复杂度 $O(n)$。