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'(', ')', '&', '|', '!', 't', 'f', and ','.This approach uses a recursive function to parse and evaluate the boolean expression. We define base and recursive cases for handling 't', 'f', NOT, AND, and OR operations. The main idea is to evaluate each sub-expression independently and combine the results when necessary.
The function parse_bool_expr starts by defining a helper function that iterates over the expression. It handles constants 't' and 'f' directly and recursively processes expressions by recognizing operation types (!, &, |). It evaluates them using respective Python operations and accumulates results.
JavaScript
Time Complexity: O(N), where N is the length of the expression, as each character is processed once.
Space Complexity: O(N), due to recursion stack space and the results list which stores intermediate results.
In this approach, we use a stack to simulate the recursive evaluation of the expression. As we traverse through the string, operations and operands are pushed onto the stack. When we encounter a closing parenthesis, we pop from the stack until we reach an opening parenthesis, evaluate the expression, and push the result back onto the stack.
This Java solution uses a stack to evaluate the expression iteratively. As we traverse, each character is handled based on whether it is an operator, opening bracket, or closing bracket. Upon encountering a ')' we pop and evaluate the enclosed expression.
C++
Time Complexity: O(N), where N is the length of the expression, as processing each character is done in constant time.
Space Complexity: O(N), due to the stack use which can grow to store the entire expression temporarily during evaluation.
| Approach | Complexity |
|---|---|
| Recursive Parsing Approach | Time Complexity: O(N), where N is the length of the expression, as each character is processed once. |
| Stack-Based Iterative Approach | Time Complexity: O(N), where N is the length of the expression, as processing each character is done in constant time. |
Parsing A Boolean Expression - Leetcode 1106 - Python • NeetCodeIO • 8,432 views views
Watch 9 more video solutions →Practice Parsing A Boolean Expression with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor