Solution: Parsing a Boolean Expression

Statement

You are given a string, expression, that represents a boolean expression. The expression can take one of the following forms:

• 't': Represents the boolean value TRUE.

• 'f': Represents the boolean value FALSE.

• '!(expr)': Represents a NOT operation applied to a subexpression expr. It returns the logical negation of expr.

• '&(expr1, expr2, ..., exprN)': Represents an AND operation over one or more subexpressions. It returns TRUE only if all subexpressions evaluate to TRUE.

• '|(expr1, expr2, ..., exprN)': Represents an OR operation over one or more subexpressions. It returns TRUE if at least one of the subexpressions evaluates to TRUE.

Your task is to parse this expression and return its boolean evaluation result.

Note: The input expression is guaranteed to always be valid and strictly adhere to the specified format and rules.

Constraints:

• $1 \leq$ expression.length $\leq 20000$

• expression[i] is one of the following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

Solution

The core intuition behind solving this problem is to evaluate a nested boolean expression using a stack-based approach that mimics how humans solve expressions from the inside out, starting with the innermost parentheses. Values and operators are pushed onto the stack as the expression is scanned character by character. When a closing parenthesis is encountered, it signals the end of a subexpression. The algorithm then collects all the boolean values inside that subexpression by popping the stack, applies the appropriate boolean operator, and pushes the result back onto the stack. This process repeats until the entire expression is reduced to a single boolean value at the top of the stack, representing the final result.

Using the intuition above, we implement the algorithm as follows:

1. Initialize a stack, st, to keep track of characters in the expression.

2. Iterate through each character c in the input string expression:

   1. If c is a closing parenthesis ')', it marks the end of a subexpression:

      1. Initialize an array, values, to collect the boolean values inside the subexpression.

      2. Pop characters from the stack and append to values until an opening parenthesis '(' is found. Pop '('.

      3. The operator (one of '!', '&', or '|') is located just before '('; pop it.

      4. Call the helper function evaluateSubExpr(op, values) to compute the subexpression result.

      5. Push the result ('t' or 'f') back onto the stack.

   2. Else if c is not a comma ',', push it onto the stack (we skip commas as they are only separators).

3. After the loop ends, the final evaluation result is at the top of the stack. Return TRUE if it is 't', else return FALSE.

The evaluateSubExpr helper function receives op and values and evaluates the subexpression according to these rules:

• For NOT ('!'): Return 'f' if the only value is 't'; else return 't'.

• For AND ('&'): If any value is 'f', return 'f'; otherwise, return 't'.

• For OR ('|'): If any value is 't', return 't'; otherwise, return 'f'.

Let’s look at the following illustration to get a better understanding of the solution: