Evaluate Mathematical Expression

You are given a string s representing a valid mathematical expression. The expression can contain non-negative integers, the operators +, -, *, and / (where / denotes integer division), as well as parentheses ( ) for grouping. The expression must be evaluated following the usual operator precedence rules and associativity. In particular, multiplication and division are performed before addition and subtraction, and expressions in parentheses are fully evaluated first.

Note that division performs integer division. For example, \(5/2 = 2\) using integer division.

Examples:

• Input: 3+2*2 — Output: 7
• Input: (2+3)*(5/2) — Output: 10

inputFormat

The input consists of a single line that contains a string representing a valid mathematical expression. The expression only includes non-negative integers, the operators +, -, *, /, and parentheses ( ).

Note: There are no extra spaces in the input.

outputFormat

Output a single integer which is the result of evaluating the expression. Make sure to perform integer division when dividing.

3+2

5