1. Find Rightmost Atomic Expression

Intuition

A ternary expression like T?a:b consists of a condition (T or F), followed by ?, then the true branch, :, and the false branch. When expressions are nested, we can evaluate from the inside out.

The key insight is that the rightmost atomic expression (a simple B?E1:E2 where both E1 and E2 are single characters) can always be evaluated first without affecting the rest. By repeatedly finding and reducing these atomic expressions from right to left, we eventually collapse the entire expression to a single result.

Algorithm

  1. Define a helper to check if a 5-character substring is a valid atomic expression (form B?X:Y where B is T or F, and X, Y are digits or T/F).
  2. Define a helper to evaluate an atomic expression, returning X if B is T, otherwise Y.
  3. While the expression has more than one character:
    • Scan from the right to find the rightmost valid atomic expression.
    • Replace that 5-character substring with its evaluated single character result.
  4. Return the final single character.
class Solution:
    def parseTernary(self, expression: str) -> str:

        # Checks if the string s is a valid atomic expression
        def isValidAtomic(s):
            return s[0] in 'TF' and s[1] == '?' and s[2] in 'TF0123456789'\
                and s[3] == ':' and s[4] in 'TF0123456789'

        # Returns the value of the atomic expression
        def solveAtomic(s):
            return s[2] if s[0] == 'T' else s[4]

        # Reduce expression until we are left with a single character
        while len(expression) != 1:
            j = len(expression) - 1
            while not isValidAtomic(expression[j-4:j+1]):
                j -= 1
            expression = expression[:j-4] + \
                solveAtomic(expression[j-4:j+1]) + expression[j+1:]

        # Return the final character
        return expression

Time & Space Complexity

  • Time complexity: O(N2)O(N^2)
  • Space complexity: O(N)O(N)

Where NN is the length of expression

2. Reverse Polish Notation

Intuition

Instead of validating the full atomic expression pattern, we can simplify by just finding the rightmost ? operator. The character immediately before ? is the condition, and the characters at positions +1 and +3 relative to ? are the true and false values respectively.

This works because the rightmost ? is always part of the innermost (deepest nested) ternary that can be evaluated. After each reduction, the next rightmost ? becomes evaluable.

Algorithm

  1. While the expression has more than one character:
    • Find the index of the rightmost ? by scanning from the end.
    • The condition is at index questionMarkIndex - 1.
    • If the condition is T, take the character at questionMarkIndex + 1.
    • Otherwise, take the character at questionMarkIndex + 3.
    • Replace the 5-character ternary with the resulting single character.
  2. Return the final character.
class Solution:
    def parseTernary(self, expression: str) -> str:

        # Reduce expression until we are left with a single character
        while len(expression) != 1:
            questionMarkIndex = len(expression) - 1
            while expression[questionMarkIndex] != '?':
                questionMarkIndex -= 1

            # Find the value of the expression.
            if expression[questionMarkIndex - 1] == 'T':
                value = expression[questionMarkIndex + 1]
            else:
                value = expression[questionMarkIndex + 3]

            # Replace the expression with the value
            expression = expression[:questionMarkIndex - 1] + value\
                + expression[questionMarkIndex + 4:]

        # Return the final character
        return expression

Time & Space Complexity

  • Time complexity: O(N2)O(N^2)
  • Space complexity: O(N)O(N)

Where NN is the length of expression

3. Reverse Polish Notation using Stack

Intuition

Processing from right to left with a stack eliminates the need for string manipulation. When we encounter a ?, we know the stack contains the true value, :, and false value (in that order from top). The current character is the condition, so we can immediately resolve which value to keep.

This approach processes each character exactly once and avoids expensive substring operations, achieving linear time complexity.

Algorithm

  1. Initialize an empty stack.
  2. Traverse the expression from right to left:
    • If the stack's top is ?:
      • Pop ?, pop the true value, pop :, pop the false value.
      • Push the true value if the current character is T, otherwise push the false value.
    • Otherwise, push the current character onto the stack.
  3. Return the single character remaining in the stack.
class Solution:
    def parseTernary(self, expression: str) -> str:
        
        # Initialize a stack
        stack = []
        
        # Traverse the expression from right to left
        for char in expression[::-1]:
            
            # If stack top is ?, then replace next four characters
            # with E1 or E2 depending on the value of B
            if stack and stack[-1] == '?':
                stack.pop()
                onTrue = stack.pop()
                stack.pop()
                onFalse = stack.pop()
                stack.append(onTrue if char == 'T' else onFalse)
            
            # Otherwise, push this character
            else:
                stack.append(char)
        
        # Return the final character
        return stack[0]

Time & Space Complexity

  • Time complexity: O(N)O(N)
  • Space complexity: O(N)O(N)

Where NN is the length of expression

4. Binary Tree

Intuition

A ternary expression naturally maps to a binary tree structure. Each condition becomes a node, with its true branch as the left child and false branch as the right child. Leaf nodes hold the final values (digits or T/F).

Once the tree is built, evaluating the expression is straightforward: start at the root and traverse left for T conditions, right for F conditions, until reaching a leaf.

Algorithm

  1. Build the binary tree recursively:
    • Create a node for the current character.
    • If the next character is ?, recursively build the left subtree (true branch) and right subtree (false branch).
    • Use a global index to track position in the expression.
  2. Traverse the tree from root:
    • If the current node is T, move to the left child.
    • If the current node is F, move to the right child.
    • Continue until reaching a leaf node.
  3. Return the leaf node's value.
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    def parseTernary(self, expression: str) -> str:
        
        # Global Index to Construct Binary Tree
        self.index = 0
        root = self.constructTree(expression)
        
        # Parse the binary tree till we reach the leaf node
        while root.left and root.right:
            if root.val == 'T':
                root = root.left
            else:
                root = root.right
        
        return root.val

    def constructTree(self, expression):
        
        # Storing current character of expression
        root = TreeNode(expression[self.index])

        # If the last character of expression, return
        if self.index == len(expression) - 1:
            return root
        
        # Check the next character
        self.index += 1
        if expression[self.index] == '?':
            self.index += 1
            root.left = self.constructTree(expression)
            self.index += 1
            root.right = self.constructTree(expression)
            
        return root

Time & Space Complexity

  • Time complexity: O(N)O(N)
  • Space complexity: O(N)O(N)

Where NN is the length of expression

5. Recursion

Intuition

We can evaluate the expression top-down by recursively processing subexpressions. The key challenge is finding where the true branch ends and the false branch begins, since branches can contain nested ternaries.

By counting ? and : characters, we can find the matching : for any given ?. Each ? increments a counter, each : decrements it. When the counter reaches zero, we have found the boundary between the true and false branches.

Algorithm

  1. Define a recursive function solve(i, j) that evaluates the expression between indices i and j.
  2. Base case: if i == j, return the single character.
  3. Find the first ? after index i.
  4. Find the matching : by tracking nested ternaries:
    • Start with count = 1 after the ?.
    • Increment count for each ?, decrement for each :.
    • Stop when count reaches 0.
  5. If the condition at index i is T, recurse on the true branch.
  6. Otherwise, recurse on the false branch.
  7. Return the result of solve(0, len(expression) - 1).
class Solution:
    def parseTernary(self, expression: str) -> str:

        # To analyze the expression between two indices
        def solve(i, j):

            # If expression is a single character, return it
            if i == j:
                return expression[i]

            # Find the index of ?
            questionMarkIndex = i
            while expression[questionMarkIndex] != '?':
                questionMarkIndex += 1

            # Find one index after corresponding :
            aheadColonIndex = questionMarkIndex + 1
            count = 1
            while count != 0:
                if expression[aheadColonIndex] == '?':
                    count += 1
                elif expression[aheadColonIndex] == ':':
                    count -= 1
                aheadColonIndex += 1

            # Check the value of B and recursively solve
            if expression[i] == 'T':
                return solve(questionMarkIndex + 1, aheadColonIndex - 2)
            else:
                return solve(aheadColonIndex, j)

        # Solve for the entire expression
        return solve(0, len(expression) - 1)

Time & Space Complexity

  • Time complexity: O(N2)O(N^2)
  • Space complexity: O(N)O(N)

Where NN is the length of expression

6. Constant Space Solution

Intuition

We can evaluate the expression iteratively without recursion or extra space by simulating the evaluation process directly. Starting from the beginning, we repeatedly decide whether to take the true or false branch based on each condition.

When the condition is T, we simply skip past the ? to the true branch. When it is F, we must skip the entire true branch (which may contain nested ternaries) by counting ? and : to find where the false branch starts.

Algorithm

  1. Initialize index i = 0.
  2. Loop while i is within bounds:
    • If the current character is not T or F, or we have reached the end, or the next character is :, we have found the result. Return it.
    • If the condition is T, skip to i + 2 (start of true branch).
    • If the condition is F:
      • Skip to i + 2 and use a counter starting at 1.
      • Increment counter for ?, decrement for :.
      • Stop when counter reaches 0; we are now at the false branch.
  3. Return the character at position i.
class Solution:
    def parseTernary(self, expression: str) -> str:
        i = 0
        while True:

            if expression[i] not in 'TF' or i == len(expression) - 1\
            or expression[i + 1] == ':':
                return expression[i]
            if expression[i] == 'T':
                i = i + 2
            else:
                count = 1
                i = i + 2
                while count != 0:
                    if expression[i] == ':':
                        count -= 1
                    elif expression[i] == '?':
                        count += 1
                    i += 1

Time & Space Complexity

  • Time complexity: O(N)O(N)
  • Space complexity: O(1)O(1)

Where NN is the length of expression

Common Pitfalls

Evaluating Left-to-Right Instead of Right-to-Left

A common mistake is trying to evaluate the expression from left to right. Ternary expressions are right-associative, meaning T?T?1:2:3 should be parsed as T?(T?1:2):3, not (T?T?1:2):3. Processing from the right ensures nested expressions are resolved correctly before their parent expressions.

Incorrectly Matching ? with :

When expressions are deeply nested, finding the matching : for a given ? is tricky. Each ? must pair with exactly one :, but nested ternaries introduce additional ? and : characters. Use a counter that increments for ? and decrements for : to find the correct boundary between true and false branches.

Off-by-One Errors in Substring Extraction

The atomic expression pattern is exactly 5 characters (B?X:Y), and miscounting indices when extracting or replacing substrings leads to incorrect results. Be careful with inclusive vs exclusive bounds in substring operations, especially when the expression shrinks after each reduction.