Question

1106. 解析布尔表达式

English Version

题目描述

布尔表达式 是计算结果不是 true 就是 false 的表达式。有效的表达式需遵循以下约定：

• 't'，运算结果为 true
• 'f'，运算结果为 false
• '!(subExpr)'，运算过程为对内部表达式 subExpr 进行 逻辑非（NOT）运算
• '&(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑与（AND）运算
• '|(subExpr1, subExpr2, ..., subExprn)'，运算过程为对 2 个或以上内部表达式 subExpr1, subExpr2, ..., subExprn 进行 逻辑或（OR）运算

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

题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。

 

示例 1：

输入：expression = "&(|(f))"
输出：false
解释：
首先，计算 |(f) --> f ，表达式变为 "&(f)" 。
接着，计算 &(f) --> f ，表达式变为 "f" 。
最后，返回 false 。

示例 2：

输入：expression = "|(f,f,f,t)"
输出：true
解释：计算 (false OR false OR false OR true) ，结果为 true 。

示例 3：

输入：expression = "!(&(f,t))"
输出：true
解释：
首先，计算 &(f,t) --> (false AND true) --> false --> f ，表达式变为 "!(f)" 。
接着，计算 !(f) --> NOT false --> true ，返回 true 。

 

提示：

• 1 <= expression.length <= 2 * 104
• expression[i] 为 '('、')'、'&'、'|'、'!'、't'、'f' 和 ',' 之一

解法

方法一：栈

对于这种表达式解析问题，我们可以使用栈来辅助解决。

从左到右遍历表达式 expression，对于遍历到的每个字符 $c$：

• 如果 $c$ 是 "tf!&|" 中的一个，我们直接将其入栈；
• 如果 $c$ 是右括号 ')'，我们将栈中元素依次出栈，直到遇到操作符 '!' 或 '&' 或 '|'。过程中我们用变量 $t$ 和 $f$ 记录出栈字符中 't' 和 'f' 的个数。最后根据出栈字符的个数和操作符计算得到新的字符 't' 或 'f'，并将其入栈。

遍历完表达式 expression 后，栈中只剩下一个字符，如果是 't'，返回 true，否则返回 false。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是表达式 expression 的长度。

class Solution:
  def parseBoolExpr(self, expression: str) -> bool:
    stk = []
    for c in expression:
      if c in 'tf!&|':
        stk.append(c)
      elif c == ')':
        t = f = 0
        while stk[-1] in 'tf':
          t += stk[-1] == 't'
          f += stk[-1] == 'f'
          stk.pop()
        match stk.pop():
          case '!':
            c = 't' if f else 'f'
          case '&':
            c = 'f' if f else 't'
          case '|':
            c = 't' if t else 'f'
        stk.append(c)
    return stk[0] == 't'

class Solution {
  public boolean parseBoolExpr(String expression) {
    Deque<Character> stk = new ArrayDeque<>();
    for (char c : expression.toCharArray()) {
      if (c != '(' && c != ')' && c != ',') {
        stk.push(c);
      } else if (c == ')') {
        int t = 0, f = 0;
        while (stk.peek() == 't' || stk.peek() == 'f') {
          t += stk.peek() == 't' ? 1 : 0;
          f += stk.peek() == 'f' ? 1 : 0;
          stk.pop();
        }
        char op = stk.pop();
        c = 'f';
        if ((op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0)) {
          c = 't';
        }
        stk.push(c);
      }
    }
    return stk.peek() == 't';
  }
}

class Solution {
public:
  bool parseBoolExpr(string expression) {
    stack<char> stk;
    for (char c : expression) {
      if (c != '(' && c != ')' && c != ',')
        stk.push(c);
      else if (c == ')') {
        int t = 0, f = 0;
        while (stk.top() == 't' || stk.top() == 'f') {
          t += stk.top() == 't';
          f += stk.top() == 'f';
          stk.pop();
        }
        char op = stk.top();
        stk.pop();
        if (op == '!') c = f ? 't' : 'f';
        if (op == '&') c = f ? 'f' : 't';
        if (op == '|') c = t ? 't' : 'f';
        stk.push(c);
      }
    }
    return stk.top() == 't';
  }
};

func parseBoolExpr(expression string) bool {
  stk := []rune{}
  for _, c := range expression {
    if c != '(' && c != ')' && c != ',' {
      stk = append(stk, c)
    } else if c == ')' {
      var t, f int
      for stk[len(stk)-1] == 't' || stk[len(stk)-1] == 'f' {
        if stk[len(stk)-1] == 't' {
          t++
        } else {
          f++
        }
        stk = stk[:len(stk)-1]
      }
      op := stk[len(stk)-1]
      stk = stk[:len(stk)-1]
      c = 'f'
      if (op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0) {
        c = 't'
      }
      stk = append(stk, c)
    }
  }
  return stk[0] == 't'
}

function parseBoolExpr(expression: string): boolean {
  const expr = expression;
  const n = expr.length;
  let i = 0;
  const dfs = () => {
    let res: boolean[] = [];
    while (i < n) {
      const c = expr[i++];
      if (c === ')') {
        break;
      }

      if (c === '!') {
        res.push(!dfs()[0]);
      } else if (c === '|') {
        res.push(dfs().some(v => v));
      } else if (c === '&') {
        res.push(dfs().every(v => v));
      } else if (c === 't') {
        res.push(true);
      } else if (c === 'f') {
        res.push(false);
      }
    }
    return res;
  };
  return dfs()[0];
}

impl Solution {
  fn dfs(i: &mut usize, expr: &[u8]) -> Vec<bool> {
    let n = expr.len();
    let mut res = Vec::new();
    while *i < n {
      let c = expr[*i];
      *i += 1;
      match c {
        b')' => {
          break;
        }
        b't' => {
          res.push(true);
        }
        b'f' => {
          res.push(false);
        }
        b'!' => {
          res.push(!Self::dfs(i, expr)[0]);
        }
        b'&' => {
          res.push(
            Self::dfs(i, expr)
              .iter()
              .all(|v| *v)
          );
        }
        b'|' => {
          res.push(
            Self::dfs(i, expr)
              .iter()
              .any(|v| *v)
          );
        }
        _ => {}
      }
    }
    res
  }

  pub fn parse_bool_expr(expression: String) -> bool {
    let expr = expression.as_bytes();
    let mut i = 0;
    Self::dfs(&mut i, expr)[0]
  }
}