C++の3項式パーサー

任意にネストされた3項式を表す文字列があるとすると、式の結果を計算する必要があります。与えられた式が有効であり、0〜9、？、：、T、およびFの数字のみで構成されていると常に想定できます。 （ここで、TとFはそれぞれTrueとFalseを表します）。いくつかのプロパティがあります-

• 指定された文字列の長さは10000以下である必要があります。

• 各番号には1桁のみが含まれます。

• 条件式は右から左にグループ化します。

• 条件は常に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までの範囲のIの場合

  • x：=s [i]

  • stが空でなく、スタックの最上位が「？」の場合、

    • stから削除

    • 最初に：=stの先頭、次にスタックから2つの要素を削除します

    • 2番目：=スタックの一番上、stから削除

    • xがTの場合は、最初にstに挿入します。それ以外の場合は、2番目を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