【力扣】1106. 解析布尔表达式（C++/Go 栈的应用）

题目链接

题意

给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。

有效的表达式需遵循以下约定：

“t”，运算结果为 True
“f”，运算结果为 False
“!(expr)”，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
“&(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 与的运算（AND）
“|(expr1,expr2,…)”，运算过程为对 2 个或以上内部表达式 expr1, expr2, … 进行逻辑 或的运算（OR）

思路

类似于表达式求值的题目，用栈来求解。
遍历字符串，

• 如果当前字符是逗号的话，跳过；
• 如果当前字符不是右括号，将该字符添加到栈里；
• 如果是右括号，说明要求值了。遍历前面的字符直到遇到左括号，记录t,f的个数。再根据运算符分类讨论。

1. 运算符为!。当f的个数为1时，结果才为t；其余结果为f
2. 运算符为&。当f的个数为0时，结果才为t；其余结果为f
3. 运算符为|。当t的个数为0时，结果才为f；其余结果为t
   将结果放入栈里

• 遍历完成后，如果栈顶字符为t说明表达式值为true

代码

class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char>stk;
        for(int i=0;i<expression.size();i++){
            if(expression[i]==','){
                continue;
            }else if(expression[i]!=')'){
                stk.push(expression[i]);
            }else{
                int t=0,f=0;
                while(stk.top()!='('){
                    if(stk.top()=='t') t++;
                    else f++;
                    stk.pop();
                }
                stk.pop();
                char op = stk.top();stk.pop();
                if(op=='!'){
                    if(f==1) stk.push('t');
                    else stk.push('f');
                }else if(op=='&'){
                    if(f==0) stk.push('t');
                    else stk.push('f');
                }else if(op=='|'){
                    if(t==0) stk.push('f');
                    else stk.push('t');
                }
            }
        }
        return stk.top()=='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
29
30
31
32
33

func parseBoolExpr(expression string) bool {
    stk := []rune{}
    for _,val := range expression {
        if val == ','{
            continue
        }
        if val != ')' {
            stk=append(stk,val)
            continue
        }
        t := 0
        f := 0
        for stk[len(stk)-1] != '(' {
            ch := stk[len(stk)-1]
            if ch == 't' {
                t++
            }else{
                f++
            }
            stk = stk[:len(stk)-1]
        }    
        stk = stk[:len(stk)-1]
        op := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        if op == '!' {
            if f == 1 {
                stk = append(stk, 't')
            }else{
                stk = append(stk, 'f')
            }
        }else if op == '&' {
            if f == 0 {
                stk = append(stk, 't')
            }else{
                stk = append(stk, 'f')
            }   
        }else if op == '|' {
            if t == 0 {
                stk = append(stk, 'f')
            }else{
                stk = append(stk, 't')
            }   
        }
    }
    return stk[len(stk)-1] == '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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46