Ternary Expression Parser - Solution & Explanation

Problem Overview: The input is a string representing a nested ternary expression such as T?2:3 or F?1:T?4:5. Each condition is either T or F. The expression follows right-to-left associativity, meaning nested ternaries are evaluated from the rightmost pair first. Your goal is to return the final evaluated character.

Approach 1: Recursive Parsing (O(n) time, O(n) space)

The recursive approach directly models how ternary expressions are evaluated. Start from the left and identify the condition before the first ?. Then locate the matching : that pairs with that question mark while accounting for nested ternaries. If the condition is T, recursively evaluate the true branch; otherwise evaluate the false branch. Each recursive call processes a smaller substring until a single character remains. This approach is intuitive if you are comfortable with recursion, but handling nested ? and : pairs requires careful counting.

Approach 2: Stack with Right-to-Left Traversal (O(n) time, O(n) space)

The optimal approach scans the string from right to left using a stack. Because ternary expressions associate from right to left, reversing the evaluation order naturally exposes the smallest sub-expressions first. Push characters onto the stack while iterating backward. When the top of the stack forms the pattern value1 : value2 and the current character is a condition (T or F) followed by ?, resolve the ternary immediately. Pop the two values and push back the chosen result depending on the condition.

This works because every time you encounter a condition during the backward scan, the corresponding true and false results have already been processed and sit on the stack. The algorithm repeatedly collapses ternary segments until only one value remains. The stack operations are constant time, so the entire expression is processed in a single linear pass.

The implementation is compact and avoids substring creation. It also aligns well with problems involving expression evaluation using string traversal and stacks.

Recommended for interviews: The right-to-left stack approach. It runs in linear time O(n), uses predictable stack operations, and avoids complicated substring parsing. Interviewers often accept the recursive solution, but the stack-based evaluation demonstrates stronger control over expression parsing and space management.