Parsing A Boolean Expression
Hard · Stack & Strings · String · Stack · Recursion
Problem
You are given a string expression that describes a boolean expression in one of these forms:
- 't' is true and 'f' is false;
- '!(e)' is the logical NOT of the inner expression e;
- '&(e1,e2,...,en)' is the logical AND of one or more inner expressions;
- '|(e1,e2,...,en)' is the logical OR of one or more inner expressions.
The expression is always valid. Evaluate it and return the result as a boolean.
Examples
Input: expression = "&(t,|(f,t),!(t))" Output: false
The parts evaluate to t, t and f, and an AND with any false part is false.
Input: expression = "|(f,!(f))" Output: true
!(f) is true, so the OR is true.
Input: expression = "&(t,!(f),t)" Output: true
All three parts are true.
Constraints
- 1 <= len(expression) <= 2 · 10^4
- expression[i] is one of '(', ')', '&', '|', '!', 't', 'f' and ','
- expression is a valid expression following the rules above
Approaches
- Rewrite the innermost group until one letter is left — time O(n²), space O(n)
Follow-up
A recursive-descent parser (one function that reads an expression and returns its value and where it ended) is the most natural way to write this, but nesting can be about 5,000 levels deep here, past Python's default recursion limit. The explicit stack has no such limit. Could you also short-circuit, skipping the rest of an AND as soon as you see an f? Only by skipping to the matching ), which still means reading those characters.
Related problems
Start free on Cariara · Coding problems · System design studio
