题目描述

输入一个表达式，仅可能含有 阿拉伯数字，+，-，*，/, ^，(，)。请计算表达式的值。

注：其中 / 取商的整数部分，^ 表示幂运算。

另外：

（1）负数可以加括号，也可以不加括号，如 1*(-5) 或 1*-5 均有可能出现

（2）对于幂运算 a^b 不会出现 b 为负数的情况，也不会出现 a、b 均为 0 即 0^0 的形式。

（3）数据可能会出现多余括号情况，比如：

2*(((1+3)-4 的值为 0

2*(1+3)))-4 的值为 4

但不会出现非法括号情形，比如：

2*)(1+3)-4

输入

一行，一个表达式

输出

表达式的值；如果运算过程中出现了除以 0 的情形，则输出 division by zero

样例输入#1

-10-1*(-12+(7-5)^3^2))

样例输出#1

-510

样例输入#2

10-(((3/(1+2-3)

样例输出#2

division by zero

样例输入#3

3+1*-5)^2)^2^3))

样例输出#3

65536

提示

测试数据保证表达式运算中间结果及最终结果在 long long 范围内

数据范围

共 13 个测试点，每个测试点的表达式长度均不超过 1000。其中：

测试点 1-2：符号仅可能含有 + -

测试点 3-4：符号仅可能含有 + - * /

测试点 5-6：符号仅可能含有 + - * / ^

测试点 7-13：符号仅可能含有 + - * / ^ ( )