# 1106. Parsing A Boolean Expression

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: expression = "&#x26;(|(f))"
</strong><strong>Output: false
</strong><strong>Explanation: 
</strong>First, evaluate |(f) --> f. The expression is now "&#x26;(f)".
Then, evaluate &#x26;(f) --> f. The expression is now "f".
Finally, return false.
</code></pre>

**Example 2:**

<pre><code><strong>Input: expression = "|(f,f,f,t)"
</strong><strong>Output: true
</strong><strong>Explanation: The evaluation of (false OR false OR false OR true) is true.
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: expression = "!(&#x26;(f,t))"
</strong><strong>Output: true
</strong><strong>Explanation: 
</strong>First, evaluate &#x26;(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)".
Then, evaluate !(f) --> NOT false --> true. We return true.
</code></pre>

&#x20;

**Constraints:**

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

## 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
```

{% code title="C++" lineNumbers="true" %}

```cpp
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;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###