Parsing A Boolean Expression
Problem
A boolean expression is built from 't' (true), 'f' (false), '!(expr)' (logical NOT), '&(expr1,expr2,...)' (logical AND of one or more sub-expressions) and '|(expr1,expr2,...)' (logical OR of one or more sub-expressions). Evaluate the expression and return its boolean value.
expression = "|(f,&(t,f))"false&(t,f) is false, so the outer becomes |(f,false) = false.def parseBoolExpr(expression):
stack = []
for ch in expression:
if ch == ',':
continue
if ch != ')':
stack.append(ch) # 't','f','!','&','|','('
continue
vals = [] # collect operands until '('
while stack[-1] != '(':
vals.append(stack.pop())
stack.pop() # remove '('
op = stack.pop() # the operator
if op == '!':
res = 'f' if vals[0] == 't' else 't'
elif op == '&':
res = 't' if all(v == 't' for v in vals) else 'f'
else: # op == '|'
res = 't' if any(v == 't' for v in vals) else 'f'
stack.append(res)
return stack[-1] == 't'function parseBoolExpr(expression) {
const stack = [];
for (const ch of expression) {
if (ch === ',') continue;
if (ch !== ')') { stack.push(ch); continue; }
const vals = [];
while (stack[stack.length - 1] !== '(') vals.push(stack.pop());
stack.pop(); // remove '('
const op = stack.pop(); // the operator
let res;
if (op === '!') res = vals[0] === 't' ? 'f' : 't';
else if (op === '&') res = vals.every(v => v === 't') ? 't' : 'f';
else res = vals.some(v => v === 't') ? 't' : 'f';
stack.push(res);
}
return stack[stack.length - 1] === 't';
}class Solution {
public boolean parseBoolExpr(String expression) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : expression.toCharArray()) {
if (ch == ',') continue;
if (ch != ')') { stack.push(ch); continue; }
List<Character> vals = new ArrayList<>();
while (stack.peek() != '(') vals.add(stack.pop());
stack.pop(); // remove '('
char op = stack.pop(); // the operator
char res;
if (op == '!') res = vals.get(0) == 't' ? 'f' : 't';
else if (op == '&') {
res = 't';
for (char v : vals) if (v == 'f') res = 'f';
} else {
res = 'f';
for (char v : vals) if (v == 't') res = 't';
}
stack.push(res);
}
return stack.peek() == 't';
}
}bool parseBoolExpr(string expression) {
vector<char> stack;
for (char ch : expression) {
if (ch == ',') continue;
if (ch != ')') { stack.push_back(ch); continue; }
vector<char> vals;
while (stack.back() != '(') { vals.push_back(stack.back()); stack.pop_back(); }
stack.pop_back(); // remove '('
char op = stack.back(); stack.pop_back();
char res;
if (op == '!') res = vals[0] == 't' ? 'f' : 't';
else if (op == '&') {
res = 't';
for (char v : vals) if (v == 'f') res = 'f';
} else {
res = 'f';
for (char v : vals) if (v == 't') res = 't';
}
stack.push_back(res);
}
return stack.back() == 't';
}Explanation
The expression nests operators inside parentheses, and a stack lets us evaluate each group the moment it closes. We push every character as we scan, and a closing ) triggers us to fold the most recent group into a single result.
We scan left to right. Commas are separators, so we skip them. Any other character that is not ) — a value t/f, an operator !/&/|, or an open ( — is simply pushed onto the stack.
When we hit ), we pop operands until we reach the matching (, then pop that ( and the operator sitting beneath it. We apply the operator: ! flips its single operand, & is t only if all operands are t, and | is t if any is t. The single resulting t or f is pushed back.
Example: "|(f,&(t,f))". The inner &(t,f) closes first, folding to f. The outer group is then effectively |(f,f), which folds to f, so the final answer is false.
It works because every ) always resolves the innermost unfinished group first, replacing it with its boolean value, so by the end exactly one value — the answer — remains on the stack.