C++でネストした三項式を解析する：スタックを使ったパーサーの実装

任意の深さでネストされた三項式（三項演算子による条件式）を表す文字列が与えられたとき、その式を解析して最終的な評価結果を求めるのが本問題です。入力となる式は常に有効であり、構成要素は数字「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」に書き換わり、条件Fは偽であるため最終的に4が出力されるからです。

アルゴリズムの考え方

この問題は、文字列を右から左へ走査しながらスタックを活用することで、シンプルかつ効率的に解くことができます。具体的な手順は以下の通りです。

1. ret := 空文字列、n := 文字列sの長さとし、空のスタックstを用意する。
2. i を n − 1 から 0 まで逆順にループする。
   • x := s[i] とする。
   • スタックが空でなく、かつスタックの先頭が「?」である場合は、次のように処理する。
     • 先頭の「?」をポップして取り除く。
     • first := スタックの先頭要素とし、続けて2つの要素をポップする（真の場合の値と「:」を除去）。
     • second := スタックの先頭要素とし、それをポップする。
     • x が「T」であれば first を、そうでなければ second をスタックにプッシュする。
   • 上記以外の場合は、x をそのままスタックにプッシュする。
3. スタックが空になるまで、先頭の文字を ret の末尾に加えながらポップを繰り返す。
4. 最後に 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