LC439. 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).
Example:
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"
实现？：这个表达式，记录?和：的位置，利用count找到最外层的表达式，利用recursion一层一层操作。
public class Solution {
public String parseTernary(String expression) {
if(expression == null || expression.length() <= 1) return expression;
return search(expression.toCharArray(), 0, expression.length()-1) + "";
}
private char search(char[] arr, int begin, int end){
if(begin == end) return arr[begin];
int count = 0, pos = 0, i = begin;
for(i = begin; i <= end; i++){
if(arr[i] == '?') {
count++;
if(count == 1) pos = i - 1;
}else if(arr[i] == ':') {
count--;
if(count == 0){
break;
}
} // else
} // for
return arr[pos] == 'T'?search(arr, pos+2, i-1):search(arr, i+1, end);
}
}
O(n), O(1)