Problem

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Note:

  1. The length of the given string is ≤ 10000.
  2. Each number will contain only one digit.
  3. The conditional expressions group right-to-left (as usual in most languages).
  4. The condition will always be either T or F. That is, the condition will never be a digit.
  5. The result of the expression will always evaluate to either a digit 0-9, T or F.

Examples

Example 1:

Input: "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: "F?1:T?4:5"
Output: "4"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"

Example 3:

Input:"T?T?F:5:3"
Output: "F"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"

Solution

Method 1 - Using Stack

To evaluate the ternary expressions considering the nested and right-to-left grouping nature of these operations, we use a stack to manage the evaluation process. By traversing the string from right to left, we can ensure that the deepest ternary operations are evaluated first, respecting the nested structure.

Here is the approach:

  1. Initialization:
    • Initialize a stack (stk) to keep track of the characters.
    • Use a boolean flag (cond) to identify when a ternary condition is being evaluated.
  2. Traversal:
    • Traverse the string from right to left.
    • Ignore the colon (:) characters as they are only separators in the ternary expression.
    • When encountering a question mark (?), set the cond flag to true.
    • For every other character:
      • If the cond flag is true:
        • Check the current character:
          • If it is T, pop the top element from the stack, skip the next top element (which is the :), and push the popped element back onto the stack.
          • If it is F, pop the next top element from the stack (discarding the next character, which is the correct branch to take for F).
        • Reset the cond flag to false.
      • Otherwise, simply push the character onto the stack.
  3. Result Extraction:
    • After the traversal, the stack will have the final evaluated result at the top, which is returned.

Code

C++
class Solution {
public:
    string parseTernary(string expression) {
        string stk;
        bool cond = false;
        reverse(expression.begin(), expression.end());
        for (char& c : expression) {
            if (c == ':') {
                continue;
            }
            if (c == '?') {
                cond = true;
            } else {
                if (cond) {
                    if (c == 'T') {
                        char x = stk.back();
                        stk.pop_back();
                        stk.pop_back();
                        stk.push_back(x);
                    } else {
                        stk.pop_back();
                    }
                    cond = false;
                } else {
                    stk.push_back(c);
                }
            }
        }
        return {stk[0]};
    }
};
Go
func parseTernary(expression string) string {
	stk := []byte{}
	cond := false
	for i := len(expression) - 1; i >= 0; i-- {
		c := expression[i]
		if c == ':' {
			continue
		}
		if c == '?' {
			cond = true
		} else {
			if cond {
				if c == 'T' {
					x := stk[len(stk)-1]
					stk = stk[:len(stk)-2]
					stk = append(stk, x)
				} else {
					stk = stk[:len(stk)-1]
				}
				cond = false
			} else {
				stk = append(stk, c)
			}
		}
	}
	return string(stk[0])
}
Java
class Solution {
    public String parseTernary(String expression) {
        Deque<Character> stk = new ArrayDeque<>();
        boolean cond = false;
        for (int i = expression.length() - 1; i >= 0; --i) {
            char c = expression.charAt(i);
            if (c == ':') {
                continue;
            }
            if (c == '?') {
                cond = true;
            } else {
                if (cond) {
                    if (c == 'T') {
                        char x = stk.pop();
                        stk.pop();
                        stk.push(x);
                    } else {
                        stk.pop();
                    }
                    cond = false;
                } else {
                    stk.push(c);
                }
            }
        }
        return String.valueOf(stk.peek());
    }
}
Python
class Solution:
    def parseTernary(self, expression: str) -> str:
        stk = []
        cond = False
        for c in expression[::-1]:
            if c == ':':
                continue
            if c == '?':
                cond = True
            else:
                if cond:
                    if c == 'T':
                        x = stk.pop()
                        stk.pop()
                        stk.append(x)
                    else:
                        stk.pop()
                    cond = False
                else:
                    stk.append(c)
        return stk[0]

…

Complexity

  • Time: O(n), where n is the length of the string. Each character is processed once.
  • Space: O(n), for storing the characters in the stack.