C++で三項式を評価するプログラム

三項式を保持する式があるとすると、式の結果を評価する必要があります。 TrueとFalseのTとF、および「？」などのいくつかの値をサポートします。および「：」文字。いくつかのプロパティがあります：

• 指定された文字列の長さは10000以下である必要があります。
• 条件式は右から左にグループ化します。
• 条件は常にTまたはFのいずれかになります。したがって、条件が数字になることはありません。
• 式の結果は常にTまたはFに評価されます。

たとえば、入力が「T？ T？ F：T：T」なので、出力はFになります。

これを解決するには、次の手順に従います。

• 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を返す

理解を深めるために、次の実装を見てみましょう。

例

#include
using namespace std;
class Solution {
   public:
   string parseTernary(string s) {
      string ret = "";
      int n = s.size();
      stack 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("T?T?F:T:T"));
}

入力

" T?T?F:T:T"

出力

F