Ternary Expression Parser
Problem
Given a string representing arbitrarily nested 'T?...:...' ternary expressions, return the result. Operands are digits 0–9 or T/F.
expr = "T?2:3""2"def parse_ternary(expr):
stack = []
for ch in reversed(expr):
if stack and stack[-1] == "?":
stack.pop() # ?
t = stack.pop()
stack.pop() # :
f = stack.pop()
stack.append(t if ch == "T" else f)
else:
stack.append(ch)
return stack[-1]function parseTernary(expr) {
const stack = [];
for (let i = expr.length - 1; i >= 0; i--) {
const ch = expr[i];
if (stack.length && stack[stack.length - 1] === "?") {
stack.pop();
const t = stack.pop();
stack.pop();
const f = stack.pop();
stack.push(ch === "T" ? t : f);
} else {
stack.push(ch);
}
}
return stack[stack.length - 1];
}class Solution {
public String parseTernary(String expr) {
Deque<Character> stack = new ArrayDeque<>();
for (int i = expr.length() - 1; i >= 0; i--) {
char ch = expr.charAt(i);
if (!stack.isEmpty() && stack.peek() == '?') {
stack.pop();
char t = stack.pop();
stack.pop();
char f = stack.pop();
stack.push(ch == 'T' ? t : f);
} else stack.push(ch);
}
return String.valueOf(stack.peek());
}
}string parseTernary(string expr) {
stack<char> st;
for (int i = expr.size() - 1; i >= 0; i--) {
char ch = expr[i];
if (!st.empty() && st.top() == '?') {
st.pop();
char t = st.top(); st.pop();
st.pop();
char f = st.top(); st.pop();
st.push(ch == 'T' ? t : f);
} else st.push(ch);
}
return string(1, st.top());
}Explanation
Ternary expressions like a?b:c are right-associative, meaning the rightmost ? resolves first. The trick is to scan the string right to left using a stack, so the pieces a ? needs are always sitting right on top, already resolved.
As we move backwards, most characters just get pushed. But when the current character is the condition (the next top of the stack is ?), we have a complete ternary ready: pop the ?, pop the true-value t, pop the :, pop the false-value f, then push t if the condition is T, else f.
Why right-to-left? Because the value immediately after a ? in the text ends up on top of the stack by the time we reach that ?'s condition. Nested expressions to the right have already collapsed into a single value, so each ? always sees clean operands.
Example: expr = "T?2:3". Scanning backward we push 3, :, 2, ?. Now we reach T; the top is ?, so we pop the four pieces and, because the condition is T, push 2. The stack's remaining value is "2".
Whatever single value is left on the stack at the end is the answer.