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

,

| stack | queue | | dfs | bfs |

という対応は綺麗なので好き。

結構時間取られた。1時間半ぐらい。

F - 逆ポーランド記法

問題

逆ポーランド記法の式が与えられる。 逆ポーランド記法の式の計算の際にstackでなくqueueを使って計算した場合に、元の計算結果と同じ結果になるようにこの式を並び換えよ。

解法

類推と実験か。

       -
   *       +
 +   *   -   -
1 2 3 4 5 6 7 8

という木で表される式があるとする。

このとき、stackの(つまり普通の)rpnであれば、

       15
   7       14
 3   6   10  13
1 2 4 5 8 9 11 12

という順で書き、12+34**56-78-+-となる。これはdfs。

一方、queueのrpnであれば、

       15
   14      13
 12  11  10  9
8 7 6 5 4 3 2 1

という順で書き、87654321--*++*-となる。これはbfs。

実装

競技でnewしたの始めてかも。

#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <cassert>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
struct expr_t {
    char c;
    expr_t *l;
    expr_t *r;
};
expr_t *alloc_expr(char c, expr_t *l, expr_t *r) {
    expr_t *e = new expr_t;
    e->c = c;
    e->l = l;
    e->r = r;
    return e;
}
expr_t *parse(string const & s) {
    stack<expr_t *> x;
    for (char c : s) {
        if (isdigit(c)) {
            x.push(alloc_expr(c, NULL, NULL));
        } else {
            assert (c == '+' or c == '-' or c == '*');
            assert (x.size() >= 2);
            expr_t *r = x.top(); x.pop();
            expr_t *l = x.top(); x.pop();
            x.push(alloc_expr(c, l, r));
        }
    }
    assert (x.size() == 1);
    return x.top();
}
void format(expr_t *e, int i, map<int,string> & acc) {
    if (e == NULL) return;
    acc[i] += e->c;
    format(e->r, i+1, acc);
    format(e->l, i+1, acc);
}
string format(expr_t *e) {
    map<int,string> acc;
    format(e, 0, acc);
    string s;
    for (auto p : acc) s = p.second + s;
    return s;
}
int main() {
    string s; cin >> s;
    expr_t *e = parse(s);
    cout << format(e) << endl;
    return 0;
}

実験用 stack

#include <iostream>
#include <stack>
#include <cassert>
using namespace std;
int main() {
    string s; cin >> s;
    stack<int> x;
    for (char c : s) {
        if (isdigit(c)) {
            x.push(c - '0');
        } else {
            assert (c == '+' or c == '-' or c == '*');
            assert (x.size() >= 2);
            int r = x.top(); x.pop();
            int l = x.top(); x.pop();
            x.push(c == '+' ? l + r :
                    c == '-' ? l - r :
                    l * r);
        }
    }
    assert (x.size() == 1);
    cout << x.top() << endl;
    return 0;
}

実験用 queue

#include <iostream>
#include <queue>
#include <cassert>
using namespace std;
int main() {
    string s; cin >> s;
    queue<int> x;
    for (char c : s) {
        if (isdigit(c)) {
            x.push(c - '0');
        } else {
            assert (c == '+' or c == '-' or c == '*');
            assert (x.size() >= 2);
            int r = x.front(); x.pop();
            int l = x.front(); x.pop();
            x.push(c == '+' ? l + r :
                    c == '-' ? l - r :
                    l * r);
        }
    }
    assert (x.size() == 1);
    cout << x.front() << endl;
    return 0;
}