Sponsored
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.
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.
1def parse_bool_expr(expression: str) -> bool:
2 def helper(index: int) -> (bool, int):
3 if expression[index] == 't':
4 return True, index + 1
5 elif expression[index] == 'f':
6 return False, index + 1
7 op = expression[index]
8 index += 2 # Skip the operator and the opening bracket
9 results = []
10 while expression[index] != ')':
11 result, index = helper(index)
12 results.append(result)
13 if expression[index] == ',': # Move past commas
14 index += 1
15 index += 1 # Skip the closing bracket
16
17 if op == '!':
18 return not results[0], index
19 elif op == '&':
20 return all(results), index
21 elif op == '|':
22 return any(results), index
23 return False, index
24
25 result, _ = helper(0)
26 return result
27The 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.
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.
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.
1#include <stack>
2using namespace std;
3
4class Solution {
5public:
bool parseBoolExpr(string expression) {
stack<char> stack;
for (char& c : expression) {
if (c == ',') continue;
if (c != ')') {
stack.push(c);
} else {
int countT = 0, countF = 0;
while (stack.top() != '(') {
char top = stack.top(); stack.pop();
if (top == 't') countT++;
if (top == 'f') countF++;
}
stack.pop();
char op = stack.top(); stack.pop();
if (op == '!') stack.push(countF == 1 ? 't' : 'f');
else if (op == '&') stack.push(countF > 0 ? 'f' : 't');
else if (op == '|') stack.push(countT > 0 ? 't' : 'f');
}
}
return stack.top() == 't';
}
};In this C++ solution, we use a stack to process the expression iteratively. Upon encountering a closing parenthesis, we pop the stack to evaluate the enclosed boolean expression. This avoids recursion and still respects the logic of nested expressions.