Skip to main content
Talentd

Ternary Expression Parser - Solution & Explanation

MediumPremiumFree on FleetCodeStringStackRecursion5 min readAsked at: Snapchat
Practice this problem

Problem Statement

Given a string expression representing arbitrarily nested ternary expressions, evaluate the expression, and return the result of it.

You can always assume that the given expression is valid and only contains digits, '?', ':', 'T', and 'F' where 'T' is true and 'F' is false. All the numbers in the expression are one-digit numbers (i.e., in the range [0, 9]).

The conditional expressions group right-to-left (as usual in most languages), and the result of the expression will always evaluate to either a digit, 'T' or 'F'.

 

Example 1:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: expression = "F?1:T?4:5"
Output: "4"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
"(F ? 1 : (T ? 4 : 5))" --> "(F ? 1 : 4)" --> "4"
or "(F ? 1 : (T ? 4 : 5))" --> "(T ? 4 : 5)" --> "4"

Example 3:

Input: expression = "T?T?F:5:3"
Output: "F"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 3)" --> "F"
"(T ? (T ? F : 5) : 3)" --> "(T ? F : 5)" --> "F"

 

Constraints:

  • 5 <= expression.length <= 104
  • expression consists of digits, 'T', 'F', '?', and ':'.
  • It is guaranteed that expression is a valid ternary expression and that each number is a one-digit number.

Approach Overview

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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive ParsingO(n)O(n)When modeling the ternary structure directly using recursion
Stack with Right-to-Left TraversalO(n)O(n)Best general solution for interviews and large inputs
Substring SimulationO(n^2)O(n)Simple to reason about but inefficient due to repeated string slicing

Video Solution

439. Ternary Expression Parser - Week 4/5 Leetcode July Challenge • Programming Live with Larry • 427 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Ternary Expression Parser easy or hard?
Ternary Expression Parser is generally classified as a medium difficulty problem. The challenge comes from understanding that ternary expressions associate from right to left and designing a parsing strategy that correctly evaluates nested conditions.
Ternary Expression Parser Python/Java solution
Python, Java, C++, and Go implementations typically follow the same stack strategy. Iterate from the end of the string, push characters onto a stack, and when encountering a condition with '?', resolve the two candidate values and push the chosen result back.
How to solve Ternary Expression Parser in O(n)?
Traverse the expression from right to left and maintain a stack of characters. When encountering a condition ('T' or 'F') followed by '?', pop the true and false values from the stack and push back the selected result. This collapses each ternary segment exactly once, producing an O(n) solution.
What is the best approach for Ternary Expression Parser?
The stack-based right-to-left traversal is the most reliable approach. Scan the string from the end, push characters onto a stack, and resolve ternary segments whenever you see a condition followed by '?'. This evaluates nested expressions in one pass with O(n) time and O(n) space.
Is Ternary Expression Parser asked at Google/Amazon/Meta?
Ternary expression evaluation problems appear in interviews at large tech companies including Google, Amazon, and Meta because they test stack usage, parsing logic, and understanding of expression associativity. Variants also appear in compiler or interpreter style interview questions.
What data structure is used in Ternary Expression Parser?
A stack is the primary data structure used in the optimal solution. It helps evaluate nested ternary expressions while scanning the string from right to left. Recursion can also be used, which implicitly relies on the call stack.
What is the time complexity of Ternary Expression Parser?
The optimal solutions run in O(n) time where n is the length of the expression. Each character is processed once during the right-to-left scan and stack operations are constant time. Space complexity is O(n) due to the stack or recursion call stack.

Ready to solve this problem?

Practice Ternary Expression Parser with our built-in code editor and test cases.

Practice on FleetCode
Previous

Mini Parser

Next

Parse Lisp Expression