DIY: Basic Calculator III

Problem statement

You are given a string s containing only positive integers, operators ('+', '-', '*', '/'), and parentheses '()'. The intermediate results of the given expression string are in the range [-$2^{31}$, $2^{31}$ - 1]. The expression is guaranteed to be valid and the integer division truncates towards zero. Your task is to evaluate the given expression string.

Constraints

• $1$ <= expression <= $10^4$
• The string consists of only digits, '+', '-', '*', '/', '(', and ')'.

Input

The input of the function is a string. The following is an example input:

3*(5+5)/2+(6/2)

Output

The following is the output of the above input:

18

Coding exercise

Implement the calculate(string) function, where the string is a mathematical expression and returns the integer number.