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

• 因为我的范围是n – 1至0

• 从st删除

• 首先：= st的顶部，然后从堆栈中删除两个元素

• 第二：=栈顶，然后从st删除

• 如果x是T，则将第一个插入st，否则将第二个插入st

• x：= s [i]

• 如果st不为空并且栈顶为'？'，则

• 否则，将x插入st

• 当st不为空时，则

• ret：= ret + st的顶部并从st删除

• 反向退出和返回退出

范例（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