Ternary Expression Parser - Leetcode Solution

The Ternary Expression Parser problem on leetcode can be solved using a stack-based approach. The problem statement is as follows:

Given a string representing a ternary expression, evaluate the expression and return the result.

The expression is represented in the following format: expression ? trueValue : falseValue

For example, the string "T?2:3" represents the expression "if true, return 2; otherwise, return 3".

The solution for this problem can be broken down into the following steps:

1. Iterate through the input expression from right to left using a for loop.
2. Push each character onto the stack.
3. When a question mark (?) is encountered, pop the top two elements of the stack (which should be the expressions before and after the question mark).
4. Evaluate the expression before the question mark. If it is true, continue evaluation with the expression after the question mark. Otherwise, skip the expression after the colon (:) and continue with the next element in the stack.
5. After all elements in the stack have been evaluated, return the result.

Here's the Python code implementing this solution:

class Solution:
    def parseTernary(self, expression: str) -> str:
        stack = []
        for c in reversed(expression):
            stack.append(c)
            if stack[-2:-1] == ['?',]:
                ternary = []
                while stack[-1] not in [':', '?']:
                    ternary.append(stack.pop())
                stack.pop() # remove '?'
                if stack.pop() == 'T':
                    stack += ternary[::-1]
                else:
                    while stack[-1] != ':':
                        stack.pop()
                    stack.pop() # remove ':'
        return stack[0]

This solution has a time complexity of O(n), where n is the length of the input expression. This is because we iterate through the expression once and perform constant-time operations for each character. The space complexity is also O(n), since we use a stack to store the characters in the expression.

1