RPN表达式

算法描述

RPN是对算数表达式的一种描述，描述中不含括号RPN经常用于虚拟机上，比如JVMRPN的书写特点之一是：操作符写在数字之后例如，“3-4” 可以写成 “3 4 -”同样的，“(3 - 4) * 5”可以写成 “3 4 - 5”注意以下，虽然没有括号，单RPN表达式依然没有歧义再比如，“3 - (4 * 5)” 会被写为“3 4 5 * -”RPN表达式通过一个栈来计算，表达式总左至右来处理遇到的每个数字被放入到栈中，遇到操作符时，合适的数字从栈中提取出来，进行计算，计算结果再入栈最后，栈的顶部数字就是表达式的值RPN支持的运算符包括加（+）、减（-）、乘（*）、负（~）例如，RPN表达式“2 3 + 6 ~ 7 * -”可以按照如下方式计算 Remaining Expression Stack New Stack 2 3 + 6 ~ 7 * - [] [2] 3 + 6 ~ 7 * - [2] [2 3] <---- Stacks grow to the right + 6 ~ 7 * - [2 3] [5] 6 ~ 7 * - [5] [5 6] ~ 7 * - [5 6] [5 -6] 7 * - [5 -6] [5 -6 7] * - [5 -6 7] [5 -42] - [5 -42] [47] <---- Final answer is 47 若是因为RPN表达式构造不合理，你可以返回-999

---

参数定义

类名 RPN方法 evaluate输入参数 string输出 string方法声明 int evaluate(string expr)

限制条件

expr包含奇数个字符expr 的奇数位置是空格expr 的偶数位置是[0 - 9] ,或者符号加（+）、减（-）、乘（*）、负（~）

例子

输入 expr: “2 3 + 6 ~ 7 * -“输出 47

测试实例

实例一

输入

”5 ~ ~ ~”

输出

-5

实例二

输入 ”9 8 7 * * 4 5 - -“输出 505

实例三

输入 ”1 + 2 + 3” 输出 -999

实例四

输入 ”1 9 ~ 2 8 * +” 输出 -999