> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/stack/1106.-parsing-a-boolean-expression.md).

# 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

###


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/stack/1106.-parsing-a-boolean-expression.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.