> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Parsing A Boolean Expression Python Solution

> Tested Python solution for LeetCode 1106 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 1106, [Hard](/catalog/hard). Topics: [String](/catalog/topics/string), [Stack](/catalog/topics/stack), [Recursion](/catalog/topics/recursion). [View on LeetCode](https://leetcode.com/problems/parsing-a-boolean-expression/description/).

Generate this problem as a practice environment: tested reference solution, 17 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1106   # by problem number
lcpy gen -s parsing_a_boolean_expression   # by problem name
```

## Problem

A \<strong>boolean expression\</strong> is an expression that evaluates to either \<code>true\</code> or \<code>false\</code>. It can be in one of the following shapes:

* \<code>'t'\</code> that evaluates to \<code>true\</code>.
* \<code>'f'\</code> that evaluates to \<code>false\</code>.
* \<code>'!(subExpr)'\</code> that evaluates to \<strong>the logical NOT\</strong> of the inner expression \<code>subExpr\</code>.
* \<code>'&(subExpr\<sub>1\</sub>, subExpr\<sub>2\</sub>, ..., subExpr\<sub>n\</sub>)'\</code> that evaluates to \<strong>the logical AND\</strong> of the inner expressions \<code>subExpr\<sub>1\</sub>, subExpr\<sub>2\</sub>, ..., subExpr\<sub>n\</sub>\</code> where \<code>n >= 1\</code>.
* \<code>'|(subExpr\<sub>1\</sub>, subExpr\<sub>2\</sub>, ..., subExpr\<sub>n\</sub>)'\</code> that evaluates to \<strong>the logical OR\</strong> of the inner expressions \<code>subExpr\<sub>1\</sub>, subExpr\<sub>2\</sub>, ..., subExpr\<sub>n\</sub>\</code> where \<code>n >= 1\</code>.

Given a string \<code>expression\</code> that represents a \<strong>boolean expression\</strong>, return \<em>the evaluation of that expression\</em>.

It is \<strong>guaranteed\</strong> that the given expression is valid and follows the given rules.

### Examples

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

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

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

* \<code>1 \<= expression.length \<= 2 \* 10\<sup>4\</sup>\</code>
* \<code>expression\[i]\</code> is one following characters: \<code>'('\</code>, \<code>')'\</code>, \<code>'&'\</code>, \<code>'|'\</code>, \<code>'!'\</code>, \<code>'t'\</code>, \<code>'f'\</code>, and \<code>','\</code>.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/parsing_a_boolean_expression/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/parsing_a_boolean_expression/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n)
    # Space: O(n)
    def parse_bool_expr(self, expression: str) -> bool:
        stack: list[str] = []
        for ch in expression:
            if ch == ",":
                continue
            if ch != ")":
                stack.append(ch)
                continue
            seen: list[bool] = []
            while stack[-1] in ("t", "f"):
                seen.append(stack.pop() == "t")
            stack.pop()
            op = stack.pop()
            if op == "!":
                stack.append("t" if not seen[0] else "f")
            elif op == "&":
                stack.append("t" if all(seen) else "f")
            else:
                stack.append("t" if any(seen) else "f")
        return stack[-1] == "t"
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.