1106. Parsing A Boolean Expression

HardStackRecursionString
Leetcode Link

Problem Description

The problem at hand entails evaluating a boolean expression that can be either true ('t') or false ('f'). The expression can take one of several forms: a direct true or false value, a negation of a subexpression, a logical AND of one or more subexpressions, or a logical OR of one or more subexpressions. The different expressions are represented as:

  • 't': evaluates to true
  • 'f': evaluates to false
  • '!(subExpr)': evaluates to the logical NOT of the inner expression subExpr
  • '&(subExpr1, subExpr2, ..., subExprn)': evaluates to the logical AND of all the inner expressions subExpr1, subExpr2, ..., subExprn (with n >= 1)
  • '|(subExpr1, subExpr2, ..., subExprn)': evaluates to the logical OR of all the inner expressions subExpr1, subExpr2, ..., subExprn (with n >= 1)

The goal is to compute the result of the given boolean expression, assured by the problem's constraints to be valid and conform to the rules above.

Intuition

The intuition behind the solution for evaluating the boolean expression is to process the expression in a structured way, making use of a stack to keep track of the characters that form a subexpression until it's complete and can be evaluated. This resembles the classic stack-based evaluation of expressions which is commonly used in parsing algorithms.

Here's how the approach breaks down:

  1. Initialize a Stack: Since the expression is nested with parentheses, we can use a stack to keep track of and evaluate the inner expressions in the correct order.

  2. Iterate through Each Character:

    • If we encounter a t, f, !, &, or |, we push it onto the stack as these characters indicate the beginning of an expression or a value.
    • If a character is a ), it means we have reached the end of an inner expression, so we begin to evaluate it.

  3. Evaluate the Expression:

    • We keep popping from the stack until we get t, f, or an operator. Here, we count how many t and f we have encountered which corresponds to the truth values.
    • Based on the operator before the sequence of t and f values (!, &, |), we apply the NOT, AND, or OR operation accordingly. For AND, the result is false if any f is found; for OR, the result is true if any t is found; for NOT, the result is true if f is found and vice versa.
    • The result of the inner expression (resulting t or f) is then pushed back onto the stack as the new 'value' for that subexpression.

  4. Result:

    • After evaluating the entire expression, the last element on the stack is the value of the whole expression. We check if it's equal to 't' to return True else it will be False.

This approach carefully constructs truth values by evaluating the smallest subexpressions first and combining them according to logical operations as specified by the nested structure of the parentheses and operators.

Learn more about Stack and Recursion patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Solution Approach

To decipher and evaluate the boolean expression provided in the problem statement, the solution leverages the use of a stack (stk) data structure to keep track of the components of the expression.

Here is how the implementation works:

  • Iterate through every character (c) in the string expression.
  • When encountering characters that are 't', 'f', '!', '&', or '|', they are pushed onto the stack (stk), as these signify values or operators.
  • If the character is a closing parenthesis ')', it indicates the end of a subexpression and triggers the evaluation sequence:
    • Initialize counters for true (t) and false (f) occurrences within the subexpression.
    • Pop characters from the stack until an operator is found, counting the t and f values found in the way.
    • Based on the popped operator, apply the logical NOT (!), AND (&), or OR (|) operation:
      • For !: Invert the boolean value, push 't' if there was an f in the subexpression, and 'f' if there was a t.
      • For &: If any f was found, the result of the AND operation is 'f', otherwise, it's 't'.
      • For |: If any t was found, the result of the OR operation is 't', otherwise, it's 'f'.
    • The result of this operation replaces the subexpression by being pushed onto the stack.
  • After the iteration is complete, the last character left in the stack is the result of the entire expression. Return True if this character is 't', otherwise return False.

A key algorithmic pattern used here is stack-based parsing, which is a common approach for handling nested expressions. Using a stack allows us to respect the precedence of the logical operations, dealing with the innermost expressions first before combining the results into higher-level expressions—essentially a form of bottom-up evaluation.

This pattern is effective because we process the expression linearly, maintaining only the information necessary for the current subexpression's evaluation. The stack implicitly handles the "waiting" operations, resuming them when their operands become available after inner expressions are evaluated.

In Python, the solution makes use of the match statement (available from Python 3.10), which provides a clean and readable way to perform actions based on the value of the operator. This increases the clarity of the code, especially when dealing with multiple conditions.

Overall, the combination of a simple stack along with a case-based action sequence allows the implementation to concisely and effectively evaluate the boolean expressions as required by the problem's specifications.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's consider a small example that illustrates the solution approach:

Given the expression: &(t,|(f,t),!(f))

Now, let's step through the process of evaluating it:

Step 1: Initialize Stack

Initially, our stack (stk) is empty.

Step 2: Start Iterating

  • We encounter '&' and push it onto stk: stack = ['&']
  • We encounter '(' and ignore it as it's not part of evaluation.
  • We encounter 't' and push it onto stk: stack = ['&', 't']
  • We encounter ',' (a delimiter between expression values) and ignore it.
  • We encounter '(' and ignore it.
  • We encounter '|' and push it onto stk: stack = ['&', 't', '|']
  • We encounter 'f' and push it onto stk: stack = ['&', 't', '|', 'f']
  • We encounter ',' and ignore it.
  • We encounter 't' and push it onto stk: stack = ['&', 't', '|', 'f', 't']
  • We encounter ')' and now we have to evaluate the subexpression with OR.

Step 3: Evaluate OR Subexpression

  • We start popping from stk until we hit the | operator: we get 't' and 'f' (we count 1 true and 1 false). Once we hit '|', we check for the | operation rules.
  • We found a 't' in our count, so the result of the OR subexpression is 't'. We push this result on stk: stack = ['&', 't', 't']
  • We encounter ',' and ignore it.
  • We encounter '!' and push it onto stk: stack = ['&', 't', 't', '!']
  • We encounter '(' and ignore it.
  • We encounter 'f' and push it onto stk: stack = ['&', 't', 't', '!', 'f']
  • We encounter ')' and now evaluate the NOT subexpression.

Step 4: Evaluate NOT Subexpression

  • We start by popping from stk and we find 'f'. Once we hit '!', we apply NOT on our f, which makes it a 't'. We push this 't' on stk: stack = ['&', 't', 't', 't']

At this point, we've evaluated all inner expressions and are left with the AND operation to perform on the remaining stack elements.

Step 5: Final Evaluation

  • We keep popping and find all ts, meaning that our AND operation will result in true. The top-level operator '&' ensures we check all values.
  • Once we've evaluated this final expression, our stack is now: stack = ['t'].

Step 6: Result

  • Our stack is left with a single element 't', which means our entire expression evaluates to True.

This step-by-step process demonstrates how the stack-based evaluation method effectively breaks down and solves the expression by evaluating inner subexpressions and progressively building up to the entire expression's value.

Solution Implementation

1class Solution:
2    def parseBoolExpr(self, expression: str) -> bool:
3        stack = []
4      
5        # Iterate through each character in the expression
6        for char in expression:
7            # If it's an operator or a boolean value, push it onto the stack
8            if char in 'tf!&|':
9                stack.append(char)
10            # When we encounter a closing parenthesis, we should evaluate the expression
11            elif char == ')':
12                true_count = false_count = 0
13              
14                # Count the number of true ('t') and false ('f') until we hit an operator
15                while stack[-1] in 'tf':
16                    true_count += stack[-1] == 't'
17                    false_count += stack[-1] == 'f'
18                    stack.pop() # Remove the boolean value as it's counted
19              
20                # Pop the operator from the stack and apply the logic for each operator
21                operator = stack.pop()
22                if operator == '!':
23                    # For not, result is true if we have a false, otherwise it's false
24                    result_char = 't' if false_count else 'f'
25                elif operator == '&':
26                    # For and, result is false if we have any false, otherwise it's true
27                    result_char = 'f' if false_count else 't'
28                elif operator == '|':
29                    # For or, result is true if we have any true, otherwise it's false
30                    result_char = 't' if true_count else 'f'
31              
32                # Push the result of the evaluation back onto the stack
33                stack.append(result_char)
34      
35        # At the end, the stack should only have one element which is the result
36        # Return True if the result is 't', otherwise False
37        return stack[0] == 't'
38
1class Solution {
2    public boolean parseBoolExpr(String expression) {
3        // Stack to hold characters representing boolean values and operators
4        Deque<Character> stack = new ArrayDeque<>();
5      
6        // Iterate through each character in the expression
7        for (char c : expression.toCharArray()) {
8            if (c != '(' && c != ')' && c != ',') {
9                // If the character is not a parenthesis or comma, push it onto the stack
10                stack.push(c);
11            } else if (c == ')') {
12                // When a closing parenthesis is encountered, evaluate the expression inside
13                int countTrue = 0; // Count of 't' (true) characters
14                int countFalse = 0; // Count of 'f' (false) characters
15              
16                // Pop characters from the stack until the corresponding operator is found
17                while (stack.peek() == 't' || stack.peek() == 'f') {
18                    if (stack.peek() == 't') {
19                        countTrue++;
20                    } else {
21                        countFalse++;
22                    }
23                    stack.pop();
24                }
25              
26                // Pop the operator ('!', '&', or '|')
27                char operator = stack.pop();
28              
29                // Evaluate the expression based on the operator
30                if (operator == '!' && countFalse > 0) {
31                    // For '!', the expression is true if it has any 'f' (since '!' is a negation)
32                    c = 't';
33                } else if (operator == '&' && countFalse == 0) {
34                    // For '&', the expression is true if all are 't'
35                    c = 't';
36                } else if (operator == '|' && countTrue > 0) {
37                    // For '|', the expression is true if at least one is 't'
38                    c = 't';
39                } else {
40                    // In all other cases, the expression is false
41                    c = 'f';
42                }
43              
44                // Push the result of the evaluated expression back onto the stack
45                stack.push(c);
46            }
47        }
48        // The result of the entire expression is at the top of the stack
49        // Return true if the top of the stack is 't', otherwise false
50        return stack.peek() == 't';
51    }
52}
53
1class Solution {
2public:
3    // Function to evaluate the boolean expression.
4    bool parseBoolExpr(string expression) {
5        stack<char> charStack; // Create a stack to manage the characters.
6
7        // Iterating over each character in the input expression.
8        for (char c : expression) {
9            // If the character is not an operator or a comma, push it onto the stack.
10            if (c != '(' && c != ')' && c != ',') {
11                charStack.push(c);
12            } else if (c == ')') { // When a closing bracket is encountered, evaluate the expression inside it.
13                int trueCount = 0, falseCount = 0; // Variables to count the number of true and false values.
14
15                // Process all operands up to the previous operator.
16                while (charStack.top() == 't' || charStack.top() == 'f') {
17                    // Increment trueCount or falseCount based on the operand.
18                    trueCount += charStack.top() == 't';
19                    falseCount += charStack.top() == 'f';
20                    charStack.pop(); // Remove the processed operand from the stack.
21                }
22
23                // Now, pop the operator from the stack.
24                char operatorChar = charStack.top();
25                charStack.pop();
26
27                // Evaluate the expression based on the operator.
28                if (operatorChar == '!') {
29                    c = falseCount > 0 ? 't' : 'f'; // Logical NOT: 'true' if any is 'false', else 'false'.
30                }
31                if (operatorChar == '&') {
32                    c = falseCount > 0 ? 'f' : 't'; // Logical AND: 'false' if any is 'false', else 'true'.
33                }
34                if (operatorChar == '|') {
35                    c = trueCount > 0 ? 't' : 'f'; // Logical OR: 'true' if any is 'true', else 'false'.
36                }
37
38                // Push the result onto the stack.
39                charStack.push(c);
40            }
41        }
42
43        // The top of the stack now contains the result, return 'true' if 't', 'false' otherwise.
44        return charStack.top() == 't';
45    }
46};
47
1// Parses the given boolean expression and returns the result.
2// Supported operators: '!', '&', and '|'
3// Operands can be 't' (true) or 'f' (false)
4// Expression examples: "|(f,t)", "&(t,f)", "!(t)", "&(!(&(t,f,t)),|(f,t))"
5// Each expression is guaranteed to be valid and only consist of these characters.
6function parseBoolExpr(expression: string): boolean {
7    // The current index pointer used while scanning through the expression
8    let currentIndex = 0;
9    // The length of the expression
10    const expressionLength = expression.length;
11
12    // Recursive function to evaluate the expression
13    const evaluate = (): boolean[] => {
14        let resultStack: boolean[] = [];
15        while (currentIndex < expressionLength) {
16            const currentChar = expression[currentIndex++];
17          
18            if (currentChar === ')') {
19                // End of the current expression
20                break;
21            }
22          
23            if (currentChar === '!') {
24                // Not operation: Flip the boolean value of the next expression
25                resultStack.push(!evaluate()[0]);
26            } else if (currentChar === '|') {
27                // Or operation: Return true if any of the values in the next expression is true
28                resultStack.push(evaluate().some(value => value));
29            } else if (currentChar === '&') {
30                // And operation: Return true only if all values in the next expression are true
31                resultStack.push(evaluate().every(value => value));
32            } else if (currentChar === 't') {
33                // Literal 'true' value
34                resultStack.push(true);
35            } else if (currentChar === 'f') {
36                // Literal 'false' value
37                resultStack.push(false);
38            }
39        }
40        return resultStack;
41    };
42  
43    // Start evaluating the expression and return the result of the top-level expression
44    return evaluate()[0];
45}
46
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the expression string. This is because the code iterates over each character in the input string exactly once. During the iteration, each character is processed in a way that takes constant time. Operations like pushing to and popping from the stack, comparing characters, and assigning values all occur in O(1) time.

The space complexity of the code is also O(n). This is due to the use of a stack that, in the worst case, might need to store an element for every character in the expression string before any reduction happens. The case that would result in this space usage is one where the string contains a long series of open parentheses before reaching any operator or closed parenthesis.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫