Problem

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:

  • 't' that evaluates to true.
  • 'f' that evaluates to false.
  • '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr.
  • '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.
  • '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1.

Given a string expression that represents a boolean expression, return the evaluation of that expression.

It is guaranteed that the given expression is valid and follows the given rules.

Examples

Example 1

1
2
3
4
5
6

Input: expression = "&(|(f))"
Output: false
Explanation: 
First, evaluate |(f) --> f. The expression is now "&(f)".
Then, evaluate &(f) --> f. The expression is now "f".
Finally, return false.

Example 2

1
2
3

Input: expression = "|(f,f,f,t)"
Output: true
Explanation: The evaluation of (false OR false OR false OR true) is true.

Example 3

1
2
3
4
5

Input: expression = "!(&(f,t))"
Output: true
Explanation: 
First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)".
Then, evaluate !(f) --> NOT false --> true. We return true.

Solution

Method 1 - Using Stack

We can evaluate the Boolean expression using a stack-based approach. Here is a step-by-step description:

  1. Stack Usage: Use a stack to keep track of characters and sub-expressions as we parse through the input string.
  2. Character Handling:
    • Operands: Push t and f onto the stack.
    • Operators and Parentheses: When encountering &, |, and !, push them onto the stack.
    • Closing Parenthesis ): Start evaluating the expression when encountering ). Pop elements from the stack until a matching ( is found. Depending on the operator, compute the result for the sub-expression and push the result back onto the stack.
  3. Evaluation of Sub-Expressions:
    • NOT !: Negate the sub-expression.
    • AND &: Evaluate the AND operation over multiple sub-expressions.
    • OR |: Evaluate the OR operation over multiple sub-expressions.
  4. Final Result: The final result of the evaluation will be left at the top of the stack once the entire expression is processed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {

    public boolean parseBoolExpr(String expression) {
        Stack<Character> stack = new Stack<>();
        
        for (char ch : expression.toCharArray()) {
            if (ch == ',') {
                continue;
            } else if (ch != ')') {
                stack.push(ch);
            } else {
                int tCount = 0, fCount = 0;
                
                while (stack.peek() != '(') {
                    char val = stack.pop();
                    if (val == 't') {
                        tCount++;
                    } else if (val == 'f') {
                        fCount++;
                    }
                }
                
                stack.pop();  // Remove '('
                char operator = stack.pop();
                
                switch (operator) {
                    case '&':
                        stack.push(fCount > 0 ? 'f' : 't');
                        break;
                    case '|':
                        stack.push(tCount > 0 ? 't' : 'f');
                        break;
                    case '!':
                        stack.push(fCount > 0 ? 't' : 'f');
                        break;
                }
            }
        }
        
        return stack.pop() == 't';
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        
        for ch in expression:
            if ch == ',':
                continue
            elif ch != ')':
                stack.append(ch)
            else:
                t_count = 0
                f_count = 0
                while stack and stack[-1] != '(':
                    val = stack.pop()
                    if val == 't':
                        t_count += 1
                    elif val == 'f':
                        f_count += 1
                
                stack.pop()  # Remove '('
                operator = stack.pop()
                
                if operator == '&':
                    stack.append('t' if f_count == 0 else 'f')
                elif operator == '|':
                    stack.append('t' if t_count > 0 else 'f')
                elif operator == '!':
                    stack.append('t' if f_count > 0 else 'f')
        
        return stack.pop() == 't'

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string expression. This accounts for traversing and processing each character in the expression.
  • 🧺 Space complexity: O(n) in the worst case, due to the stack usage for storing the characters and intermediate results.