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
- Scan the expression from right to left with a stack.
- 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. - Pop them, push the selected branch, and continue.
- 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.