C++で三項式を評価するプログラムの書き方｜スタックを使った実装例

三項式（条件演算式）を含む文字列が与えられたとき、その評価結果を求める問題を考えます。式には真偽値を表す「T」（True）と「F」（False）、および条件を示す「?」と「:」の記号が使用されます。この問題には以下のような性質があります。

• 与えられる文字列の長さは10,000以下である。
• 条件式は右から左へ向かってグループ化される。
• 条件部分は必ず「T」または「F」であり、数字が現れることはない。
• 式の評価結果は常に「T」または「F」のいずれかになる。

たとえば、入力が「T ? T ? F : T : T」であれば、出力は「F」となります。

解法のアプローチ

この問題は、スタックを使って文字列を右から左へ走査することで効率的に解けます。「?」を見つけた時点で、その右側にある「真のときの値」「:」「偽のときの値」はすでにスタックに積まれているため、条件に応じて適切な値だけを残せばよいのです。具体的な手順は以下の通りです。

1. ret := 空文字列、n := 文字列sのサイズとします。
2. スタックstを作成します。
3. i を n − 1 から 0 まで1ずつ減らしながら以下を繰り返します。
   • x := s[i] とします。
   • スタックが空でなく、スタックの先頭が「?」である場合は次のように処理します。
     • スタックから「?」を取り除きます（pop）。
     • first := スタックの先頭要素とし、続けて2つの要素をpopして取り除きます（真のときの値と「:」）。
     • second := スタックの先頭要素とし、それをpopします（偽のときの値）。
     • x が「T」であれば first をスタックにpushし、そうでなければ second をpushします。
   • 上記以外の場合は、x をそのままスタックにpushします。
4. スタックが空になるまで、先頭要素を ret の末尾に連結しながらpopしていきます。
5. 最後に ret を反転して返します。

C++での実装例

#include <iostream>
#include <stack>
#include <algorithm>
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;
    }
};

int main() {
    Solution ob;
    cout << (ob.parseTernary("T?T?F:T:T"));
}

入力

"T?T?F:T:T"

出力

F

動作のポイント

右から左へ走査するのは、三項演算子が右結合であるためです。ネストされた「?」は右側ほど内側の式に対応するので、右端から処理することで、常に最も深い入れ子の式から順に評価結果を確定できます。各「?」に出会った時点で、対応する2つの分岐の値はすでにスタック上に揃っているため、条件が「T」か「F」かに応じて一方を選んでスタックに戻すだけで評価が完了します。計算量はO(n)、空間計算量もO(n)であり、長さ10,000までの文字列でも十分高速に動作します。