Parsing A Boolean Expression - Video Solutions

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.