Parsing A Boolean Expression — Problem & Solution
Parsing A Boolean Expression solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Parsing A Boolean Expression is a hard coding problem on strings, stack and recursion, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Strings, Stack, Recursion
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A CodeKairo feature flag is written as a boolean expression in a tiny prefix language. An expression is one of:
t— true;f— false;!(e)— the logical NOT of the inner expressione;&(e1,e2,...,ek)— the logical AND of one or more inner expressions;|(e1,e2,...,ek)— the logical OR of one or more inner expressions.
Given a valid expression, return what it evaluates to.
Example 1
Input: expression = "|(&(t,f,t),!(f))"
Output: true
Explanation: `&(t,f,t)` is false and `!(f)` is true, so the OR is true.
Example 2
Input: expression = "&(|(f,t),!(t))"
Output: false
Example 3
Input: expression = "|(f)"
Output: false
Constraints
1 <= expression.length <= 2 * 10^4expression[i] is one of '(', ')', '&', '|', '!', 't', 'f' and ','expression is a valid expression as defined above
Hints for Parsing A Boolean Expression
Hint 1
An operator's value is only known once its closing
)is reached — that suggests a stack.Hint 2
Push every character except commas. On
), pop values until the matching(, counting how many weretand how manyf.Hint 3
Then pop the
(and the operator below it:!gives true iff the single value wasf,&gives true iff nofwas seen,|gives true iff sometwas seen. Push the result ast/f.
How to solve Parsing A Boolean Expression
Evaluate bottom-up with one stack: by the time a ) arrives, all of its operands have already been reduced to single t/f characters sitting above its (.
Approach
- Scan the expression; skip commas and push every other character except
). - On
): pop characters until the top is(, counting thets andfs popped. - Pop the
(and then the operator. - Compute the result —
!: true iff the operand wasf;&: true iff thef-count is 0;|: true iff thet-count is positive — and push it astorf. - When the scan ends, the stack holds one character; return whether it is
t.
Why it works
Each ) closes the innermost open operator, and every operand of that operator is either a literal or an inner expression whose own ) came earlier and was already replaced by its value. So the popped run is exactly the operator's list of operand values. AND and OR only need to know whether a false or a true value is present, which the counts provide.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Forgetting to skip commas mixes them into the operand counts.
- An operator can have a single operand (
|(f),&(t)); the counting rule handles it without special cases. - A recursive parser works too, but a 2 * 10^4-character expression can nest deeply — the explicit stack avoids recursion limits.
Reference solution
Python
def parseBoolExpr(expression: str) -> bool:
st = []
for c in expression:
if c == ",":
continue
if c != ")":
st.append(c)
continue
t = f = 0
while st[-1] != "(":
if st.pop() == "t":
t += 1
else:
f += 1
st.pop()
op = st.pop()
if op == "!":
r = f > 0
elif op == "&":
r = f == 0
else:
r = t > 0
st.append("t" if r else "f")
return st[-1] == "t"Java
public static boolean parseBoolExpr(String expression) {
char[] st = new char[expression.length() + 1];
int top = 0;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == ',') continue;
if (c != ')') {
st[top++] = c;
continue;
}
int t = 0, f = 0;
while (st[top - 1] != '(') {
if (st[--top] == 't') t++;
else f++;
}
top--;
char op = st[--top];
boolean r = op == '!' ? f > 0 : op == '&' ? f == 0 : t > 0;
st[top++] = r ? 't' : 'f';
}
return st[top - 1] == 't';
}C++
bool parseBoolExpr(string expression) {
vector<char> st;
for (char c : expression) {
if (c == ',') continue;
if (c != ')') {
st.push_back(c);
continue;
}
int t = 0, f = 0;
while (st.back() != '(') {
if (st.back() == 't') t++;
else f++;
st.pop_back();
}
st.pop_back();
char op = st.back();
st.pop_back();
bool r = op == '!' ? f > 0 : op == '&' ? f == 0 : t > 0;
st.push_back(r ? 't' : 'f');
}
return st.back() == 't';
}JavaScript
var parseBoolExpr = function(expression) {
var st = [];
for (var i = 0; i < expression.length; i++) {
var c = expression[i];
if (c === ",") continue;
if (c !== ")") {
st.push(c);
continue;
}
var t = 0, f = 0;
while (st[st.length - 1] !== "(") {
if (st.pop() === "t") t++;
else f++;
}
st.pop();
var op = st.pop();
var r = op === "!" ? f > 0 : op === "&" ? f === 0 : t > 0;
st.push(r ? "t" : "f");
}
return st[st.length - 1] === "t";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure