Skip to content

1197. Parsing A Boolean Expression

Difficulty: Hard

LeetCode Problem View on GitHub

1197. Parsing A Boolean Expression

Hard

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.

 

Example 1:

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:

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

Example 3:

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.

 

Constraints:

  • 1 <= expression.length <= 2 * 104
  • expression[i] is one following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.

Solution

class Solution {
    public boolean parseBoolExpr(String s) {
        int n = s.length();
        Stack<Character> first = new Stack<>();
        Stack<Character> second = new Stack<>();
        for (int i = 0; i < n; i++) {
            char current = s.charAt(i);
            if (current == ',') continue;
            if (current == '&' || current == '|' || current == '!') second.add(current);
            else {
                if (current == ')') {
                    char todo = second.pop();
                    if (todo == '&') {
                        boolean flag = true;
                        while (first.size() > 0 && first.peek() != '(') {
                            char ch = first.pop();
                            if (ch == 'f') flag = false;
                        }
                        first.pop();
                        if (flag == true) first.add('t');
                        else first.add('f');
                    }
                    else if (todo == '|') {
                        boolean flag = false;
                        while (first.size() > 0 && first.peek() != '(') {
                            char ch = first.pop();
                            if (ch == 't') flag = true;
                        }
                        first.pop();
                        if (flag == true) first.add('t');
                        else first.add('f');
                    }
                    else if (todo == '!') {
                        char ch = first.pop();
                        first.pop();
                        if (ch == 't') first.add('f');
                        else first.add('t');
                    }
                }
                else first.add(current);
            }
        }
        if (first.peek() == 't') return true;
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(?)
  • Space Complexity: O(?)

Approach

Detailed explanation of the approach will be added here