A spreadsheet cell stores a formula as an infix arithmetic expression string with no whitespace. It uses the digits 0-9, the binary operators +, -, *, /, parentheses ( ), and unary signs: a + or - acts as a unary sign when it appears at the start of the expression, right after an opening parenthesis (, or right after another operator. A unary sign binds more tightly than the binary operators, so -3*2 is (-3)*2 = -6 and 2*-3 is 2*(-3) = -6.
Evaluate with standard precedence (* and / bind tighter than binary + and -), left-to-right associativity among operators of equal precedence, and parentheses overriding precedence. Division truncates toward zero (like integer division in C or Java), so -7/2 is -3. Each maximal run of digits is a non-negative integer literal.
The expression is guaranteed to be syntactically valid and division by zero never occurs.
Input format
A single line: the expression string (no whitespace).
Output format
A single integer: the value of the expression.
Constraints
- 1 <= length of the expression <= 200
- Every intermediate and final value fits in a signed 64-bit integer.
- Division by zero never occurs.