Ternary Expression Parser - Practice Coding Problems

Ternary Expression Parser - Problem

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

You can always assume that the given expression is valid and only contains digits '0'-'9', '?', ':', 'T' (true), and 'F' (false).

Note:

All 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)
The result will always evaluate to either a digit, 'T', or 'F'

Input & Output

Example 1 — Simple Ternary

$ Input: expression = "T?2:3"

› Output: "2"

💡 Note: Condition is T (true), so we return the true value which is '2'

Example 2 — Nested Ternary

$ Input: expression = "F?1:T?4:5"

› Output: "4"

💡 Note: Condition is F (false), so we evaluate T?4:5. T is true, so return '4'

Example 3 — Complex Nesting

$ Input: expression = "T?T?F?1:2:3:4"

› Output: "2"

💡 Note: T is true, so evaluate T?F?1:2:3. T is true, so evaluate F?1:2. F is false, so return '2'

Constraints

5 ≤ expression.length ≤ 10⁴
expression consists of digits, 'T', 'F', '?', and ':'
It is guaranteed that expression is a valid ternary expression
Each number in the expression is a one-digit number

Visualization

Tap to expand

Understanding the Visualization

Input Expression

T?2:F?3:1 - nested ternary with right-associativity

Parse Structure

T ? 2 : (F ? 3 : 1) - parentheses show precedence

Evaluate

T is true, so result is 2

Key Takeaway

🎯 Key Insight: Ternary expressions are right-associative, so we need to handle precedence correctly using stack or recursion

Asked in

f Facebook 8 G Google 5

The key insight is understanding that ternary expressions are right-associative. The optimal approach uses either a stack processing from right to left or recursive descent parsing. Both achieve O(n) time complexity by processing each character exactly once.

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Evaluation	O(n)	O(n)	Use a stack to parse the expression from right to left, handling the right-associative nature
Recursive Descent Parser	O(n)	O(d)	Use recursion to parse the expression by handling the ternary operator precedence correctly
Iterative String Replacement	O(n²)	O(n)	Repeatedly find and evaluate the simplest ternary expressions until only the result remains

Stack-Based Evaluation — Algorithm Steps

Step 1: Traverse expression from right to left
Step 2: Push operands onto stack
Step 3: When seeing ':', pop and evaluate ternary
Step 4: Push result back to stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Right to Left

Process expression from right to left

Stack Operations

Push values, evaluate on ':'

Final Result

Last remaining element is answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* expression) {
    int len = strlen(expression);
    char* stack = malloc(len);
    int top = -1;
    int i = len - 1;
    
    while (i >= 0) {
        char ch = expression[i];
        if (ch == ':') {
            // We have a complete ternary, evaluate it
            char falseVal = stack[top--];
            char trueVal = stack[top--];
            i--; // Skip '?'
            char condition = expression[i];
            char result = condition != 'F' ? trueVal : falseVal;
            stack[++top] = result;
        } else if (ch != '?') {
            stack[++top] = ch;
        }
        i--;
    }
    
    char* result = malloc(2);
    result[0] = stack[0];
    result[1] = '\0';
    free(stack);
    return result;
}

int main() {
    char expression[1000];
    fgets(expression, sizeof(expression), stdin);
    expression[strcspn(expression, "\n")] = 0;
    
    char* result = solution(expression);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the expression with constant time stack operations

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n/2 elements in the worst case

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Evaluation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler