Problem statement

https://leetcode.com/problems/ternary-expression-parser/

Solution

First important point is that we need to traverse our string from right to left, be careful! We keep stack of elements and we add element to the end one by one. If at some point we have reversed pattern *?*:* (because we go form the end) in the end, where * is any symbol, we transform these 5 elements to one.

Complexity

Time complexity is O(n), space potentially is also O(n).

Code

class Solution:
    def parseTernary(self, expression):
        stack = []
        
        for symb in expression[::-1]:
            stack.append(symb) 
            while len(stack) > 4 and stack[-4] == ":" and stack[-2] == "?":
                last_5 = [stack.pop() for _ in range(5)]
                if last_5[0] == "F": 
                    stack.append(last_5[4])
                else: 
                    stack.append(last_5[2])
        return stack[0]