1
class Solution:
2
    def parseBoolExpr(self, expression: str) -> bool:
3

4
        # expresssion map
5
        opMap = {"!": "!", "|": "|", "&": "&"}
6
        expMap = {"t": True, "f": False}
7
        expStack = []
8
        opStack = []
9
        ans = 0
10
        i = 0
11

12
        while i < len(expression):
13

14
            if expression[i] in opMap:
15
                opStack.append(opMap[expression[i]])
16

17
            elif expression[i] in expMap:
18
                expStack.append(expMap[expression[i]])
19

20
            elif expression[i] == "(":
21
                expStack.append("(")
22

23
            # strat performing operations
24
            elif expression[i] == ")":
25
                op = opStack.pop()
26
                ans = []  # evaluator arr
27

28
                # To Check
29
                # print("EXPSTACK :- ", expStack, "OPSTACK :- ", opStack, "outer WHILE")
30

31
                # Performing serries of operation on exp inside a ()
32
                while expStack[-1] != "(":
33

34
                    # To check
35
                    # print("EXPSTACK :- ", expStack, "OPSTACK :- ", opStack, "OPerator :- ",op, "INNER WHILE")
36

37
                    # Not single operation only
38
                    if op == "!":
39
                        ans.append(not expStack.pop())
40
                    else:
41
                        ans.append(expStack.pop())
42

43
                # Operation evaluation for more then 1 exp inside () for &, or
44
                while len(ans) > 1:
45
                    # or
46
                    if op == "|":
47
                        exp1, exp2 = ans.pop(), ans.pop()
48
                        res = exp1 or exp2
49
                        ans.append(res)
50
                    # and
51
                    elif op == "&":
52
                        exp1, exp2 = ans.pop(), ans.pop()
53
                        res = exp1 and exp2
54
                        ans.append(res)
55

56
                # poping ")" and adding the res of operation done above
57
                expStack.pop()  # poping ")"
58
                expStack.append(ans[-1])
59

60
            # increment i
61
            i += 1
62

63
        return expStack[-1]
64

65

66
"""
67
TC : O(n * m) | n = len(expression), m = no of expression inside a prenthesis
68
Sc : O(n)
69
"""