LeetCode 439: Ternary Expression Parser

Problem Restatement

We are given a valid string expression representing nested ternary expressions.

A ternary expression has the form:

condition ? true_value : false_value

The condition is always either:

T
F

where T means true and F means false.

The expression contains only:

Each number has only one digit, and ternary expressions group from right to left. The result is always a single character: a digit, T, or F. The input length is at most 10000.

Input and Output

Example function shape:

def parseTernary(expression: str) -> str:
    ...

Examples

Example 1:

expression = "T?2:3"

Since the condition is T, we choose the true branch:

2

Answer:

"2"

Example 2:

expression = "F?1:T?4:5"

Because ternary expressions group right-to-left, this means:

F ? 1 : (T ? 4 : 5)

The first condition is F, so we evaluate the false branch:

T ? 4 : 5

That condition is T, so the result is:

"4"

Example 3:

expression = "T?T?F:5:3"

This groups as:

T ? (T ? F : 5) : 3

The first condition is T, so we evaluate:

T ? F : 5

That condition is also T, so the result is:

"F"

First Thought: Recursive Parsing

We can parse the expression recursively.

For an expression like:

T?A:B

we need to find the : that matches the first ?.

This becomes tricky because the true or false branch may itself contain nested ternary expressions.

For example:

T?T?F:5:3

The first : we see does not necessarily belong to the first ?.

A recursive parser can work, but we need careful nesting counts.

There is a simpler stack solution.

Key Insight

Ternary expressions group from right to left.

So we can scan the expression from right to left.

When scanning from right to left, by the time we see a condition and its ?, both possible branch results are already available on the stack.

For example:

T ? 2 : 3

Scanning right to left:

3
:
2
?
T

When we reach ?, the stack already contains the true value and false value.

So we can evaluate one ternary expression immediately and push back only the chosen result.

Algorithm

Use a stack of characters.

Scan the expression from right to left using index i.

At each position:

If the current character is a value, push it.

If the current character is :, skip it.

If the current character is ?:

1. The condition is the character immediately before it: expression[i - 1].
2. Pop the true branch from the stack.
3. Pop the false branch from the stack.
4. If the condition is T, push the true branch.
5. Otherwise, push the false branch.
6. Move i one extra step left to skip the condition.

At the end, the stack contains the final result.

Correctness

Because ternary expressions are right-associative, the rightmost complete ternary expression must be evaluated before any ternary expression that contains it.

Scanning from right to left guarantees that when the algorithm reaches a ?, the results of both branches have already been reduced to single characters on the stack.

For each ?, the character immediately before it is the condition. The stack contains the true branch result and false branch result for that ternary expression. The algorithm chooses exactly one of them according to whether the condition is T or F.

This replaces one complete ternary expression with its evaluated result.

Repeating this process reduces nested expressions from inside to outside, following the required right-to-left grouping. Since the input is valid, every ? has exactly one condition, one true branch, and one false branch.

After all operators are processed, only the final evaluated character remains. Therefore, the returned string is correct.

Complexity

Here, n is the length of expression.

Implementation

class Solution:
    def parseTernary(self, expression: str) -> str:
        stack = []
        i = len(expression) - 1

        while i >= 0:
            ch = expression[i]

            if ch == ':':
                i -= 1
            elif ch == '?':
                condition = expression[i - 1]

                true_value = stack.pop()
                false_value = stack.pop()

                if condition == 'T':
                    stack.append(true_value)
                else:
                    stack.append(false_value)

                i -= 2
            else:
                stack.append(ch)
                i -= 1

        return stack[-1]

Code Explanation

We scan from the end:

i = len(expression) - 1

The stack stores values that are ready to be used by a ternary operator:

stack = []

A colon is only a separator:

if ch == ':':
    i -= 1

So we skip it.

When we see ?, the condition is immediately before it:

condition = expression[i - 1]

The two branches are already on the stack.

The first popped value is the true branch.

The second popped value is the false branch.

true_value = stack.pop()
false_value = stack.pop()

Then we keep the correct branch:

if condition == 'T':
    stack.append(true_value)
else:
    stack.append(false_value)

After handling ?, we skip both the ? and its condition:

i -= 2

Any other character is a value and can be pushed:

stack.append(ch)

At the end, the remaining stack value is the final result:

return stack[-1]

Testing

def run_tests():
    s = Solution()

    assert s.parseTernary("T?2:3") == "2"

    assert s.parseTernary("F?1:T?4:5") == "4"

    assert s.parseTernary("T?T?F:5:3") == "F"

    assert s.parseTernary("F?T:F") == "F"

    assert s.parseTernary("T?9:F?1:2") == "9"

    assert s.parseTernary("F?9:F?1:2") == "2"

    assert s.parseTernary("T") == "T"

    assert s.parseTernary("7") == "7"

    print("all tests passed")

run_tests()

Test meaning: