No.2595 Parsing Challenge
タグ : / 解いたユーザー数 11
作問者 :
SSRS
/ テスター :
Forested
注意
この問題は多倍長整数の使用を想定しています。
多倍長整数の計算の速度差を問うことがこの問題の目的ではないため、想定解を作るにあたって作成した多倍長整数を扱う簡単なライブラリ (C++) を GitHub にアップロードしました。
想定解はこのライブラリを用いて書かれており、想定解の実行時間は 920 ms です。
問題文
以下の BNF (バッカス・ナウア記法) において <expression> にあたる長さ $N$ の数式 $S$ が与えられます。計算してください。
<nonzero_digit> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<digit> ::= '0' | <nonzero_digit>
<positive_number> ::= <nonzero_digit> | <positive_number> <digit>
<number> ::= '0' | <positive_number> | '-' <number>
<factor> ::= <number> | '(' <expression> ')'
<term> ::= <factor> | <term> '*' <factor>
<expression> ::= <term> | <expression> '+' <term> | <expression> '-' <term>
入力
入力は以下の形式で標準入力から与えられます。
$N$ $S$
出力
計算結果を標準出力に $1$ 行で出力してください。
最後に改行してください。
制約
入力は以下の制約を満たします。
- $1 \leq N \leq 10^6$
- $S$ は長さ $N$ の文字列である。
- $S$ は問題文中の BNF における
<expression>である。 - $N$ は整数である。
サンプル
サンプル1
入力
10 -74+5+59-7
出力
-17
$-74+5+59-7 = -17$ なので、$-17$ を出力します。
サンプル2
入力
10 28*299+-99
出力
8273
$28 \times 299 + (-99) = 8273$ なので、$8273$ を出力します。
サンプル3
入力
15 ((8+26))*(92*9)
出力
28152
$((8+26))\times(92\times9)=28152$ なので、$28152$ を出力します。
無駄な括弧が付いていることもあることに注意してください。
サンプル4
入力
15 -9659*(----1)-7
出力
-9666
$-9659 \times (----1)-7=-9666$ なので、$-9666$ を出力します。
負号が $2$ つ以上連続することもあることに注意してください。
サンプル5
入力
50 4-(((6160)))-((4*8967+6194-581))*1602893-3300-35-7
出力
-66489614031
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。