Solution Explanation

This problem asks to evaluate a ternary expression string. The key is understanding that the expression is evaluated from right to left. We can solve this efficiently using a stack.

Approach

The algorithm iterates through the input string expression from right to left. The core logic revolves around handling three characters: ':', '?', and the operands ('T', 'F', or digits).

1. Initialization: A stack stk is used to store the operands and intermediate results. A boolean variable cond tracks whether we're currently inside a conditional expression (after a '?').

2. Iteration: The loop processes each character:

   • ':': This character is ignored because it's only a separator within the ternary structure.

   • '?': This indicates the start of a ternary operation. The cond flag is set to true.

   • Operands ('T', 'F', digits): If cond is true, we're dealing with the operands of a ternary expression.

     • If the operand is 'T', the true branch is selected: the top two elements are popped from the stack, the top element (the false branch) is discarded, and the next-to-top element (the true branch) is pushed back onto the stack.
     • If the operand is 'F', the false branch is selected: only the top element (the true branch) is popped from the stack.
     • Then cond is set back to false.

   • If cond is false, the current character is simply pushed onto the stack.

3. Result: After processing all characters, the stack will contain only the final result. This result is then returned.

Time and Space Complexity Analysis

Time Complexity: O(n), where n is the length of the input string. The algorithm iterates through the string once. Stack operations (push and pop) take constant time.

Space Complexity: O(n) in the worst case. The stack's maximum size can be proportional to the length of the input string if the nesting is deep. In the best case, the space complexity is O(1) if there is minimal nesting.

Code Explanation (Python)

The Python code directly implements this approach. The use of expression[::-1] efficiently reverses the string for right-to-left processing. The if cond: block handles the conditional logic based on the current character and the cond flag. The remaining code pushes or pops from the stack as described in the approach.

The Java, C++, and Go solutions are very similar in structure and logic, adapting the stack and string manipulation to their respective language features. The core algorithmic approach remains consistent across all the code examples.