Skip to main content
Talentd

Parsing A Boolean Expression - Solution & Explanation

HardStringStackRecursion15 min readAsked at: Amazon, Microsoft, Goldman Sachs +5
Practice this problem

Problem Statement

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
  • 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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaC++

Java

C++

Complexity

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.

Try this approach in the editor →

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 c is one of "tf!&|", we push it directly onto the stack;
  • If 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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Parsing Approach

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.

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.
Space Complexity: O(N), due to the stack use which can grow to store the entire expression temporarily during evaluation.

Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive ParsingO(n)O(n)When implementing a natural expression-tree style evaluator using recursion
Stack-Based IterativeO(n)O(n)Preferred for interviews and production when avoiding recursion depth issues

Video Solution

Parsing A Boolean Expression | Cleanest Explanation | Dry Run | LeetCode 1106 | codestorywithMIK • codestorywithMIK • 11,809 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Parsing A Boolean Expression with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring