LeetCode 439: Ternary Expression Parser Solution in Python – A Step-by-Step Guide

What Is LeetCode 439: Ternary Expression Parser?

In LeetCode 439: Ternary Expression Parser, you’re given a string representing a ternary expression—think of it as a shorthand for if-then-else statements. The format is condition?value_if_true:value_if_false, where conditions can nest (e.g., "T?2:F?3:4"). Your task is to evaluate it and return the final value as a string. For example, "F?1:T?4:5" means "if false, pick 1, else evaluate T?4:5," which resolves to "4". It’s like unwinding a logic puzzle one step at a time.

Problem Statement

• Input: expression (str)—a valid ternary expression.
• Output: str—the evaluated result (a single character: "T", "F", or a digit).
• Rules:
• Expression uses "T" (true), "F" (false), "?", ":", and digits 0-9.
• Always valid and evaluates to one character.
• Conditions can nest (e.g., "T?F?1:2:3").

Constraints

• 1 <= expression.length <= 10^4.
• Contains only "T", "F", "?", ":", and digits 0-9.
• Guaranteed to be valid and evaluate to a single character.

Examples to Get Us Started

• Input: expression = "T?2:3"
• Output: "2" (T means true, so pick 2).
• Input: expression = "F?1:T?4:5"
• Output: "4" (F picks T?4:5, then T picks 4).
• Input: expression = "T?T?F:5:3"
• Output: "F" (T picks T?F:5, then T picks F).

Understanding the Problem: Decoding the Ternary Puzzle

To solve LeetCode 439: Ternary Expression Parser in Python, we need to evaluate a string of nested ternary expressions. A naive approach—manually splitting and checking each part—would be messy and slow, especially with nesting. Instead, we’ll use:

• Best Solution (Stack-Based, Right-to-Left): O(n) time, O(n) space—fast and clean.
• Alternative Solution (Recursive): O(n) time, O(n) space—intuitive but trickier with recursion depth.

Let’s dive into the stack-based solution—it’s the key to cracking this code efficiently.

Best Solution: Stack-Based Parsing (Right-to-Left)

Why This Is the Best Solution

The stack-based, right-to-left approach is the champ because it’s O(n) time and O(n) space, processing the string in one pass without complex recursion. By scanning from the end and using a stack to hold values and operators, we resolve nested expressions as we encounter their conditions. It’s like reading a book backward, piecing together the story as you go—simple and effective!

How It Works

Here’s the strategy:

• Step 1: Start from the right end of the string.
• Step 2: Use a stack to push characters:
• Push digits, "T", "F", ":", and "?" as you scan right to left.
• Step 3: When you hit a condition ("T" or "F") with a full expression on the stack:
• Pop the condition, "?", true_value, ":", and false_value.
• Evaluate: if "T", push true_value; if "F", push false_value.
• Step 4: Continue until one value remains—the result.
• Why It Works:
• Right-to-left ensures we evaluate inner expressions first.
• Stack naturally handles nesting by resolving as conditions appear.

Step-by-Step Example

Example: expression = "T?2:3"

• Scan Right to Left:
• Stack: [] → [3] → [3, :] → [3, :, 2] → [3, :, 2, ?] → [3, :, 2, ?, T].
• Process:
• Top: T, ?, 2, :, 3.
• T?2:3 → T is true, push 2.
• Stack: [2].
• Result: "2".

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

• Scan:
• Stack: [5] → [5, :] → [5, :, 4] → [5, :, 4, ?] → [5, :, 4, ?, T] → [5, :, 4, ?, T, :] → [5, :, 4, ?, T, :, 1] → [5, :, 4, ?, T, :, 1, ?] → [5, :, 4, ?, T, :, 1, ?, F].
• Process:
• F, ?, 1, :, (T?4:5):
• Evaluate T?4:5 → T picks 4, stack = [5, :, 4, ?, T, :, 4].
• Pop extra, stack = [4].
• F?1:4 → F picks 4, stack = [4].
• Result: "4".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def parseTernary(self, expression: str) -> str:
        # Stack to hold characters
        stack = []

        # Scan from right to left
        for char in reversed(expression):
            stack.append(char)

            # Check if we have a full ternary expression
            while len(stack) >= 5 and stack[-1] in 'TF':
                # Pop condition, ?, true_val, :, false_val
                condition = stack.pop()  # T or F
                stack.pop()  # ?
                true_val = stack.pop()
                stack.pop()  # :
                false_val = stack.pop()

                # Evaluate and push result
                if condition == 'T':
                    stack.append(true_val)
                else:
                    stack.append(false_val)

        # Final result is the only item left
        return stack[0]

• Line 4: Initialize empty stack.
• Line 7-8: Push each character from right to left.
• Line 11-19: When stack has 5+ items and top is a condition:
• Pop T/F, ?, true_val, :, false_val (e.g., [3, :, 2, ?, T]).
• If T, push true_val; if F, push false_val.
• Line 22: Return lone remaining value.
• Time Complexity: O(n)—one pass, each char processed once.
• Space Complexity: O(n)—stack size.

It’s like unwinding a nested gift box in one smooth motion!

Alternative Solution: Recursive Parsing

Why an Alternative Approach?

The recursive method parses left-to-right, breaking the string into condition, true, and false parts—O(n) time, O(n) space due to recursion. It’s more intuitive, mimicking how we’d manually evaluate, but it’s trickier with nested expressions. It’s like following a treasure map step-by-step, diving deeper at each fork.

How It Works

• Step 1: Start at index 0 with condition.
• Step 2: Recursively:
• Find "?" and split into true/false parts at ":".
• Evaluate sub-expressions if nested.
• Return value based on condition.
• Step 3: Base case: single character.

Step-by-Step Example

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

• Parse:
• F?1:(T?4:5):
• F is false, evaluate T?4:5.
• T?4:5 → T picks 4.
• F picks 4.
• Result: "4".

Code for Recursive Approach

Copy codeclass Solution:
    def parseTernary(self, expression: str) -> str:
        def parse(index):
            # Base case: single character
            if index >= len(expression) or expression[index + 1] != '?':
                return expression[index], index + 1

            # Condition
            condition = expression[index]
            index += 2  # Skip ? after condition

            # True value (might be nested)
            true_val, next_index = parse(index)
            index = next_index + 1  # Skip :

            # False value
            false_val, next_index = parse(index)

            # Evaluate
            return (true_val if condition == 'T' else false_val), next_index

        result, _ = parse(0)
        return result

• Time Complexity: O(n)—processes each char once.
• Space Complexity: O(n)—recursion stack.

It’s a deep dive into the expression’s layers.

Comparing the Two Solutions

• Stack-Based (Best):
• Pros: O(n), simple, iterative.
• Cons: O(n) space, less intuitive at first.
• Recursive (Alternative):
• Pros: O(n), mirrors logic flow.
• Cons: O(n) space, recursion overhead.

Stack wins for simplicity and control.

Edge Cases and More Examples

• Input: "5" → "5".
• Input: "T?F:5" → "F".
• Input: "F?T:F" → "F".

Both handle these smoothly.

Complexity Recap

• Stack-Based: Time O(n), Space O(n).
• Recursive: Time O(n), Space O(n).

Stack’s iterative edge shines.

Key Takeaways

• Stack: Unwind from the end.
• Recursive: Dive from the start.
• Python Tip: Stacks simplify parsing—see [Python Basics](/python/basics).

Final Thoughts: Crack the Code

LeetCode 439: Ternary Expression Parser in Python is a logic-packed parsing adventure. The stack-based solution is your quick decoder, while recursion offers a thoughtful journey. Want more parsing fun? Try LeetCode 394: Decode String or LeetCode 227: Basic Calculator II. Ready to parse some ternaries? Head to Solve LeetCode 439 on LeetCode (if unlocked) and unravel the puzzle today—your coding detective skills are on fire!