> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dfs-and-bfs/439.-ternary-expression-parser.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dfs-and-bfs/439.-ternary-expression-parser.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.