京都大学プログラミングコンテスト2015 F - 逆ポーランド記法

問題

kupc2015.contest.atcoder.jp

解法

計算の構文木を作って, その構文木を幅優先探索して得られる文字順を反転させると答えになります。

例えば以下のような感じですね。

デバッグ用に計算結果も出力してくれます↓

int calcs(string s) {
    stack<int> X;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (isdigit(s[i])) X.push(s[i]-'0');
        else {
            int r = X.top(); X.pop();
            int l = X.top(); X.pop();
            if (s[i] == '+') X.push(l+r);
            if (s[i] == '-') X.push(l-r);
            if (s[i] == '*') X.push(l*r);
        }
    }
    return X.top();
}

int calcq(string s) {
    queue<int> X;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (isdigit(s[i])) X.push(s[i]-'0');
        else {
            int r = X.front(); X.pop();
            int l = X.front(); X.pop();
            if (s[i] == '+') X.push(l+r);
            if (s[i] == '-') X.push(l-r);
            if (s[i] == '*') X.push(l*r);
        }
    }
    return X.front();
}

int L[111], R[111];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    string ans;
    int n = s.size();
    stack<int> S;
    for (int i = 0; i < n; i++) {
        if (!isdigit(s[i])) {
            int r = S.top(); S.pop();
            int l = S.top(); S.pop();
            L[i] = l; R[i] = r;
        }
        S.push(i);
    }
    queue<int> que;
    que.push(S.top());
    while (!que.empty()) {
        int x = que.front(); que.pop();
        ans += s[x];
        if (!isdigit(s[x])) {
            que.push(L[x]);
            que.push(R[x]);
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
//    cout << calcs(s) << endl;
//    cout << calcq(ans) << endl;
    return 0;
}