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

``````class Solution {
public:
string parseTernary(string expression) {
string res = expression;
stack<int> s;
for (int i = 0; i < expression.size(); ++i) {
if (expression[i] == '?') s.push(i);
}
while (!s.empty()) {
int t = s.top(); s.pop();
res = res.substr(0, t - 1) + eval(res.substr(t - 1, 5)) + res.substr(t + 4);
}
return res;
}
string eval(string str) {
if (str.size() != 5) return "";
return str[0] == 'T' ? str.substr(2, 1) : str.substr(4);
}
};
``````

``````class Solution {
public:
string parseTernary(string expression) {
stack<char> s;
for (int i = expression.size() - 1; i >= 0; --i) {
char c = expression[i];
if (!s.empty() && s.top() == '?') {
s.pop();
char first = s.top(); s.pop();
s.pop();
char second = s.top(); s.pop();
s.push(c == 'T' ? first : second);
} else {
s.push(c);
}
}
return string(1, s.top());
}
};
``````

``````class Solution {
public:
string parseTernary(string expression) {
string res = expression;
while (res.size() > 1) {
int i = res.find_last_of("?");
res = res.substr(0, i - 1) + string(1, res[i - 1] == 'T' ? res[i + 1] : res[i + 3]) + res.substr(i + 4);
}
return res;
}
};
``````

https://discuss.leetcode.com/topic/64389/easy-and-concise-5-lines-python-java-solution

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

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation