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:
- The length of the given string is ≤ 10000.
- Each number will contain only one digit.
- The conditional expressions group right-to-left (as usual in most languages).
- The condition will always be either
T
orF
. That is, the condition will never be a digit. - The result of the expression will always evaluate to either a digit
0-9
,T
orF
.
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"
[Thoughts]
从右往左扫,发现?号就处理掉,最后的结果就是。
[Code]
1: string parseTernary(string expression) {
2: int len = expression.size();
3:
4: if(len == 0) return expression;
5:
6: for(int i = len-1; i>=0; i--) {
7: if(expression[i] != '?') continue;
8:
9: int index = i;
10: char result;
11: if(expression[index-1] == 'T'){
12: result = expression[index+1];
13: }else {
14: result = expression[index+3];
15: }
16:
17: expression.erase(index -1, 5);
18: expression.insert(index-1, 1, result);
19: }
20: return expression;
21: }
No comments:
Post a Comment