# 439 Ternary Expression Parser

## 439. [Ternary Expression Parser](https://leetcode.com/problems/ternary-expression-parser/description/)

## 1. Question

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:**

```
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"
```

## 2. Implementation

**(1) Stack**

思路：这是当年面Pocket Gem的电面题，当时的我完全懵逼无从入手...这道题既可以用递归，也可以用stack解。如果用stack的话，需要从后往前扫，这样的好处是当我们遇到'?'前面的character(T 或者 F)，我们可以知道该保留‘?’后面的哪个expression

```java
class Solution {
    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();

                char firstVal = stack.pop();
                stack.pop();
                char secondVal = stack.pop();

                if (c == 'T') {
                    stack.push(firstVal);
                }
                else {
                    stack.push(secondVal);
                }
            }
            else {
                stack.push(c);
            }
        }
        return String.valueOf(stack.pop());
    }
}
```

**(2) DFS**

```java
class Solution {
    public String parseTernary(String expression) {
        int len = expression.length();

        if (len == 1) {
            return expression;
        }

        int count = 0;
        for (int i = 0; i < len; i++) {
            if (expression.charAt(i) == '?') {
                ++count;
            }
            else if (expression.charAt(i) == ':') {
                --count;

                // When the number of '?' matches with ':', we get a valid expression
                if (count == 0) {
                    if (expression.charAt(0) == 'T') {
                        // Get the expression before ':', skip 'T' and '?' at the beginning
                        return parseTernary(expression.substring(2, i));
                    } 
                    else {
                        // Get the expression after ':'
                        return parseTernary(expression.substring(i + 1));
                    }
                }
            }
        }
        return "";
    }
}
```

## 3. Time & Space Complexity

Stack: 时间复杂度O(n), 空间复杂度O(n)

DFS: 时间复杂度O(n), 空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/stack/439.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.