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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Parsing A Boolean Expression

Number: 1197

Difficulty: Hard

Paid? No

Companies: Google, Meta, Amazon, Microsoft, HiLabs, Affinity

Problem Description

Evaluate a boolean expression given as a string that consists of the literals 't' (true) and 'f' (false), as well as the operators:

  • '!' for logical NOT,
  • '&' for logical AND, and
  • '|' for logical OR. The expression follows a nested recursive format with parentheses and commas to separate operands.

Key Insights

  • The expression is recursively defined. When encountering an operator, you must process the subexpressions enclosed in parentheses.
  • Using recursion or a stack effectively handles nested and comma-separated subexpressions.
  • A pointer or index variable helps traverse the input string without pre-tokenizing.
  • Beware of correctly handling the comma separator, ensuring you don’t process extra characters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the expression, since every character is processed one time. Space Complexity: O(n) in the worst case for the recursion/stack usage when the expression is deeply nested.

Solution

The approach is to parse the expression recursively:

  1. Use a pointer (or index variable) to traverse the string.
  2. When a literal ('t' or 'f') is encountered, return its corresponding boolean value.
  3. For operators ('!', '&', '|'):
    • For '!', process the single subexpression inside its parentheses and return the negated value.
    • For '&' and '|', parse the comma-separated subexpressions within the parentheses. For '&', ensure all subexpressions are true; for '|', check if at least one is true.
  4. Skip commas and parenthesis characters as needed.
  5. Recursive parsing naturally handles the nested structure.

Data structures used include:

  • Recursion for natural nested parsing.
  • A pointer (index variable) that is passed among recursive calls to keep track of the current parsing position.

This method avoids any extra tokenization and directly interprets the expression.

Code Solutions

def parse_bool_expr(expression: str) -> bool:
    # Use a mutable index pointer encapsulated in a list so that it can be updated in nested calls
    index = [0]
    
    def helper() -> bool:
        # Get the current character
        char = expression[index[0]]
        if char == 't':
            index[0] += 1  # advance pointer
            return True
        if char == 'f':
            index[0] += 1  # advance pointer
            return False
        if char == '!':
            index[0] += 2  # skip '!' and '('
            # Parse the subexpression inside the parentheses
            result = helper()
            index[0] += 1  # skip the closing ')'
            return not result
        if char in '&|':
            op = char  # store operator
            index[0] += 2  # skip operator and '('
            # For '&' and '|' we aggregate multiple subexpressions separated by commas.
            # Initialize result based on operator.
            result = True if op == '&' else False
            # Process first subexpression always
            result = helper() if op == '&' else helper()
            # Process subsequent subexpressions
            while expression[index[0]] == ',':
                index[0] += 1  # skip comma
                current = helper()
                if op == '&':
                    result = result and current
                else:
                    result = result or current
            index[0] += 1  # skip the closing ')'
            return result
    
    return helper()

# Example usage:
# print(parse_bool_expr("&(|(f))"))  # Output: False
# print(parse_bool_expr("|(f,f,f,t)"))  # Output: True
# print(parse_bool_expr("!(& (f,t))".replace(" ","")))  # Output: True
← Back to All Questions