2570 < JAG Regional < Challenges | Aizu Online Judge
問題
以下の BNF で表される言語を考える。
1
2
|
expr ::= term | expr sp ">>" sp term
term ::= number | "S" sp "<" sp expr sp ">"
|
ここでsp
は 0 個以上のスペースからなる文字列、number
は $0$ 以上 $10^9$ 以下の整数を表す。
言語の評価規則は以下の通り。
x>>y
は $\left\lfloor \frac{x}{2^y} \right\rfloor$ と評価される。
S<x>
は $x^2 \bmod{10^9 + 7}$ と評価される。
expr
で表現可能な文字列が与えられるので、それを評価した結果を求めよ。
制約
- 文字列の長さは $2 \cdot 10^6$ 以下
考察
何も考えずに実装すると、入力例にあるS<S<S<S<S<2>>>>>
でパースエラーになる。
これは「S<x>
中の>
が 2 つ連なったもの」と、「x>>y
中の>>
」が区別できないためである。
これを区別するために、何らかのアドホックな処理が必要になる。
以下の実装では、「S<S<x>>
のような項の直後にterm
は来ない」ことを利用して、「>>
の後にS
か数字が来るかどうか」で判定をしている。
実装例
C++11 以降のコンパイラって偉いな〜というお気持ちになる。
Run #4990718 < misteer < Solutions | Aizu Online Judge
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
#include <iostream>
#include <string>
#include <cassert>
using lint = long long;
constexpr lint MOD = 1000000007;
struct Parser {
std::string s;
int i;
Parser(const std::string& s) : s(s), i(0) {}
void sp() {
while (s[i] == ' ') ++i;
}
lint term() {
if (s[i] == 'S') {
// S<x>
++i;
sp();
assert(s[i] == '<');
++i;
sp();
auto e = expr();
sp();
assert(s[i] == '>');
++i;
return e * e % MOD;
} else {
// number
assert(std::isdigit(s[i]));
lint ret = 0;
while (std::isdigit(s[i])) {
ret = ret * 10 + s[i] - '0';
++i;
}
return ret;
}
}
lint expr() {
auto ret = term();
sp();
while (s.substr(i, 2) == ">>") {
// iのバックアップ(j)を用意
int j = i;
i += 2;
sp();
// >>の先がtermでないなら、shiftではないので復元する
if (s[i] != 'S' && !std::isdigit(s[i])) {
i = j;
break;
}
// shift
auto t = term();
if (t > 30) {
ret = 0;
} else {
ret >>= t;
}
sp();
}
return ret;
}
};
bool solve() {
std::string s;
std::getline(std::cin, s);
if (s == "#") return false;
Parser parser(s);
std::cout << parser.expr() << "\n";
return true;
}
|