# LeetCode 439: Ternary Expression Parser

## Problem Restatement

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

A ternary expression has the form:

```text
condition ? true_value : false_value
```

The condition is always either:

```text
T
F
```

where `T` means true and `F` means false.

The expression contains only:

| Character | Meaning |
|---|---|
| `T` | true |
| `F` | false |
| `0` to `9` | single digit value |
| `?` | starts a ternary choice |
| `:` | separates true branch and false branch |

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

| Item | Meaning |
|---|---|
| Input | A valid ternary expression string |
| Output | The evaluated result as a string |
| Condition | Always `T` or `F` |
| Values | Single characters: digit, `T`, or `F` |
| Associativity | Right-to-left |

Example function shape:

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

## Examples

Example 1:

```python
expression = "T?2:3"
```

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

```text
2
```

Answer:

```python
"2"
```

Example 2:

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

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

```text
F ? 1 : (T ? 4 : 5)
```

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

```text
T ? 4 : 5
```

That condition is `T`, so the result is:

```python
"4"
```

Example 3:

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

This groups as:

```text
T ? (T ? F : 5) : 3
```

The first condition is `T`, so we evaluate:

```text
T ? F : 5
```

That condition is also `T`, so the result is:

```python
"F"
```

## First Thought: Recursive Parsing

We can parse the expression recursively.

For an expression like:

```text
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:

```text
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:

```text
T ? 2 : 3
```

Scanning right to left:

```text
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each character is processed at most once |
| Space | `O(n)` | The stack can store characters from the expression |

Here, `n` is the length of `expression`.

## Implementation

```python
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:

```python
i = len(expression) - 1
```

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

```python
stack = []
```

A colon is only a separator:

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

So we skip it.

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

```python
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.

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

Then we keep the correct branch:

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

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

```python
i -= 2
```

Any other character is a value and can be pushed:

```python
stack.append(ch)
```

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

```python
return stack[-1]
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `T?2:3` | Checks simple true branch |
| `F?1:T?4:5` | Checks right-to-left grouping |
| `T?T?F:5:3` | Checks nested true branch |
| `F?T:F` | Checks boolean result |
| `T?9:F?1:2` | Checks skipping false branch |
| `F?9:F?1:2` | Checks nested false branch |
| Single `T` | Checks already evaluated expression |
| Single digit | Checks value-only expression |