# 7-line O(N) C++ solution using stack scanning backward (detailed explanation)

• Key observation: Ternary expression is defined as grouping from right to left, so the sub-expression of first '?' from right is always calculated first.

Simply using a `stack<char> chars` to scan string `expression` from right to left:

1. if encounter a non `'?'` char, just push it into stack;
2. if encounter a `'?'` at index `i`, e.g., in string fraction `"...T?5:8..."`, we must have
• char at next index i-1 `expression[i-1] = 'T'` is the condition char;
• char at top of stack `chars.top = '5'` is the first value in current ternary expression;
• char at 3rd top of stack `'8'` is the second value in current ternary expression.
Then we just pop out those chars, calculate the current ternary expression and push the result back to stack.
3. continue to next char in `expression` til its begining.
4. The final result must be the single char in the stack.
``````    string parseTernary(string expression) {
stack<char> chars;
for (auto i = expression.rbegin(); i != expression.rend(); ++i)
if (*i == '?') { // calculate ternary expression
char TF = *(++i), first = chars.top(), second = (chars.pop(),chars.pop(),chars.top());
chars.pop(); chars.push(TF == 'T'? first : second); // push result back into stack
} else chars.push(*i); // push other chars into stack
return string(1, chars.top());
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.