数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++三元表达式解析器
假设我们有一个字符串，表示任意嵌套的三元表达式，我们需要计算表达式的结果。我们可以始终假设给定的表达式是有效的，并且仅包含数字 0-9、?、:、T 和 F 这几个字符。（这里 T 和 F 分别代表 True 和 False）。有一些属性：
给定字符串的长度必须小于或等于 10000。
每个数字只包含一位。
条件表达式从右到左分组。
条件总是 T 或 F。因此，条件永远不会是数字。
表达式的结果将始终计算为数字 0-9、T 或 F 之一。
例如，如果输入类似于“F?1:T?4:5”，则输出将为 4，因为它将解析最右边的表达式“T?4:5”，它将返回 4，然后主表达式将变为“F?1:4”，因此返回值为 4。
为了解决这个问题，我们将遵循以下步骤：
ret := 一个空字符串，n := s 的大小，创建一个栈 st
for I in range n – 1 down to 0
x := s[i]
如果 st 不为空且栈顶为‘?’，则
从 st 中删除
first := st 的栈顶，然后从栈中删除两个元素
second := 栈顶，并从 st 中删除
如果 x 为 T，则将 first 插入 st，否则将 second 插入 st
否则，将 x 插入 st
当 st 不为空时
ret := ret + st 的栈顶，并从 st 中删除
反转 ret 并返回 ret
示例 (C++)
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string parseTernary(string s) {
string ret = "";
int n = s.size();
stack <char> st;
for(int i = n - 1; i >= 0; i--){
char x = s[i];
if(!st.empty() && st.top() == '?'){
st.pop();
char first = st.top();
st.pop();
st.pop();
char second = st.top();
st.pop();
if(x == 'T'){
st.push(first);
}
else st.push(second);
}
else{
st.push(x);
}
}
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.parseTernary("F?1:T?4:5"));
}输入
"F?1:T?4:5"
输出
4
更新于：2020年4月29日
493 次浏览
广告