Evaluate Mathematical Expression

You are given a string representing a mathematical expression which includes non-negative integers, the operators ( + ), ( - ), ( * ), ( / ) and parentheses ( ( ) and ( ) ). The task is to evaluate the expression using the Shunting Yard algorithm to convert the expression from infix notation to Reverse Polish Notation (RPN), and then evaluate the RPN. Note that division ( / ) should truncate towards zero.

For example, given the expression 3+(2*2)-1, the correct output is 6.

inputFormat

The input consists of a single line containing the mathematical expression. The expression is guaranteed to be valid and may contain spaces. The operators allowed are +, -, *, /, and parentheses ( ).

Formally, the input is:

S

where S is a string representing the expression.

outputFormat

Output a single integer which is the result of evaluating the expression. The division operation should truncate towards zero.

Formally, output:

result

where result is the integer evaluation of the input expression.

## sample

3+(2*2)-1

6