# 439. Ternary Expression Parser

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

```cpp
// Two Pass + Stack
string eval(const string& str) {
    if (str.length() != 5) return "";
    return str[0] == 'T' ? str.substr(2, 1) : str.substr(4);
}
string parseTernary(string expression) { // time: O(n); space: O(n)
    string res = expression;
    stack<int> st; // store positions of '?'
    for (int i = 0; i < expression.length(); ++i) {
        if (expression[i] == '?') st.push(i);
    }
    while (!st.empty()) {
        int t = st.top(); st.pop();
        res = res.substr(0, t - 1) + eval(res.substr(t - 1, 5)) + res.substr(t + 4);
    }
    return res;
}
```

```cpp
// Iteration with Stack
string parseTernary(string expression) { // time: O(n); space: O(n)
    stack<char> st;
    for (int i = expression.length() - 1; i >= 0; --i) {
        char c = expression[i];
        if (!st.empty() && st.top() == '?') {
            st.pop();
            char first = st.top(); st.pop();
            st.pop(); // skip ':'
            char second = st.top(); st.pop();
            st.push(c == 'T' ? first : second);
        } else {
            st.push(c);
        }
    }
    return string(1, st.top());
}
```

```cpp
// Bottom-Up Recursion
char helper(const string& expression, int& idx) { 
    char ch = expression[idx];
    if (idx == expression.length() - 1 || expression[idx + 1] == ':') {
        idx += 2; // skip ':'
        return ch;
    }
    idx += 2; // skip '?'
    char first = helper(expression, idx), second = helper(expression, idx);
    return ch == 'T' ? first : second;
}
string parseTernary(string expression) { // time: O(n); space: O(n)
    int idx = 0;
    return string(1, helper(expression, idx));
}
```


---

# 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://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dfs-and-bfs/439.-ternary-expression-parser.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.