LeetCode 439 - Ternary Expression Parser

LeetCode Problem 439

Difficulty: 🟡 Medium
Topics: String, Stack, Recursion

Solution

Problem Understanding

The problem gives us a string representing a nested ternary expression and asks us to evaluate it. A ternary expression follows the familiar format:

condition ? value_if_true : value_if_false

The condition is always either 'T' or 'F'. If the condition is 'T', the expression evaluates to the value before the ':'. If the condition is 'F', it evaluates to the value after the ':'.

The important complication is that expressions may be nested arbitrarily deeply. For example:

F?1:T?4:5

is interpreted as:

F ? 1 : (T ? 4 : 5)

because ternary expressions associate from right to left.

The input string contains only:

• Digits from 0 to 9
• 'T' and 'F'
• '?'
• ':'

Every numeric value is guaranteed to be a single digit, which simplifies parsing because we never need to read multi-character numbers.

The constraints allow expressions up to length 10^4, which means recursive reparsing or repeated string slicing can become expensive. We need an efficient linear-time solution.

Several edge cases are especially important:

• Deeply nested expressions such as "T?T?T?1:2:3:4"
• Expressions where only the far-right branch matters
• Alternating true and false conditions
• Minimal valid expressions like "T?2:3"

The problem guarantees the expression is always valid, which means we never need to handle malformed syntax.

Approaches

Brute Force Approach

A straightforward solution is to repeatedly locate and evaluate the innermost ternary expression.

For example:

F?1:T?4:5

We could first identify:

T?4:5

evaluate it to 4, then replace the substring:

F?1:4

and finally evaluate again.

This works because nested ternary expressions always reduce to a single value after evaluation.

However, repeatedly scanning the string and rebuilding substrings is inefficient. Each replacement may cost O(n), and we may perform many such operations, leading to quadratic complexity in the worst case.

With input sizes up to 10^4, this becomes unnecessarily slow.

Optimal Approach

The key observation is that ternary expressions associate from right to left.

For example:

T?T?F:5:3

should be interpreted as:

T ? (T ? F : 5) : 3

This naturally suggests processing the string from right to left.

A stack works extremely well here. As we scan backward:

• Operands are pushed onto the stack
• When we encounter a condition (T or F) followed by a '?', we already have the true and false results available on the stack
• We evaluate immediately and push the chosen result back

This allows every character to be processed exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly reparses and rebuilds strings
Optimal	O(n)	O(n)	Uses right-to-left traversal with a stack

Algorithm Walkthrough

1. Initialize an empty stack.

The stack will store partially evaluated results. Since every expression ultimately evaluates to a single character, each stack element is just one character. 2. Traverse the expression from right to left.

Right-to-left traversal matches the natural associativity of ternary expressions. By the time we encounter a condition, its true and false branches have already been processed. 3. For each character, check whether it starts a ternary operation.

Specifically, if the current character is 'T' or 'F', and the next character is '?', then we are looking at a condition expression. 4. Pop the true and false branches from the stack.

The stack layout will look like:

[ ..., true_value, false_value ]

because the expression was processed from right to left. 5. Evaluate the condition.

• If condition is 'T', choose the true branch
• Otherwise choose the false branch

Push the selected value back onto the stack. 6. Ignore ':' and '?' characters during normal traversal.

They only help identify expression structure. 7. Push literal values onto the stack.

Digits, 'T', and 'F' that are not conditions are treated as values. 8. After traversal completes, the stack contains exactly one value.

That value is the final result.

Why it works

The correctness relies on right-to-left associativity. When processing a condition, the stack already contains the fully evaluated results of both branches. Replacing the ternary expression with its chosen branch preserves the meaning of the original expression. Repeating this reduction eventually collapses the entire expression into a single value.

Python Solution

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

        i = len(expression) - 1

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

            # If current character is a condition
            if (
                current in ("T", "F")
                and i + 1 < len(expression)
                and expression[i + 1] == "?"
            ):
                true_value = stack.pop()
                false_value = stack.pop()

                if current == "T":
                    stack.append(true_value)
                else:
                    stack.append(false_value)

                i -= 1  # Skip '?'
            elif current not in ("?", ":"):
                stack.append(current)

            i -= 1

        return stack[-1]

The implementation mirrors the algorithm directly.

We maintain a stack of evaluated values. Traversing from right to left ensures nested expressions are resolved before outer expressions.

The key section is:

if current in ("T", "F") and expression[i + 1] == "?":

This identifies whether the current character is acting as a condition rather than merely being a value.

When such a condition is found, we pop two values from the stack. Because of right-to-left traversal:

• The first popped value corresponds to the true branch
• The second corresponds to the false branch

We then select the correct result based on the condition and push it back.

Characters ':' and '?' are structural markers and do not need to be stored.

At the end, the stack contains the fully evaluated result.

Go Solution

func parseTernary(expression string) string {
	stack := []byte{}

	for i := len(expression) - 1; i >= 0; i-- {
		current := expression[i]

		// Check if current character is a condition
		if (current == 'T' || current == 'F') &&
			i+1 < len(expression) &&
			expression[i+1] == '?' {

			trueValue := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			falseValue := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			if current == 'T' {
				stack = append(stack, trueValue)
			} else {
				stack = append(stack, falseValue)
			}

			i-- // Skip '?'
		} else if current != '?' && current != ':' {
			stack = append(stack, current)
		}
	}

	return string(stack[len(stack)-1])
}

The Go implementation follows the same logic as the Python version but uses a byte slice as the stack.

Because all characters are single-byte ASCII values, using []byte is efficient and avoids unnecessary string allocations.

Stack popping is implemented with slice truncation:

stack = stack[:len(stack)-1]

The final byte is converted back into a string before returning.

Worked Examples

Example 1

expression = "T?2:3"

Processing from right to left:

Step	Character	Stack Before	Action	Stack After
1	3	[]	Push value	[3]
2	:	[3]	Ignore	[3]
3	2	[3]	Push value	[3,2]
4	?	[3,2]	Ignore	[3,2]
5	T	[3,2]	Choose true branch	[2]

Final result:

"2"

Example 2

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

Step	Character	Stack Before	Action	Stack After
1	5	[]	Push	[5]
2	:	[5]	Ignore	[5]
3	4	[5]	Push	[5,4]
4	?	[5,4]	Ignore	[5,4]
5	T	[5,4]	Choose 4	[4]
6	:	[4]	Ignore	[4]
7	1	[4]	Push	[4,1]
8	?	[4,1]	Ignore	[4,1]
9	F	[4,1]	Choose 4	[4]

Final result:

"4"

Example 3

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

Step	Character	Stack Before	Action	Stack After
1	3	[]	Push	[3]
2	:	[3]	Ignore	[3]
3	5	[3]	Push	[3,5]
4	:	[3,5]	Ignore	[3,5]
5	F	[3,5]	Push literal	[3,5,F]
6	?	[3,5,F]	Ignore	[3,5,F]
7	T	[3,5,F]	Choose F	[3,F]
8	?	[3,F]	Ignore	[3,F]
9	T	[3,F]	Choose F	[F]

Final result:

"F"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed at most once
Space	O(n)	Stack may store many intermediate values

The algorithm performs a single right-to-left traversal of the input string. Every character is either ignored, pushed once, or popped once, giving linear time complexity.

The stack may contain up to O(n) values in heavily nested expressions, so the auxiliary space usage is linear.

Test Cases

solution = Solution()

assert solution.parseTernary("T?2:3") == "2"  # Simple true condition
assert solution.parseTernary("F?2:3") == "3"  # Simple false condition

assert solution.parseTernary("F?1:T?4:5") == "4"  # Nested right-side ternary
assert solution.parseTernary("T?T?F:5:3") == "F"  # Nested left-side ternary

assert solution.parseTernary("T?T?1:2:F?3:4") == "1"  # Multiple nested expressions
assert solution.parseTernary("F?T?1:2:F?3:4") == "4"  # Nested false branch

assert solution.parseTernary("T?F:T") == "F"  # Boolean result
assert solution.parseTernary("F?F:T") == "T"  # Boolean result with false condition

assert solution.parseTernary("T?0:9") == "0"  # Digit boundary
assert solution.parseTernary("F?0:9") == "9"  # Digit boundary

assert solution.parseTernary("T?T?T?1:2:3:4") == "1"  # Deep nesting
assert solution.parseTernary("F?1:F?2:F?3:4") == "4"  # Deep false nesting

Test	Why
"T?2:3"	Verifies basic true evaluation
"F?2:3"	Verifies basic false evaluation
"F?1:T?4:5"	Tests right-to-left associativity
"T?T?F:5:3"	Tests nested true branches
"T?T?1:2:F?3:4"	Tests multiple nested expressions
"F?T?1:2:F?3:4"	Tests nested false branches
"T?F:T"	Verifies boolean outputs
"F?F:T"	Verifies false-condition boolean selection
"T?0:9"	Tests lower digit boundary
"F?0:9"	Tests upper digit boundary
"T?T?T?1:2:3:4"	Tests deep recursive nesting
"F?1:F?2:F?3:4"	Tests repeated false nesting

Edge Cases

One important edge case is deeply nested right-associative expressions. A naive left-to-right parser may incorrectly interpret:

T?T?1:2:3

as:

(T ? T ? 1 : 2) : 3

instead of the correct:

T ? (T ? 1 : 2) : 3

The right-to-left traversal naturally handles this associativity correctly because inner expressions are evaluated before outer ones.

Another subtle case is when 'T' or 'F' appears as a value rather than as a condition. For example:

T?F:5

Here, the inner 'F' is not a condition. Incorrect implementations may try to treat every 'T' or 'F' as the start of a ternary operation. The implementation avoids this by checking whether the next character is '?'.

A third important case is very deep nesting near the maximum input size. Recursive solutions may risk stack overflow if nesting depth becomes large. The iterative stack-based solution avoids recursion entirely, making it safe for expressions of length up to 10^4.