Ternary Expression Parser

How it works

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.

Steps

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.

Complexity

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

Where N is the length of expression

Things to watch for

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.

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

class Solution {
public:
    string parseTernary(string expression) {
        int i = 0;
        for ( ; i < expression.length(); ) {

            if (expression[i] != 'T' && expression[i] != 'F'
            || i == expression.length() - 1 || expression[i + 1] == ':') {
                break;
            }
            if (expression[i] == 'T') {
                i += 2;
            } else {
                int count;
                for (count = 1, i += 2; count != 0; i++) {
                    if (expression[i] == ':') {
                        count--;
                    } else if (expression[i] == '?') {
                        count++;
                    }
                }
            }
        }

        return expression.substr(i, 1);
    }
};