Problem statement

https://leetcode.com/problems/parsing-a-boolean-expression/

Solution

As the most of parser problems, it can be solved with stack or/and recursion. Let us iterate element by element and if we have f or t we denote them by 0 and 1 and denote other functions as 2, 3, 4. When we meet ), it means that we need to extract 0 and 1 from stack until it is possible. Then we extract one more element from stack, it will be operation and apply it. In the end we add element to stack if it is not bracket and not comma.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def parseBoolExpr(self, E):
        stack = []
        d = {"f": 0, "t": 1, "&": 2, "|": 3, "!": 4}
        for s in E:
            if s == ")":  #extract from stack until we meet 2, 3, 4 and put put result back.
                last = []
                while stack[-1] <= 1:
                    last.append(stack.pop())
                op = stack.pop()
                if op == 2: 
                    stack.append(all(last))
                if op == 3:
                    stack.append(any(last))
                if op == 4:
                    stack.append(1-last[0])
                
            if s in d:
                stack.append(d[s])
                                 
        return stack[0]