<p>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:</p>

<ul>
	<li><code>&#39;t&#39;</code> that evaluates to <code>true</code>.</li>
	<li><code>&#39;f&#39;</code> that evaluates to <code>false</code>.</li>
	<li><code>&#39;!(subExpr)&#39;</code> that evaluates to <strong>the logical NOT</strong> of the inner expression <code>subExpr</code>.</li>
	<li><code>&#39;&amp;(subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub>)&#39;</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 &gt;= 1</code>.</li>
	<li><code>&#39;|(subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub>)&#39;</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 &gt;= 1</code>.</li>
</ul>

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

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= expression.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li>expression[i] is one following characters: <code>&#39;(&#39;</code>, <code>&#39;)&#39;</code>, <code>&#39;&amp;&#39;</code>, <code>&#39;|&#39;</code>, <code>&#39;!&#39;</code>, <code>&#39;t&#39;</code>, <code>&#39;f&#39;</code>, and <code>&#39;,&#39;</code>.</li>
</ul>

from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import (
    Callable,
    Generic,
    Iterable,
    Literal,
    TypeAlias,
    TypeVar,
    assert_never,
    cast,
)

TokenTypes: TypeAlias = Literal[
    "True",
    "False",
    "Or",
    "And",
    "Not",
    "Comma",
    "LeftParenthesis",
    "RightParenthesis",
    "EOF",
]
T = TypeVar("T")
TTokenType = TypeVar("TTokenType", bound=TokenTypes)
TTokenType_co = TypeVar("TTokenType_co", bound=TokenTypes, covariant=True)


@dataclass
class Token(Generic[TTokenType_co]):
    token_type: TTokenType_co
    lexeme: str
    position: int
    literal: bool | None


class Lexer:
    def __init__(self, source: str):
        self.source = source
        self.start = 0
        self.current = 0
        return super().__init__()

    def exhausted(self):
        return self.current >= len(self.source)

    def _consume(self):
        return self.source[self._advance()]

    def _peek(self):
        return None if self.exhausted() else self.source[self.current]

    def _advance(self):
        self.current = (current := self.current) + 1
        return current

    def _make(
        self, token_type: TTokenType, parse: Callable[[str], bool] | None = None
    ) -> Token[TTokenType]:
        lexeme = self._lexeme()
        literal = None if parse is None else parse(lexeme)
        return Token(token_type, lexeme, self.start, literal)

    def _lexeme(self):
        return self.source[self.start : self.current]

    def __iter__(self):
        return Lexer(self.source)

    def __next__(self):
        while not self.exhausted():
            return self._get()
        raise StopIteration

    def _get(self):
        self.start = self.current
        match (consumed := self._consume()):
            case "(":
                return self._make("LeftParenthesis")
            case ")":
                return self._make("RightParenthesis")
            case "t":
                return self._make("True")
            case ",":
                return self._make("Comma")
            case "f":
                return self._make("False")
            case "!":
                return self._make("Not")
            case "|":
                return self._make("Or")
            case "&":
                return self._make("And")
            case other:
                raise ValueError(f"Invalid token {other!r}!")
        assert_never(consumed)


class Expression(ABC):
    @abstractmethod
    def evaluate(self) -> bool: ...

    @abstractmethod
    def __str__(self) -> str: ...


class BooleanLiteral(Expression):
    def __init__(self, value: bool):
        self.value = value
        return super().__init__()

    def evaluate(self) -> bool:
        return self.value

    def __str__(self) -> str:
        return str(self.value)


class Negation(Expression):
    def __init__(self, expression: Expression):
        self.expression = expression
        return super().__init__()

    def evaluate(self) -> bool:
        return not self.expression.evaluate()

    def __str__(self) -> str:
        return f"!({self.expression})"


class NaryExpression(Expression):
    def __init__(self, *exprs: Expression):
        self.exprs = exprs
        return super().__init__()

    @staticmethod
    @abstractmethod
    def apply(*vals: bool) -> bool: ...

    @staticmethod
    @abstractmethod
    def name() -> str: ...

    def evaluate(self) -> bool:
        return self.apply(*(expr.evaluate() for expr in self.exprs))

    def __str__(self) -> str:
        return f"{self.name()}({', '.join(map(str, self.exprs))})"


class Conjunction(NaryExpression):
    @staticmethod
    def apply(*vals: bool) -> bool:
        return all(vals)

    @staticmethod
    def name() -> str:
        return "And"


class Disjunction(NaryExpression):
    @staticmethod
    def apply(*vals: bool) -> bool:
        return any(vals)

    @staticmethod
    def name() -> str:
        return "Or"


class ParseException(Exception):
    def __init__(self, token: Token[TokenTypes] | None, message: str, *args: object):
        self.token = token
        super().__init__(message, *args)


class Parser:
    def __init__(self, tokens: Iterable[Token[TokenTypes]]):
        self.tokens = iter(tokens)
        self._exhausted = False
        self._peeked = None
        return super().__init__()

    def _match_any(self, *expected: TTokenType) -> Token[TTokenType] | None:
        for exp in expected:
            if (matched := self._match(exp)) is not None:
                return matched
        return None

    def _match(self, expected: TTokenType) -> Token[TTokenType] | None:
        if self._exhausted:
            return None
        if (token := self._peek()) is not None and token.token_type == expected:
            return cast(Token[TTokenType], self._advance())
        return None

    def _peek(self):
        if (peeked := self._peeked) is not None:
            return peeked
        peeked = self._advance()
        self._peeked = peeked
        return peeked

    def _advance(self):
        if (peeked := self._peeked) is not None:
            self._peeked = None
            return peeked
        try:
            return next(self.tokens)
        except StopIteration:
            self._exhausted = True
            return None

    def _consume(self, expected: TTokenType) -> Token[TTokenType]:
        if (matched := self._match(expected)) is None:
            peek = self._peek()
            gotten = "nothing" if peek is None else peek.token_type
            raise ParseException(peek, f"Expected {expected}, but got {gotten}!")
        return matched

    def _consume_any(self, *expected: TTokenType) -> Token[TTokenType]:
        if (matched := self._match_any(*expected)) is None:
            peek = self._peek()
            gotten = "nothing" if peek is None else peek.token_type
            raise ParseException(peek, f"Expected {expected}, but got {gotten}!")
        return matched

    def expression(self) -> Expression:
        term = self.term()
        if (peeked := self._peek()) is not None:
            raise ParseException(peeked, "Expected end of expression!")
        return term

    def _function(
        self,
        *expected: TTokenType,
        make: Callable[[Token[TTokenType], list[Expression]], T],
    ) -> T | None:
        if (token := self._match_any(*expected)) is None:
            return None
        self._consume("LeftParenthesis")
        exprs = list[Expression]()
        while True:
            exprs.append(self.term())
            sep = self._consume_any("Comma", "RightParenthesis")
            if sep.token_type == "RightParenthesis":
                return make(token, exprs)

    def _make_function(
        self, token: Token[Literal["Or", "And", "Not"]], args: list[Expression]
    ):
        match token.token_type:
            case "Not":
                assert len(args) == 1
                return Negation(args[0])
            case "And":
                return Conjunction(*args)
            case "Or":
                return Disjunction(*args)
        assert_never(token.token_type)

    def term(self) -> Expression:
        if (
            func := self._function("Or", "And", "Not", make=self._make_function)
        ) is not None:
            return func
        literal = self._consume_any("True", "False")
        match literal.token_type:
            case "True":
                return BooleanLiteral(True)
            case "False":
                return BooleanLiteral(False)
        assert_never(literal.token_type)


class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        lexer = Lexer(expression)
        parser = Parser(lexer)
        try:
            parsed = parser.expression()
            return parsed.evaluate()
        except ParseException as e:
            if (token := e.token) is not None:
                end = token.position + len(token.lexeme)
                e.add_note(
                    f"Error at: {expression[:token.position]} > {token.lexeme} < {expression[end:]}"
                )
            raise e

18400