Evaluate an Arithmetic Expression

Write evaluate(expression) that works out the value of an arithmetic expression given as text and returns it as an integer, without using eval(). The expression is made of whole numbers, the operators +, -, * and /, round brackets and spaces.

• * and / are done before + and -, and operators of the same strength go from left to right: 8 - 3 - 2 is 3.
• / divides and then drops the fractional part, rounding toward zero: 7 / 2 is 3 and -7 / 2 is -3. Careful: Python's // rounds down, which would give -4.
• A - in front of a number or a bracket negates it, so -3, -(2 + 1), 4 * -2 and --5 are all allowed. Negation binds tighter than any other operator: -2 + 3 is 1.
• Brackets can be nested inside each other.

Examples

evaluate("2 + 3 * 4")      # returns 14
evaluate("(2 + 3) * 4")    # returns 20
evaluate("7 - 10 / 3")     # returns 4
evaluate("-(8 - 20) / 5")  # returns 2

In the last example the bracket is -12, negating it gives 12, and 12 / 5 rounds toward zero to 2.

Constraints

• expression has 1 to 10,000 characters and is always valid.
• Brackets are nested at most 50 deep, and there is never a division by zero.
• Every intermediate result is between -1,000,000,000 and 1,000,000,000.