class Solution {
public:
string parseTernary(string expression) {
}
};
439. 三元表达式解析器
给定一个表示任意嵌套三元表达式的字符串 expression ，求值并返回其结果。
你可以总是假设给定的表达式是有效的，并且只包含数字， '?' ， ':' ， 'T' 和 'F' ，其中 'T' 为真， 'F' 为假。表达式中的所有数字都是 一位 数(即在 [0,9] 范围内)。
条件表达式从右到左分组(大多数语言中都是这样)，表达式的结果总是为数字 'T' 或 'F' 。
示例 1：
输入： expression = "T?2:3" 输出： "2" 解释： 如果条件为真，结果为 2；否则，结果为 3。
示例 2：
输入： expression = "F?1:T?4:5" 输出： "4" 解释： 条件表达式自右向左结合。使用括号的话，相当于： "(F ? 1 : (T ? 4 : 5))" --> "(F ? 1 : 4)" --> "4" or "(F ? 1 : (T ? 4 : 5))" --> "(T ? 4 : 5)" --> "4"
示例 3：
输入： expression = "T?T?F:5:3" 输出： "F" 解释： 条件表达式自右向左结合。使用括号的话，相当于： "(T ? (T ? F : 5) : 3)" --> "(T ? F : 3)" --> "F" "(T ? (T ? F : 5) : 3)" --> "(T ? F : 5)" --> "F"
提示:
5 <= expression.length <= 104expression 由数字, 'T', 'F', '?' 和 ':' 组成原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-22 00:14:42
func parseTernary(expression string) string {
stack := []byte{}
for i := len(expression)-1; i >= 0; i-- {
if expression[i] == ':' {
continue
} else if expression[i] == '?' {
i--
if expression[i] == 'T' {
temp := stack[len(stack)-1]
stack = stack[:len(stack)-2] // 一定满足len(stack) == 2
stack = append(stack, temp)
} else {
stack = stack[:len(stack)-1]
}
} else {
stack = append(stack, expression[i])
}
}
return string(stack[0]) // 一定满足len(stack) == 1
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-22 00:14:21
func parseTernary(expression string) string {
idx := strings.Index(expression, "?")
if idx == -1 {
return expression
}
flag := 1
i := idx+1;
for ; i < len(expression); i++ {
if expression[i] == '?' {
flag++
} else if expression[i] == ':' {
flag--
}
if flag == 0 {
break;
}
}
if expression[:idx] == "T" {
return parseTernary(expression[idx+1:i])
} else {
return parseTernary(expression[i+1:])
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 7.3 MB, 提交时间: 2023-10-22 00:13:54
class Solution {
public:
string parseExp(const string& exp, int l, int r) {
if (l == r) return exp.substr(l, 1);
int n1 = 0;
int n2 = 0;
int i = l;
for (; i <= r; ++i) {
if (exp[i] == '?') {
++n1;
} else if (exp[i] == ':') {
++n2;
}
if (n1 > 0 && n1 == n2) {
break;
}
}
return (exp[l] == 'T') ? parseExp(exp, l + 2, i - 1) : parseExp(exp, i + 1, r);
}
string parseTernary(string expression) {
return parseExp(expression, 0, expression.size() - 1);
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 40.5 MB, 提交时间: 2023-10-22 00:13:34
class Solution {
public String parseTernary(String expression) {
int n = expression.length();
int checkLevel = 0;
for (int j = 1; j < n; j++) {
if (expression.charAt(j) == '?') checkLevel++;
if (expression.charAt(j) == ':') checkLevel--;
if (checkLevel == 0) return (expression.charAt(0) == 'T') ? parseTernary(expression.substring(2, j)) : parseTernary(expression.substring(j+1, n));
}
return expression;
}
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-22 00:13:16
class Solution:
def parseTernary(self, expression: str) -> str:
# 用来标记下一个遇到的字符是条件
is_condition = 0
stk = []
# 因为是从右至左结合,所以也从右至左遍历
for i in range(len(expression) - 1, -1, -1):
if expression[i] == ':':
continue
elif expression[i] == '?': # 标记下一个遇到的字符是条件
is_condition = 1
else:
if is_condition:
if expression[i] == 'T': # 说明栈中的第一个元素是结果, 但要把错误结果删掉
res = stk[-1]
stk.pop()
stk.pop()
stk.append(res)
else: # 说明栈中第二个元素是结果, 删掉栈顶元素即可
stk.pop()
is_condition = 0
else: # 当前扫描到的元素不是条件, 就是直接入栈
stk.append(expression[i])
return stk[-1]