Skip to content

解析表达式专题

1106. 有效的括号字符串

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

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

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

方法一 栈

本题可以用普通的表达式解析来求解，过程中维护一个栈，每次遇到 ) 时进行计算。遇到其他字符（不包括 ,）压入栈中。

具体的，每次遇到 ) 时，不断弹出栈中元素，直到遇到 (。过程中记录弹出的 f 和 t 的个数。然后拿到 ( 之前的运算符，根据 f 和 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
class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> st;
        for (auto c : expression) {
            if (c == ')') {
                int f = 0, t = 0;
                while (st.top() != '(') {
                    if (st.top() == 'f') {
                        f++;
                    } else {
                        t++;
                    }
                    st.pop();
                }
                st.pop(); // pop (
                char op = st.top(); // pop op
                st.pop();
                if (op == '!') {
                    st.push(f ? 't' : 'f');
                } else if (op == '&') {
                    st.push(f ? 'f' : 't');
                } else {
                    st.push(t ? 't' : 'f');
                }
            } else if (c != ',') {
                st.push(c);
            }
        }
        return st.top() == 't' ? true : false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        st = []
        for c in expression:
            if c == ')':
                f, t = 0, 0
                while st[-1] != '(':
                    if st[-1] == 'f':
                        f += 1
                    else:
                        t += 1
                    st.pop()
                st.pop()
                op = st[-1]
                st.pop()
                if op == '!':
                    st.append('t' if f else 'f')
                elif op == '&':
                    st.append('f' if f else 't')
                elif op == '|':
                    st.append('t' if t else 'f')
            elif c != ',':
                st.append(c)
        return True if st[-1] == 't' else False
本文访问 次