Parsing A Boolean Expression Python Solution

lcpy gen -n 1106   # by problem number
lcpy gen -s parsing_a_boolean_expression   # by problem name

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.

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"