⚡Flashcard Drill➔
NeetCode #363LC-439MediumStackNC Algo100
← Back to All Problems

#363 · #439 · Ternary Expression Parser(三元表达式解析器)

📌 Problem Statement & Constraints

Given a string expression representing a ternary expression, evaluate it and return the result. The expression is always valid and consists of T, F, ?, :, digits and letters. Constraints: 1 <= expression.length <= 10^4.

💡 Core Algorithmic Approaches

  1. Scan the expression from right to left with a stack.
  2. Push every character. When the top of the stack is ?, the current character is the condition, so the next three stack entries are the true-branch value, the : and the false-branch value.
  3. Pop them, push the selected branch, and continue.
  4. Right-to-left processing guarantees that nested ternaries are already resolved when their condition is reached.

💻 Benchmark Python3 Implementation

class Solution:
    def parseTernary(self, expression: str) -> str:
        st = []
        for ch in reversed(expression):
            if st and st[-1] == "?":       # ch is the condition
                st.pop()                   # remove '?'
                first = st.pop()           # value when the condition is true
                st.pop()                   # remove ':'
                second = st.pop()          # value when the condition is false
                st.append(first if ch == "T" else second)
            else:
                st.append(ch)
        return st[-1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Scanning left to right: nested ternaries cannot be resolved without lookahead in that direction.
  • Popping in the wrong order: the top after ? is the true-branch value, then :, then the false-branch value.
  • Forgetting to pop the ?: the stack would grow incorrectly.
  • Treating multi-character results specially: values are single characters here, so no parsing is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems