[Leetcode] - 439

• expression 길이가 길어서 recursive call 방식으로는 풀지 못함
• stack을 사용해 expression을 재귀처리
• 시간복잡도: O(N)
• 공간복잡도: O(N)
• tree build 방식으로 다시 풀기

class Solution:
    def parseTernary(self, expression: str) -> str:                
        stack = []
        for c in reversed(expression):            
            if stack and stack[-1] == '?':
                stack.pop()
                left = stack.pop()
                stack.pop()
                right = stack.pop()
                if c == 'T':
                    stack.append(left)
                else:
                    stack.append(right)
            else:
                stack.append(c)
        return stack.pop()