No.2595 Parsing Challenge
Note
This problem is intended to be solved using arbitrary-precision integers.
Since the purpose of this problem is not to test differences in the speed of arbitrary-precision arithmetic, the simple library (C++) for handling arbitrary-precision integers that was written to create the intended solution has been uploaded to GitHub.
The intended solution is written using this library, and its execution time is 920 ms.
Problem Statement
You are given a mathematical expression $S$ of length $N$ that corresponds to <expression> in the following BNF (Backus-Naur form). Calculate its value.
<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>
Input
The input is given from standard input in the following format.
$N$ $S$
Output
Print the result of the calculation to standard output in $1$ line.
Print a newline at the end.
Constraints
The input satisfies the following constraints.
- $1 \leq N \leq 10^6$
- $S$ is a string of length $N$.
- $S$ is an
<expression>in the BNF given in the problem statement. - $N$ is an integer.
Sample
Sample 1
Input
10 -74+5+59-7
Output
-17
Since $-74+5+59-7 = -17$, print $-17$.
Sample 2
Input
10 28*299+-99
Output
8273
Since $28 \times 299 + (-99) = 8273$, print $8273$.
Sample 3
Input
15 ((8+26))*(92*9)
Output
28152
Since $((8+26))\times(92\times9)=28152$, print $28152$.
Note that there may be redundant parentheses.
Sample 4
Input
15 -9659*(----1)-7
Output
-9666
Since $-9659 \times (----1)-7=-9666$, print $-9666$.
Note that $2$ or more consecutive minus signs may appear.
Sample 5
Input
50 4-(((6160)))-((4*8967+6194-581))*1602893-3300-35-7
Output
-66489614031
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
SSRS
Forested