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 ','.Problem Overview: You are given a boolean expression containing t, f, and operators ! (NOT), & (AND), and | (OR). The goal is to evaluate the expression and return its boolean result. Parentheses define operator scope, so you must correctly parse nested expressions.
Approach 1: Recursive Parsing (O(n) time, O(n) space)
This approach treats the expression like a recursive grammar. Each operator consumes a subexpression inside parentheses, and the evaluation happens by recursively parsing those segments. You iterate through the string, and when an operator such as !, &, or | appears, recursively evaluate the values inside its parentheses. The recursion naturally handles nested structures, making it a clean way to interpret the expression tree. Time complexity is O(n) because each character is processed once, while recursion depth and call stack usage lead to O(n) space in the worst case. This approach closely mirrors how expression evaluators work in compilers.
Recursive parsing fits well when you want code that directly reflects the structure of the expression. If you're comfortable with recursive descent techniques and tree-like evaluation, this method is straightforward to reason about. It heavily relies on concepts from recursion and string parsing.
Approach 2: Stack-Based Iterative Approach (O(n) time, O(n) space)
The stack-based method evaluates the expression iteratively while scanning the string. Push characters onto a stack until you encounter a closing parenthesis ). At that point, pop elements until reaching the corresponding operator. Count how many t and f values appear in that segment, then compute the result depending on the operator: ! flips the value, & returns true only if all operands are true, and | returns true if at least one operand is true. Push the computed result back onto the stack and continue scanning.
This method avoids recursion entirely and instead uses a classic expression evaluation pattern built on a stack. Every character is pushed and popped at most once, giving O(n) time complexity. The stack can hold up to O(n) elements in deeply nested expressions. Since the algorithm processes the string sequentially, it works well in languages where recursion depth might be limited.
The core insight is that parentheses define evaluation boundaries. As soon as a closing parenthesis appears, you have enough information to compute that subexpression immediately. This makes the stack a natural fit for parsing problems involving nested structures in string expressions.
Recommended for interviews: The stack-based iterative approach is usually preferred. It demonstrates strong understanding of expression parsing and stack mechanics while maintaining linear O(n) performance. The recursive solution is also valid and often easier to implement quickly, but interviewers typically expect candidates to recognize that stacks naturally model nested parentheses evaluation.
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.
Python
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.
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.
For this type of expression parsing problem, we can use a stack to assist.
We traverse the expression expression from left to right. For each character c we encounter:
c is one of "tf!&|", we push it directly onto the stack;c is a right parenthesis ')', we pop elements from the stack until we encounter an operator '!', '&', or '|'. During this process, we use variables t and f to record the number of 't' and 'f' characters popped from the stack. Finally, based on the number of characters popped and the operator, we calculate a new character 't' or 'f' and push it onto the stack.After traversing the expression expression, there is only one character left in the stack. If it is 't', return true, otherwise return false.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the expression expression.
| 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. |
| Stack | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Parsing | O(n) | O(n) | When implementing a natural expression-tree style evaluator using recursion |
| Stack-Based Iterative | O(n) | O(n) | Preferred for interviews and production when avoiding recursion depth issues |
Parsing A Boolean Expression | Cleanest Explanation | Dry Run | Leetcode 1106 | codestorywithMIK • codestorywithMIK • 10,742 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