Question

1106. Parsing A Boolean Expression

中文文档

Description

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:

• 't' that evaluates to true.
• 'f' that evaluates to false.
• '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr.
• '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.
• '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.

Given a string expression that represents a boolean expression, return _the evaluation of that expression_.

It is guaranteed that the given expression is valid and follows the given rules.

 

Example 1:

Input: expression = "&(|(f))"
Output: false
Explanation: 
First, evaluate |(f) --> f. The expression is now "&(f)".
Then, evaluate &(f) --> f. The expression is now "f".
Finally, return false.

Example 2:

Input: expression = "|(f,f,f,t)"
Output: true
Explanation: The evaluation of (false OR false OR false OR true) is true.

Example 3:

Input: expression = "!(&(f,t))"
Output: true
Explanation: 
First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)".
Then, evaluate !(f) --> NOT false --> true. We return true.

 

Constraints:

• 1 <= expression.length <= 2 * 104
• expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

Solutions

Solution 1: Stack

For this type of expression parsing problem, we can use a stack to assist.

We traverse the expression expression from left to right. For each character $c$ we encounter:

• If $c$ is one of "tf!&|", we push it directly onto the stack;
• If $c$ is a right parenthesis ')', we pop elements from the stack until we encounter an operator '!', '&', or '|'. During this process, we use variables $t$ and $f$ to record the number of 't' and 'f' characters popped from the stack. Finally, based on the number of characters popped and the operator, we calculate a new character 't' or 'f' and push it onto the stack.

After traversing the expression expression, there is only one character left in the stack. If it is 't', return true, otherwise return false.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the expression 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]
  }
}