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.

Example 1:

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

Example 2:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
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"

Recursion

一个公式由3部分组成 <bool>?<left>:<right>, bool值只能为T或F, left或right可以为子公式或是单一的值. 所以只要能够正确的划分这三个部分, 就能用递归来处理.

这里我们发现?和:是成对出现的, 用一个flag来计数, 遇到?加1, 遇到:减一, 当flag == 0的时候, 说明正好为left和right的分界.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String parseTernary(String expression) {
    for (int i = 0; i < expression.length(); i++) {
        if (expression.charAt(i) == '?') {
            int flag = 1;
            for (int j = i + 1; j < expression.length(); j++) {
                if (expression.charAt(j) == '?')
                    flag++;
                if (expression.charAt(j) == ':')
                    flag--;
                if (flag == 0) {
                    if (expression.charAt(i - 1) == 'T')
                        return parseTernary(expression.substring(i + 1, j));
                    else
                        return parseTernary(expression.substring(j + 1, expression.length()));
                }
            }
        }
    }
    return expression;
}

Stack

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

Ref: https://discuss.leetcode.com/topic/64409/very-easy-1-pass-stack-solution-in-java-no-string-concat