問題一覧 > 通常問題

No.2595 Parsing Challenge

レベル : / AI推定難易度 : 3025 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題(-0 と 0 は同じとみなします)
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : SSRS / テスター : 👑 Forested
お気に入りにしたユーザー ProblemId : 9979 / 自分の提出
問題文最終更新日: 2026-10-23 18:44:16
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2023 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。