Problem Description

This problem asks you to evaluate a string that represents nested ternary expressions and return the final result.

A ternary expression follows the format: condition ? value_if_true : value_if_false

The input string expression contains:

• Digits 0-9 (single digits only)
• Characters 'T' (representing true) and 'F' (representing false)
• Operators '?' and ':' that form the ternary structure

Key rules for evaluation:

1. The expression is always valid and properly formatted
2. Ternary expressions are right-associative, meaning they group from right to left
3. The final result will always be a single character: either a digit ('0'-'9'), 'T', or 'F'

For example:

• "T?2:3" evaluates to "2" (since T is true, take the first value after ?)
• "F?1:T?4:5" evaluates to "4" (F is false, so take the part after :, which is "T?4:5", and T is true, so take "4")
• "T?T?F:5:3" evaluates to "F" (T is true, so evaluate "T?F:5", and since T is true, the result is "F")

The solution uses a stack-based approach, processing the expression from right to left. When encountering a '?', it pops values from the stack and decides which one to keep based on whether the condition character is 'T' or 'F'.

Intuition

The key insight is recognizing that ternary expressions naturally form a tree-like structure where each ? represents a decision point. Since these expressions are right-associative, we need to evaluate from the innermost (rightmost) expressions first.

Why process from right to left? Consider the expression "T?2:F?3:4". If we try to process left to right, when we see T?2:, we don't know what comes after the : - it could be a simple value or another nested expression. However, if we process right to left, we can build up the result step by step from the leaves of the expression tree.

The stack naturally handles this evaluation order. As we traverse the string backwards:

• Regular characters (digits, 'T', 'F') are potential values that get pushed onto the stack
• The : separator is just a delimiter we can skip
• The ? operator triggers an evaluation - it means we've collected both branches of a ternary expression

When we encounter a ?, we know that:

1. The character immediately before ? is the condition
2. The top of the stack contains the "false" branch (what comes after :)
3. The second item on the stack contains the "true" branch (what comes between ? and :)

By popping these two values and keeping only the appropriate one based on the condition, we effectively evaluate one ternary expression and replace it with its result. This process continues until we've evaluated the entire expression, leaving just the final answer on the stack.

This approach elegantly handles nested expressions because inner expressions get evaluated first (being rightmost), and their results become the operands for outer expressions.

Solution Approach

The solution uses a stack-based approach with right-to-left traversal to evaluate the ternary expression.

Implementation Details:

1. Initialize Data Structures:

   • Create an empty stack stk to store intermediate values
   • Use a boolean flag cond to track when we need to evaluate a ternary operation

2. Traverse the Expression Backwards:

   for c in expression[::-1]:

   We iterate through each character from right to left using Python's slice notation [::-1].

3. Process Each Character:

   • Skip colons: When we encounter ':', we simply continue to the next iteration as it's just a separator

   if c == ':':
       continue

   • Mark ternary evaluation: When we see '?', set the cond flag to True, indicating the next character will be a condition

   if c == '?':
       cond = True

   • Handle conditions and values:
     • If cond is True, the current character is a condition ('T' or 'F')
       • If condition is 'T': Pop two values from stack, keep the first one (true branch)
       • If condition is 'F': Pop two values from stack, keep the second one (false branch)
       • Reset cond to False after evaluation
     • If cond is False, the current character is a value - push it onto the stack

   if cond:
       if c == 'T':
           x = stk.pop()  # Get true branch
           stk.pop()      # Discard false branch
           stk.append(x)  # Keep true branch
       else:
           stk.pop()      # Discard true branch (keep false branch on stack)
       cond = False
   else:
       stk.append(c)      # Push value onto stack

4. Return Result: After processing all characters, the stack contains exactly one element - the final result

   return stk[0]

Example Walkthrough: For expression "T?2:3"

• Start from right: '3' → push to stack: ['3']
• Next: ':' → skip
• Next: '2' → push to stack: ['3', '2']
• Next: '?' → set cond = True
• Next: 'T' with cond = True → pop '2', pop '3', push back '2': ['2']
• Result: '2'

This algorithm has O(n) time complexity and O(n) space complexity, where n is the length of the expression.

Example Walkthrough

Let's walk through the expression "F?1:T?4:5" step by step using the stack-based approach:

Initial Setup:

• Expression: "F?1:T?4:5"
• Stack: []
• cond: False

Processing from right to left:

1. Character: '5'

   • cond is False, so push '5' onto stack
   • Stack: ['5']

2. Character: ':'

   • Skip (it's just a separator)
   • Stack: ['5']

3. Character: '4'

   • cond is False, so push '4' onto stack
   • Stack: ['5', '4']

4. Character: '?'

   • Set cond = True (next character will be a condition)
   • Stack: ['5', '4']

5. Character: 'T'

   • cond is True, so this is a condition
   • Since it's 'T' (true):
     • Pop '4' (true branch)
     • Pop '5' (false branch)
     • Push back '4' (we keep the true branch)
   • Reset cond = False
   • Stack: ['4']

6. Character: ':'

   • Skip
   • Stack: ['4']

7. Character: '1'

   • cond is False, so push '1' onto stack
   • Stack: ['4', '1']

8. Character: '?'

   • Set cond = True
   • Stack: ['4', '1']

9. Character: 'F'

   • cond is True, so this is a condition
   • Since it's 'F' (false):
     • Pop '1' (true branch) and discard it
     • Keep '4' (false branch) on the stack
   • Reset cond = False
   • Stack: ['4']

Final Result: The stack contains ['4'], so the answer is '4'.

This demonstrates how the algorithm evaluates nested expressions from the inside out, with the rightmost ternary expression "T?4:5" being evaluated first to produce '4', which then becomes the false branch of the outer expression "F?1:4".

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the expression string.

The algorithm iterates through the expression string once in reverse order (from right to left). For each character in the string, it performs constant-time operations:

• Checking if the character is ':', '?', 'T', or 'F'
• Stack push and pop operations, which are O(1)

Since we visit each character exactly once and perform O(1) operations for each character, the overall time complexity is O(n).

Space Complexity: O(n) where n is the length of the expression string.

The space complexity is determined by the stack stk. In the worst case, when processing the expression from right to left, we might push multiple characters onto the stack before encountering '?' operators that trigger pop operations. The maximum number of elements that can be on the stack at any time is bounded by the number of operands in the expression, which is proportional to the length of the expression string. Therefore, the space complexity is O(n).

Common Pitfalls

1. Incorrect Evaluation Order Due to Left-to-Right Processing

One of the most common mistakes is attempting to process the expression from left to right instead of right to left. Since ternary operators are right-associative, processing from left to right would require complex lookahead logic to determine where each ternary expression ends.

Incorrect Approach:

# This won't work correctly for nested expressions
stack = []
i = 0
while i < len(expression):
    if expression[i] == '?':
        # How do we know where the matching ':' is?
        # This becomes complex with nested ternaries
        ...

Solution: Always traverse from right to left as shown in the correct implementation. This naturally handles the right-associative nature of the operator.

2. Mishandling the Stack Pop Order

When evaluating a condition, the order in which values are popped from the stack matters. Since we're processing right-to-left, the false branch is pushed first, then the true branch.

Common Mistake:

if char == 'T':
    false_value = stack.pop()  # Wrong! This is actually the true value
    true_value = stack.pop()   # Wrong! This is actually the false value
    stack.append(true_value)

Correct Order:

if char == 'T':
    true_value = stack.pop()   # First pop gets the true branch
    false_value = stack.pop()  # Second pop gets the false branch
    stack.append(true_value)

3. Forgetting to Reset the Condition Flag

After processing a condition, the is_condition_next flag must be reset to False. Forgetting this causes subsequent characters to be incorrectly treated as conditions.

Bug Example:

if is_condition_next:
    if char == 'T':
        true_value = stack.pop()
        stack.pop()
        stack.append(true_value)
    # Missing: is_condition_next = False
    # This causes the next character to also be treated as a condition

4. Not Handling Both Branches of the Condition

When the condition is 'F', some might forget that we still need to pop both values but keep the false branch.

Incomplete Implementation:

if char == 'T':
    true_value = stack.pop()
    stack.pop()
    stack.append(true_value)
else:
    # Wrong: Just leaving the stack as-is
    pass  # This doesn't remove the unwanted true branch

Correct Implementation:

if char == 'T':
    true_value = stack.pop()
    stack.pop()
    stack.append(true_value)
else:
    stack.pop()  # Remove true branch
    # The false branch remains on top of the stack

5. Edge Case: Single Character Expression

While the algorithm handles this correctly, it's worth noting that expressions can be as simple as a single character like "5" or "T". Make sure your solution doesn't assume there will always be a ternary operator.

Test Cases to Verify:

• "5" should return "5"
• "T" should return "T"
• "F" should return "F"

The stack-based approach naturally handles these cases since non-condition characters are simply pushed to the stack and returned.