{x}
blog image

Parsing A Boolean Expression

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 ','.

Solution Explanation: Parsing a Boolean Expression

This problem requires parsing a boolean expression string and evaluating its truth value. The expression can contain logical operators (!, &, |), boolean literals (t, f), parentheses, and commas. A recursive or iterative approach using a stack is suitable for this task.

Approach: Using a Stack (Iterative)

The iterative approach with a stack offers a clear and efficient solution. The algorithm processes the expression from left to right. The stack stores intermediate results and operators.

Steps:

  1. Initialization: Create an empty stack.
  2. Iteration: Iterate through each character in the expression string.
  3. Handling Characters:
    • Operands (t, f): Push directly onto the stack.
    • Operators (!, &, |): Push onto the stack.
    • Commas (,): Ignore (they're just separators).
    • Opening Parenthesis ((): Ignore.
    • Closing Parenthesis ()): This signifies the end of a subexpression. Pop elements from the stack until an operator is encountered. Evaluate the subexpression based on the operator and the operands, and push the result back onto the stack.
  4. Evaluation: After processing the entire expression, the only remaining element on the stack is the final result (t or f).

Evaluation of Subexpressions:

When a closing parenthesis is encountered, the evaluation logic depends on the operator:

  • ! (NOT): If a single 'f' is found, the result is 't'; otherwise, it's 'f'.
  • & (AND): If any 'f' is found, the result is 'f'; otherwise, it's 't'.
  • | (OR): If any 't' is found, the result is 't'; otherwise, it's 'f'.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the expression string. Each character is processed once.
  • Space Complexity: O(n) in the worst case, as the stack's size could grow to be proportional to the length of the expression if deeply nested parentheses are present.

Code Examples (Python, Java, C++)

The following code examples demonstrate the stack-based iterative approach in different programming languages:

Python:

def parseBoolExpr(expression: str) -> bool:
    stack = []
    for char in expression:
        if char == ')':
            operands = []
            while stack and stack[-1] != '(':
                operands.append(stack.pop())
            stack.pop()  # Pop '('
            operator = stack.pop()
            result = evaluate(operator, operands)
            stack.append(result)
        elif char not in ['(', ',']:
            stack.append(char)
    return stack[0] == 't'
 
def evaluate(operator: str, operands: list) -> str:
    if operator == '!':
        return 't' if operands[0] == 'f' else 'f'
    elif operator == '&':
        return 't' if all(op == 't' for op in operands) else 'f'
    elif operator == '|':
        return 't' if any(op == 't' for op in operands) else 'f'

Java:

import java.util.Stack;
 
class Solution {
    public boolean parseBoolExpr(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char c : expression.toCharArray()) {
            if (c == ')') {
                List<Character> operands = new ArrayList<>();
                while (!stack.isEmpty() && stack.peek() != '(') {
                    operands.add(stack.pop());
                }
                stack.pop(); // Pop '('
                char operator = stack.pop();
                stack.push(evaluate(operator, operands));
            } else if (c != '(' && c != ',') {
                stack.push(c);
            }
        }
        return stack.pop() == 't';
    }
 
    private char evaluate(char operator, List<Character> operands) {
        if (operator == '!') {
            return operands.get(0) == 'f' ? 't' : 'f';
        } else if (operator == '&') {
            return operands.stream().allMatch(op -> op == 't') ? 't' : 'f';
        } else { // operator == '|'
            return operands.stream().anyMatch(op -> op == 't') ? 't' : 'f';
        }
    }
}

C++:

#include <stack>
#include <algorithm>
 
class Solution {
public:
    bool parseBoolExpr(string expression) {
        stack<char> stk;
        for (char c : expression) {
            if (c == ')') {
                vector<char> operands;
                while (!stk.empty() && stk.top() != '(') {
                    operands.push_back(stk.top());
                    stk.pop();
                }
                stk.pop(); // Pop '('
                char op = stk.top();
                stk.pop();
                stk.push(evaluate(op, operands));
            } else if (c != '(' && c != ',') {
                stk.push(c);
            }
        }
        return stk.top() == 't';
    }
 
private:
    char evaluate(char op, const vector<char>& operands) {
        if (op == '!') {
            return operands[0] == 'f' ? 't' : 'f';
        } else if (op == '&') {
            return all_of(operands.begin(), operands.end(), [](char c){ return c == 't'; }) ? 't' : 'f';
        } else { // op == '|'
            return any_of(operands.begin(), operands.end(), [](char c){ return c == 't'; }) ? 't' : 'f';
        }
    }
};

These examples provide a functional implementation of the stack-based approach. Remember to adapt the code to your preferred language and handle potential edge cases.