Given a string expression representing a boolean expression, evaluate and return the result of the expression. The expression consists of the following symbols:
't' for True'f' for False'!' for logical NOT'&' for logical AND'|' for logical OR'(' and ')' to denote precedence',' to separate arguments for operators
The input expression is always a valid boolean expression containing only the above characters. You are to parse and evaluate the expression, returning True or False accordingly.
Constraints:
!, &, and | may be nested.At first glance, the problem is about parsing and evaluating a custom boolean expression syntax. The challenge is to handle nested operations and correct operator precedence, similar to evaluating mathematical expressions with nested parentheses.
A brute-force approach might involve repeatedly searching for innermost parentheses and evaluating them, but this quickly becomes cumbersome as nesting increases. Instead, we want a systematic way to process the expression, especially since the operators may take multiple arguments (not just binary), and the nesting can be arbitrary.
A stack-based approach is a natural fit for this problem. Each time we encounter an opening parenthesis, we can push context onto a stack. When we find a closing parenthesis, we can pop from the stack and evaluate the corresponding sub-expression. This is similar to how expression evaluation is done in compilers or calculators.
To evaluate the boolean expression, we will use a stack to simulate the recursive structure of the expression. Here's a step-by-step plan:
't' or 'f'), push it onto the stack.'!', '&', '|'), push it onto the stack.'(' or a comma ',', push it onto the stack (or skip the comma).')', pop elements from the stack until the corresponding operator is found, then evaluate the sub-expression.'t' or 'f') back onto the stack.
This approach ensures that innermost expressions are evaluated first, handling operator precedence and nesting naturally.
Let's consider the input expression = "&(t,|(f,!(&(f)),t))".
'&': push to stack.'(': push to stack.'t': push to stack.',': skip.'|': push to stack.'(': push to stack.'f': push to stack.',': skip.'!': push to stack.'(': push to stack.'&': push to stack.'(': push to stack.'f': push to stack.')': pop 'f', apply & (result 'f'), push result.')': pop 'f', apply ! (result 't'), push result.')': pop 'f' and 't', apply | (result 't'), push result.',': skip.'t': push to stack.')': pop 't' and 't', apply & (result 't'), push result.
The final result is 't', which corresponds to True.
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
stack = []
for ch in expression:
if ch == ',':
continue
elif ch != ')':
stack.append(ch)
else:
vals = []
while stack[-1] != '(':
vals.append(stack.pop())
stack.pop() # remove '('
op = stack.pop()
if op == '!':
stack.append('t' if vals[0] == 'f' else 'f')
elif op == '&':
stack.append('t' if all(v == 't' for v in vals) else 'f')
elif op == '|':
stack.append('t' if any(v == 't' for v in vals) else 'f')
return stack[-1] == 't'
class Solution {
public:
bool parseBoolExpr(string expression) {
stack<char> stk;
for (char ch : expression) {
if (ch == ',') continue;
else if (ch != ')') stk.push(ch);
else {
vector<char> vals;
while (stk.top() != '(') {
vals.push_back(stk.top());
stk.pop();
}
stk.pop(); // remove '('
char op = stk.top(); stk.pop();
if (op == '!') {
stk.push(vals[0] == 'f' ? 't' : 'f');
} else if (op == '&') {
bool allTrue = true;
for (char v : vals) if (v != 't') allTrue = false;
stk.push(allTrue ? 't' : 'f');
} else if (op == '|') {
bool anyTrue = false;
for (char v : vals) if (v == 't') anyTrue = true;
stk.push(anyTrue ? 't' : 'f');
}
}
}
return stk.top() == 't';
}
};
class Solution {
public boolean parseBoolExpr(String expression) {
Deque<Character> stack = new ArrayDeque<>();
for (char ch : expression.toCharArray()) {
if (ch == ',') continue;
else if (ch != ')') stack.push(ch);
else {
List<Character> vals = new ArrayList<>();
while (stack.peek() != '(') {
vals.add(stack.pop());
}
stack.pop(); // remove '('
char op = stack.pop();
if (op == '!') {
stack.push(vals.get(0) == 'f' ? 't' : 'f');
} else if (op == '&') {
boolean allTrue = true;
for (char v : vals) if (v != 't') allTrue = false;
stack.push(allTrue ? 't' : 'f');
} else if (op == '|') {
boolean anyTrue = false;
for (char v : vals) if (v == 't') anyTrue = true;
stack.push(anyTrue ? 't' : 'f');
}
}
}
return stack.peek() == 't';
}
}
var parseBoolExpr = function(expression) {
let stack = [];
for (let ch of expression) {
if (ch === ',') continue;
else if (ch !== ')') stack.push(ch);
else {
let vals = [];
while (stack[stack.length - 1] !== '(')
vals.push(stack.pop());
stack.pop(); // remove '('
let op = stack.pop();
if (op === '!') {
stack.push(vals[0] === 'f' ? 't' : 'f');
} else if (op === '&') {
stack.push(vals.every(v => v === 't') ? 't' : 'f');
} else if (op === '|') {
stack.push(vals.some(v => v === 't') ? 't' : 'f');
}
}
}
return stack[stack.length - 1] === 't';
};
Brute-force Approach: If we tried to recursively search for innermost parentheses and evaluate them by string manipulation, each evaluation could be O(n), and with up to O(n) nested levels, the worst-case time could be O(n^2).
Optimized Stack-based Approach: Each character in the expression is processed once, and each is pushed/popped from the stack at most once. Thus, the time complexity is O(n), where n is the length of the expression. The space complexity is also O(n) in the worst case, due to the stack storing up to n elements for deeply nested expressions.
By using a stack to evaluate the boolean expression, we efficiently handle arbitrary levels of nesting and multiple-argument operators. This approach mimics the recursive structure of the expression and ensures that each sub-expression is evaluated in the correct order. The solution is both elegant and efficient, with linear time and space complexity relative to the length of the input.