class Solution:
def parseTernary(self, expression: str) -> str:
stack = []
n = len(expression)
i = n - 1
while i >= 0:
c = expression[i]
if c == '?':
true_expr = stack.pop()
stack.pop() # Remove ':'
false_expr = stack.pop()
i -= 1
cond = expression[i]
if cond == 'T':
stack.append(true_expr)
else:
stack.append(false_expr)
elif c != ':':
stack.append(c)
i -= 1
return stack[-1]
class Solution {
public:
string parseTernary(string expression) {
stack<char> st;
int n = expression.size();
for (int i = n - 1; i >= 0; --i) {
char c = expression[i];
if (c == '?') {
char trueExpr = st.top(); st.pop();
st.pop(); // remove ':'
char falseExpr = st.top(); st.pop();
--i;
if (expression[i] == 'T') {
st.push(trueExpr);
} else {
st.push(falseExpr);
}
} else if (c != ':') {
st.push(c);
}
}
return string(1, st.top());
}
};
class Solution {
public String parseTernary(String expression) {
Stack<Character> stack = new Stack<>();
int n = expression.length();
for (int i = n - 1; i >= 0; --i) {
char c = expression.charAt(i);
if (c == '?') {
char trueExpr = stack.pop();
stack.pop(); // remove ':'
char falseExpr = stack.pop();
i--;
char cond = expression.charAt(i);
if (cond == 'T') {
stack.push(trueExpr);
} else {
stack.push(falseExpr);
}
} else if (c != ':') {
stack.push(c);
}
}
return stack.peek() + "";
}
}
var parseTernary = function(expression) {
let stack = [];
let n = expression.length;
let i = n - 1;
while (i >= 0) {
let c = expression[i];
if (c === '?') {
let trueExpr = stack.pop();
stack.pop(); // remove ':'
let falseExpr = stack.pop();
i--;
let cond = expression[i];
stack.push(cond === 'T' ? trueExpr : falseExpr);
} else if (c !== ':') {
stack.push(c);
}
i--;
}
return stack[stack.length - 1];
};
You are given a string expression representing a nested ternary expression. The ternary expression uses the format condition ? exprTrue : exprFalse, where condition is always either 'T' (true) or 'F' (false), and exprTrue and exprFalse can themselves be either a single character or another ternary expression.
Your task is to evaluate the expression and return the result as a single character string. You can assume the expression is always valid and properly nested. There is exactly one valid solution for each input, and you do not need to reuse any elements from the expression.
For example, given expression = "T?2:3", the output should be "2". For expression = "F?1:T?4:5", the output should be "4".
At first glance, parsing a ternary expression may seem complex due to its nested nature. A brute-force approach might involve recursively parsing the string, identifying the matching ? and : for each condition, and evaluating each subexpression. However, this can get tricky and inefficient as the nesting increases.
By observing that ternary expressions are evaluated from right to left (right associativity), we can simplify the process. Instead of searching for matching symbols or using recursion, we can process the string backwards and use a stack to keep track of intermediate results. This shift from recursion to using a stack (iterative approach) allows us to efficiently and cleanly handle nested expressions without complex string manipulation.
The optimal strategy is to process the expression from the end to the beginning, using a stack to handle subexpressions. Here's how we can break down the approach:
? or :, push it onto the stack.?, pop the top two results (which correspond to the true and false expressions), then check the condition just before the ?. Push the result of the ternary operation back onto the stack.:, skip it (it only serves as a separator).This method works efficiently because the stack always contains the next immediate result to be used in the ternary operation, and processing from right to left respects the right-associativity of ternary operators.
Let's walk through the example expression = "F?1:T?4:5" step by step:
Thus, the answer is '4'.
Brute-force approach: Recursively parsing and evaluating each subexpression may result in O(N^2) time complexity in the worst case, due to repeated substring operations and recursive calls.
Optimized stack approach: Each character is processed exactly once, and each operation on the stack is O(1). Thus, the overall time complexity is O(N), where N is the length of the expression. The space complexity is also O(N) in the worst case, due to the stack storing up to N/2 elements for deeply nested expressions.
The key insight for solving the Ternary Expression Parser problem is recognizing the right-associativity of ternary expressions and leveraging a stack to iteratively evaluate the expression from right to left. This approach avoids recursion and complex string manipulation, leading to a clean, efficient, and elegant O(N) solution. By processing each character once and using a stack to manage intermediate results, we can handle any valid ternary expression, no matter how deeply nested.