We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Ternary Expression Parser

Number: 439

Difficulty: Medium

Paid? Yes

Companies: Snap

Problem Description

Given a string expression representing arbitrarily nested ternary expressions, evaluate the expression and return its result. The expression contains digits (always one-digit), the characters 'T' and 'F' representing true and false, and the symbols '?' and ':' for the ternary operator. Ternary expressions group right-to-left, meaning that an expression like "T?T?F:5:3" is evaluated as "T ? (T ? F : 5) : 3".

Key Insights

  • The ternary operator groups right-to-left. This property can be exploited by processing the string from the end to the beginning.
  • Using a stack allows us to "collapse" nested ternary expressions as soon as their three components (condition, true branch, false branch) are available.
  • An iterative approach is efficient and avoids building an explicit syntax tree for the expression.
  • The condition is not stored on the stack; instead, it is encountered immediately preceding the '?' operator when traversing backwards.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the expression, as we process each character exactly once.
Space Complexity: O(n), due to the use of a stack for storing characters during evaluation.

Solution

The solution uses an iterative approach with a stack. We traverse the expression string from right to left. For every character:

  • If it is a digit, 'T', or 'F' (and not a ':' or part of a pending operator), we push it onto the stack.
  • When we encounter a '?' character, we know that the next available items on the stack represent the true and false results of the ternary expression. We then skip the ':' separator that comes between them.
  • We then use the condition (the character immediately preceding the '?') to choose which result to push back on the stack. This method “collapses” each ternary expression into a single result, and by the time we finish traversing the string, the stack contains the final evaluated result.

Code Solutions

def parseTernary(expression: str) -> str:
    # Initialize stack to hold characters/results during evaluation
    stack = []
    # Iterate backwards over the expression
    i = len(expression) - 1
    while i >= 0:
        if expression[i] == '?':
            # Pop the true and false parts from the stack
            true_expr = stack.pop()
            false_expr = stack.pop()
            i -= 1  # Move to the condition character
            # Choose based on the condition
            if expression[i] == 'T':
                stack.append(true_expr)
            else:
                stack.append(false_expr)
        elif expression[i] == ':':
            # Skip the colon as it is only a separator
            pass
        else:
            # Push digits, 'T', and 'F' onto stack as is
            stack.append(expression[i])
        i -= 1  # Move to the next character
    return stack[-1]

# Example usage:
print(parseTernary("T?2:3"))  # Expected output "2"
← Back to All Questions