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.
1function parseBoolExpr(expression) {
2 const evalExpr = (str, start) => {
3 if (str[start] === 't') return [true, start + 1];
4 if (str[start] === 'f') return [false, start + 1];
5
6 let op = str[start];
7 start += 2; // Skip operator and opening bracket
8 let results = [];
9
10 while (str[start] !== ')') {
11 const [res, newStart] = evalExpr(str, start);
12 results.push(res);
13 start = newStart;
14
15 if (str[start] === ',') start++;
16 }
17 start++; // to skip the closing bracket
18
19 if (op === '!') return [!results[0], start];
20 if (op === '&') return [results.every(Boolean), start];
21 if (op === '|') return [results.some(Boolean), start];
22 };
23 return evalExpr(expression, 0)[0];
24}The JavaScript solution uses a recursive function evalExpr to process the expression. It handles constants directly and recursively evaluates AND, OR, and NOT expressions. The function returns both the result of the expression and the new index to continue parsing from.
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.
1import java.util.Stack;
2
This Java solution uses a stack to evaluate the expression iteratively. As we traverse, each character is handled based on whether it is an operator, opening bracket, or closing bracket. Upon encountering a ')' we pop and evaluate the enclosed expression.