Problem Explanation

Given a string representing a ternary expression, the problem requires us to evaluate the expression and return the result. The string uses the syntax of condition ? value if true : value if false.

Here, the conditions always use True (T) or False (F) and never digits. The value for 'if true' or 'if false' could be a digit, T, or F.

If there are nested cases, these are evaluated from right to left. If a nested ternary expression is encountered, the innermost expression is solved first, and then the next outer expression, and so on.

Example

Let's look at the example "T?T?F:5:3".

1. Interpreting the problem statement, it means "If True, then check if True then False else 5, else 3".
2. This transforms to "If True, then False, else 3" as "T?F:5" is solved.
3. And finally this gives "False" as "T?F:3" is solved.

Solution Approach

This problem is a classic recursion problem. Here is the step by step approach:

1. Parse the expression from start, if there is no nested ternary expression, return the value based on the condition.
2. If there is a nested ternary expression, recursively evaluate the innermost expression and replace it in the original ternary expression.
3. Keep doing this until you get the final result.

Python Solution

1
2python
3class Solution:
4    def parseTernary(self, expression: str) -> str:
5        stack = []
6        
7        for ch in reversed(expression):
8            if stack and stack[-1] == '?':
9                stack.pop() # Pop '?'
10                first = stack.pop()
11                stack.pop() # Pop ':'
12                second = stack.pop()
13                
14                if ch == 'T':
15                    stack.append(first)
16                else:
17                    stack.append(second)
18            else:
19                stack.append(ch)
20                
21        return stack[0]

Java Solution

1
2java
3public class Solution {
4    public String parseTernary(String expression) {
5        if (expression == null || expression.length() == 0) return "";
6        Stack<Character> stack = new Stack<Character>();
7
8        for (int i = expression.length() - 1; i >= 0; i--) {
9            char c = expression.charAt(i);
10            if (!stack.empty() && stack.peek() == '?') {
11
12                stack.pop(); // pop '?'
13                char first = stack.pop();
14                stack.pop(); // pop ':'
15                char second = stack.pop();
16
17                if (c == 'T') stack.push(first);
18                else stack.push(second);
19            } else {
20                stack.push(c);
21            }
22        }
23
24        return String.valueOf(stack.peek());
25    }
26}

Javascript Solution

1
2javascript
3var parseTernary = function(expression) {
4    let i = expression.length - 1 , stack = [];
5    while(i >= 0){
6        if(expression[i] == '?'){
7            --i;
8            if(expression[i] == 'T'){
9                stack.push(stack.pop(),stack.pop());
10            }
11            else{
12                stack.pop();
13            }
14            --i;
15        }
16        else if(expression[i] != ':'){
17            stack.push(expression[i]);
18        }
19        --i;
20    }
21    return stack.pop();
22};

C++ Solution

1
2cpp
3class Solution {
4public:
5    string parseTernary(string expression) {
6        string res = "";
7        stack<char> st;
8        for (int i = expression.size() - 1; i >= 0; --i) {
9            char c = expression[i];
10            if (!st.empty() && st.top() == '?') {
11                st.pop(); // pop '?'
12                char first = st.top(); st.pop();
13                st.pop(); // pop ':'
14                char second = st.top(); st.pop();
15                if (c == 'T') st.push(first);
16                else st.push(second);
17            } else {
18                st.push(c);
19            }
20        }
21        res += st.top(); st.pop();
22        return res;
23    }
24};

C# Solution

1
2c#
3public class Solution {
4    public string ParseTernary(string expression) {
5        Stack<char> stack = new Stack<char>();
6
7        for (int i = expression.Length - 1; i >= 0; i--) {
8            char c = expression[i];
9            if (stack.Count > 0 && stack.Peek() == '?') {
10                stack.Pop(); 
11                char first = stack.Pop();
12                stack.Pop(); 
13                char second = stack.Pop();
14                if (c == 'T') stack.Push(first);
15                else stack.Push(second);
16            } else {
17                stack.Push(c);
18            }
19        }
20        return Convert.ToString(stack.Peek());
21    }
22}

In all of the above solutions implemented in various languages, we iteratively scan the expression from right to left and use a stack to store the characters in the expression. Once we encounter a '?', we pop the '?' and and the next two characters and based on the condition (True or False) we push back the appropriate result. We then keep repeating this process until we reach the left end of the expression.# Summary

In summary, evaluating a ternary expression by handling nested conditions can be effectively solved using the stack data structure. The stack allows us to parse and evaluate the expression from right to left, ensuring that the innermost expressions are evaluated first. Then, based on each condition (True or False), we either take the 'if true' or 'if false' value. This process continues until we have parsed the entire expression and are left with our final result.

This classic recursion problem can be implemented using Python, Java, JavaScript, C++ and C#, as demonstrated above. In all of these implementations, the key strategy is to keep track of the previous and next elements in the expression with the help of a stack. Whenever a '?' is encountered, the stack pops the '?' and next two elements, evaluates the condition, and pushes back the appropriate value. This process is continued till we reach to the beginning of the expression. Notably, Python uses a list to mimic the behavior of stack, while Java, JavaScript and C# use their built-in stack data structures, and C++ uses STL stack.

Moving forward, this approach can also be applied to other programming problems that require dealing with nested conditions or recursively parsing through strings.