1106. Parsing A Boolean Expression

Problem Statement

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 ','.

Intuition

Push until ) and pop till (

Then maintain two variables hasT and hasF instead of maintaining entire array

And evaluate the answer


Another approach using recursion

Links

https://leetcode.com/problems/parsing-a-boolean-expression/description/

Video Links

https://www.youtube.com/watch?v=lYw86z7Astg&ab_channel=leetuition

Approach 1:

Stacking

C++

class Solution {
public:
    bool parseBoolExpr(string str) {
        stack<char> s;
        bool hasT = false;
        bool hasF = false;

        for(int i=0; i<str.size(); i++){
            if(s.empty() )
                s.push(str[i]);

            else if(str[i] == ')'){
                bool hasT = false, hasF = false;

                while(s.top() != '('){
                    if(s.top() == 't')
                        hasT = true;

                    if(s.top() == 'f')
                        hasF = true;

                    s.pop();
                }
                s.pop();
                char opt = s.top();
                s.pop();
                char temp;

                if(opt == '&')
                    temp = hasF == true ? 'f' : 't';           

                else if(opt == '|')
                    temp = hasT == true ? 't' : 'f';                

                else
                    temp = hasT == true ? 'f' : 't';
                
                s.push(temp);
            } 

            else if(str[i] != ',')
                s.push(str[i]);
        }

        if(s.top() == 't')
            return true;

        return false;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++