leetcode：1106. 解析布尔表达式【栈的应用】

题目截图

题目分析

• 右括号的出现代表一个表达式的结果的生成 要么t要么f
• 逗号无用
• 其余都可以存入栈
• 遇到右括号，开始pop
• 记录中途的t和f，遇到左括号，再前一个就是运算符
• 根据不同的运算符以及t和f的关系，可以计算出该表达式的t或者f即可

ac code

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        st = []
        for c in expression:
            if c == ',':
                continue
            if c != ')':
                st.append(c)
                continue
            t = f = 0
            while st[-1] != '(':
                if st.pop() == 't':
                    t += 1
                else:
                    f += 1
            st.pop()
            op = st.pop()
            if op == '!':
                it = 't' if f == 1 else 'f'
            elif op == '&':
                it = 't' if f == 0 else 'f'
            else:
                it = 't' if t > 0 else 'f'
            st.append(it)
        
        return st[0] == 't'
                
            
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

总结

栈就是适合计算这种表达式的