We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Parsing A Boolean Expression

Difficulty: Hard

Problem Description

Given a string expression that represents a boolean expression, return the evaluation of that expression. The expression can consist of the literals 't' (true) and 'f' (false), logical NOT '!', logical AND '&', and logical OR '|', along with parentheses for grouping.

Key Insights

  • The expression can be evaluated using a stack to manage nested expressions.
  • Each operator has a different evaluation rule: NOT negates a single expression, AND requires all expressions to be true, and OR requires at least one expression to be true.
  • The evaluation must handle nested sub-expressions correctly.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the expression. Each character is processed at most twice (once when pushing to stack and once when evaluating). Space Complexity: O(n) in the worst case due to the stack used for managing nested expressions.

Solution

The solution involves using a stack to keep track of the current state of the boolean expression being evaluated. We iterate through the expression character by character. When encountering an operator or a parenthesis, we determine how to process the current expression based on the rules of boolean logic. The stack helps in managing nested expressions and applying the correct logical operations.

Code Solutions

def parseBoolExpr(expression: str) -> bool:
    stack = []
    n = len(expression)
    i = 0
    
    while i < n:
        if expression[i] == 't':
            stack.append(True)
        elif expression[i] == 'f':
            stack.append(False)
        elif expression[i] == '!':
            stack.append('!')
        elif expression[i] == '&':
            stack.append('&')
        elif expression[i] == '|':
            stack.append('|')
        elif expression[i] == ')':
            # Evaluate the expression
            sub_expr = []
            while stack and stack[-1] != '(':
                sub_expr.append(stack.pop())
            stack.pop()  # remove the '('
            operator = stack.pop()
            if operator == '!':
                stack.append(not sub_expr[0])
            elif operator == '&':
                stack.append(all(sub_expr))
            elif operator == '|':
                stack.append(any(sub_expr))
        i += 1
    
    return stack[0]
← Back to All Questions