pg

PG-LC 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).

Input: “T?T?F:5:3”
Output: “F”


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string parseTernary(string expression) {
if(expression == NULL || expression.length() == 0)
return "";
stack<char> cstack;
int len = (int)expression.length();
for(int i = len-1; i >= 0; i--){
if(!cstack.empty() && cstack.top() == '?'){
cstack.pop();
char first = cstack.top(); cstack.pop();
cstack.pop();
char second = cstack.top(); cstack.pop();
if(expression[i] == 'T')
cstack.push(first);
else
cstack.push(second);
} else {
cstack.push(expression[i]);
}
}
return string(1, cstack.top());
}