Parsing A Boolean Expression solution and explanation
Google
9 more videos on this problem
Parsing A Boolean Expression | Cleanest Explanation | Dry Run | LeetCode 1106 | codestorywithMIKcodestorywithMIK · 19:16 · 11K views
Parsing A Boolean Expression - Leetcode 1106 - PythonNeetCodeIO · 25:43 · 9K views
LeetCode 1106 Parsing A Boolean Expressionleetuition · 18:04 · 4K views
Parsing A Boolean Expression | Leetcode 1106Techdose · 11:51 · 2K views
LeetCode 1106. Parsing A Boolean Expression Explanation and Solutionhappygirlzt · 10:38 · 2K views
PARSING A BOOLEAN EXPRESSION | LEETCODE 1106 | PYTHON STACK SOLUTIONCracking FAANG · 12:23 · 666 views
LeetCode 1106: Parsing A Boolean Expression | Optimal Stack Solution | Top Interview ProblemShamp Coding · 21:06 · 97 views
Parsing A Boolean Expression | Leetcode 1106 | Stacks | Java Code | Developer CoderDeveloper Coder · 28:46 · 76 views
Leetcode#42. 1106. Parsing A Boolean Expression. Daily 20th October.Sultanov · 13:16 · 63 views
Parsing a boolean Expression | Detailed Approach | Leetcode 1106 | 10mintuesCS10 Minutes CS · 16:14 · 52 views
The problem
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 totrue.'f'that evaluates tofalse.'!(subExpr)'that evaluates to the logical NOT of the inner expressionsubExpr.'&(subExpr1, subExpr2, ..., subExprn)'that evaluates to the logical AND of the inner expressionssubExpr1, subExpr2, ..., subExprnwheren >= 1.'|(subExpr1, subExpr2, ..., subExprn)'that evaluates to the logical OR of the inner expressionssubExpr1, subExpr2, ..., subExprnwheren >= 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- expression[i] is one following characters:
'(',')','&','|','!','t','f', and','.
Approach overview
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.
Approach 1: Recursive Parsing Approach
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.
def parse_bool_expr(expression: str) -> bool:
def helper(index: int) -> (bool, int):
if expression[index] == 't':
return True, index + 1
elif expression[index] == 'f':
return False, index + 1
op = expression[index]
index += 2 # Skip the operator and the opening bracket
results = []
while expression[index] != ')':
result, index = helper(index)
results.append(result)
if expression[index] == ',': # Move past commas
index += 1
index += 1 # Skip the closing bracket
if op == '!':
return not results[0], index
elif op == '&':
return all(results), index
elif op == '|':
return any(results), index
return False, index
result, _ = helper(0)
return resultfunction parseBoolExpr(expression) {
const evalExpr = (str, start) => {
if (str[start] === 't') return [true, start + 1];
if (str[start] === 'f') return [false, start + 1];
let op = str[start];
start += 2; // Skip operator and opening bracket
let results = [];
while (str[start] !== ')') {
const [res, newStart] = evalExpr(str, start);
results.push(res);
start = newStart;
if (str[start] === ',') start++;
}
start++; // to skip the closing bracket
if (op === '!') return [!results[0], start];
if (op === '&') return [results.every(Boolean), start];
if (op === '|') return [results.some(Boolean), start];
};
return evalExpr(expression, 0)[0];
}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.
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.
Approach 2: Stack-Based Iterative Approach
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.
import java.util.Stack;
public class Solution {
public boolean parseBoolExpr(String expression) {
Stack<Character> stack = new Stack<>();
for (char c : expression.toCharArray()) {
if (c == ',') continue;
if (c != ')') {
stack.push(c);
} else {
int countT = 0, countF = 0;
while (stack.peek() != '(') {
char top = stack.pop();
if (top == 't') countT++;
if (top == 'f') countF++;
}
stack.pop(); // remove '(';
char op = stack.pop();
if (op == '!') stack.push(countF == 1 ? 't' : 'f');
else if (op == '&') stack.push(countF > 0 ? 'f' : 't');
else if (op == '|') stack.push(countT > 0 ? 't' : 'f');
}
}
return stack.pop() == 't';
}
}#include <stack>
using namespace std;
class Solution {
public:
bool parseBoolExpr(string expression) {
stack<char> stack;
for (char& c : expression) {
if (c == ',') continue;
if (c != ')') {
stack.push(c);
} else {
int countT = 0, countF = 0;
while (stack.top() != '(') {
char top = stack.top(); stack.pop();
if (top == 't') countT++;
if (top == 'f') countF++;
}
stack.pop();
char op = stack.top(); stack.pop();
if (op == '!') stack.push(countF == 1 ? 't' : 'f');
else if (op == '&') stack.push(countF > 0 ? 'f' : 't');
else if (op == '|') stack.push(countT > 0 ? 't' : 'f');
}
}
return stack.top() == 't';
}
};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.
Approach 3: Stack
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:
- If
cis one of"tf!&|", we push it directly onto the stack; - If
cis a right parenthesis')', we pop elements from the stack until we encounter an operator'!','&', or'|'. During this process, we use variablestandfto 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.
function parseBoolExpr(expression: string): boolean {
const expr = expression;
const n = expr.length;
let i = 0;
const dfs = () => {
let res: boolean[] = [];
while (i < n) {
const c = expr[i++];
if (c === ')') {
break;
}
if (c === '!') {
res.push(!dfs()[0]);
} else if (c === '|') {
res.push(dfs().some(v => v));
} else if (c === '&') {
res.push(dfs().every(v => v));
} else if (c === 't') {
res.push(true);
} else if (c === 'f') {
res.push(false);
}
}
return res;
};
return dfs()[0];
}func parseBoolExpr(expression string) bool {
stk := []rune{}
for _, c := range expression {
if c != '(' && c != ')' && c != ',' {
stk = append(stk, c)
} else if c == ')' {
var t, f int
for stk[len(stk)-1] == 't' || stk[len(stk)-1] == 'f' {
if stk[len(stk)-1] == 't' {
t++
} else {
f++
}
stk = stk[:len(stk)-1]
}
op := stk[len(stk)-1]
stk = stk[:len(stk)-1]
c = 'f'
if (op == '!' && f > 0) || (op == '&' && f == 0) || (op == '|' && t > 0) {
c = 't'
}
stk = append(stk, c)
}
}
return stk[0] == 't'
}impl Solution {
fn dfs(i: &mut usize, expr: &[u8]) -> Vec<bool> {
let n = expr.len();
let mut res = Vec::new();
while *i < n {
let c = expr[*i];
*i += 1;
match c {
b')' => {
break;
}
b't' => {
res.push(true);
}
b'f' => {
res.push(false);
}
b'!' => {
res.push(!Self::dfs(i, expr)[0]);
}
b'&' => {
res.push(Self::dfs(i, expr).iter().all(|v| *v));
}
b'|' => {
res.push(Self::dfs(i, expr).iter().any(|v| *v));
}
_ => {}
}
}
res
}
pub fn parse_bool_expr(expression: String) -> bool {
let expr = expression.as_bytes();
let mut i = 0;
Self::dfs(&mut i, expr)[0]
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Parsing A Boolean Expression easy or hard?
Parsing A Boolean Expression is classified as a Hard problem on LeetCode. The difficulty comes from handling nested operators and parentheses correctly while maintaining linear complexity.
Parsing A Boolean Expression Python/Java solution
Python and JavaScript solutions often use recursive parsing because the syntax is concise for handling nested expressions. Java and C++ implementations commonly use an explicit stack to iteratively evaluate subexpressions while maintaining O(n) time complexity.
How to solve Parsing A Boolean Expression in O(n)?
Scan the string and evaluate subexpressions when encountering a closing parenthesis. Use a stack to collect operands until the operator for that group is reached, then compute the result and push it back. Because each character participates in constant work, the total complexity remains O(n).
What is the best approach for Parsing A Boolean Expression?
The stack-based iterative approach is typically the best solution. It processes the expression from left to right, pushing tokens onto a stack and evaluating subexpressions when a closing parenthesis appears. Each character is handled once, resulting in O(n) time and O(n) space complexity.
Is Parsing A Boolean Expression asked at Google/Amazon/Meta?
Expression parsing problems appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. Variations often test stack usage, recursion, and the ability to evaluate nested expressions efficiently.
What data structure is used in Parsing A Boolean Expression?
A stack is the primary data structure used in the iterative solution. It tracks operands and operators while parsing nested parentheses. Recursive solutions implicitly use the call stack to evaluate each subexpression.
What is the time complexity of Parsing A Boolean Expression?
Both the recursive parsing and stack-based solutions run in O(n) time where n is the length of the expression. Each character is visited once and every operand is pushed and popped at most one time during evaluation.