POJ 3367 - Expressions

http://poj.org/problem?id=3367

概要

逆ポーランド記法で与えられた数式をポーランド記法に変換したものを答える。

大文字のアルファベットは二項演算子であり、小文字のアルファベットは数字を表しているとする。

制約

解法

構文木を作ってポーランド記法で出力するだけ。 ただし、あまり愚直にやると Time Limit が厳しいので、動的にメモリ確保したりしないようにする。

 1 #include <cstdio>
 2 #include <utility>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int T;
 8   scanf("%d", &T);
 9   while (T-- > 0) {
10     static char buf[10001];
11     scanf("%s", buf);
12     static pair<int,int> nodes[10000];
13     static int mem[10000];
14     int sp = 0;
15     int i;
16     for (i = 0; buf[i] != '\0'; ++i) {
17       pair<int,int>& e = nodes[i];
18       if ('a' <= buf[i] && buf[i] <= 'z') {
19         e.first = e.second = -1;
20         mem[sp++] = i;
21       } else {
22         e.first = mem[--sp];
23         e.second = mem[sp-1];
24         mem[sp-1] = i;
25       }
26     }
27 
28     static char out[10001];
29     out[i] = '\0';
30     int head = 0, tail = 1;
31     while (head < tail) {
32       const int idx = mem[head++];
33       const pair<int,int>& e = nodes[idx];
34       out[--i] = buf[idx];
35       if (e.first != -1) {
36         mem[tail++] = e.second;
37         mem[tail++] = e.first;
38       }
39     }
40     puts(out);
41   }
42   return 0;
43 }
poj/3367.cc