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: Depth-First Search

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} expression
 * @return {boolean}
 */
const parseBoolExpr = function (expression) {
  const n = expression.length;

  const express = (a, b, operator) => {
    if (a === -1) return b;
    if (operator === '&') return a & b;

    return a | b;
  };

  const parseExpression = (start, end) => {
    const operator = expression[start];
    let result = -1;

    for (let index = start + 1; index <= end; index++) {
      const current = expression[index];

      if (/[!&|]/.test(current)) {
        const left = index;
        let layer = 0;

        while (expression[index] !== ')' || layer !== 1) {
          if (expression[index] === '(') layer += 1;
          if (expression[index] === ')') layer -= 1;
          index += 1;
        }
        const subResult = parseExpression(left, index);

        result = express(result, subResult, operator);
      } else if (current === 't') {
        result = express(result, true, operator);
      } else if (current === 'f') {
        result = express(result, false, operator);
      }
    }
    return operator === '!' ? !result : result;
  };

  return parseExpression(0, n - 1);
};