Parsing a boolean expression

String Stack Recursion

69.8% acceptance

Feb 25, 2026

1923

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn parse_bool_expr(expression: String) -> bool {
    let chars: Vec<char> = expression.chars().collect();
    let mut pos = 0;
    Self::parse(&chars, &mut pos)
  }

  fn parse(chars: &[char], pos: &mut usize) -> bool {
    match chars[*pos] {
      't' => { *pos += 1; true }
      'f' => { *pos += 1; false }
      '!' => {
        *pos += 2; // skip '!('
        let val = !Self::parse(chars, pos);
        *pos += 1; // skip ')'
        val
      }
      '&' => {
        *pos += 2; // skip '&('
        let mut result = true;
        loop {
          result &= Self::parse(chars, pos);
          if chars[*pos] == ')' { *pos += 1; break; }
          *pos += 1; // skip ','
        }
        result
      }
      '|' => {
        *pos += 2; // skip '|('
        let mut result = false;
        loop {
          result |= Self::parse(chars, pos);
          if chars[*pos] == ')' { *pos += 1; break; }
          *pos += 1; // skip ','
        }
        result
      }
      _ => unreachable!()
    }
  }
}