Reverse Polish Notation (RPN) is a notation for writing arithmetic expressions that is famous for not needing parentheses.
Perhaps best known for its use in certain calculators, RPN is also commonly used in virtual machines such as the JVM.
The distinguishing feature of RPN is that arithmetic operators are written after their arguments. For example, the infix expression "3 - 4" would be written in RPN as "3 4 -" (all quotes for clarity only). Similarly, the infix expression "(3 - 4) * 5"
would be written in RPN as "3 4 - 5 *". Notice how no parentheses were necessary in the RPN expression. No confusion
is possible, because the infix expression "3 - (4 * 5)" would be written in RPN as "3 4 5 * -".
An RPN expression is evaluated using a stack. The expression is processed from left to right. Each number is pushed onto the stack as
it is encountered. When an operator is encountered, the appropriate number of arguments are popped off the stack, the operation is
performed, and the result is pushed back onto the stack. The final answer is the value on the top of the stack when the end of the expression is reached. The supported arithmetic operators are addition ('+'), subtraction ('-'), multiplication ('*'),
and unary negation ('~')
For example, the RPN expression "2 3 + 6 ~ 7 * -" would be evaluated as shown in the following table:
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
You will write a method that takes an RPN expression expr as a String, evaluates it, and returns its final value.
The expression will contain only digits ('0'-'9'), arithmetic operators ('+', '-', '*', '~'), and spaces (' ').
Only single-digit numbers will be allowed, and all numbers and operators will be separated by single
spaces, with no leading or trailing spaces.
An RPN expression is malformed if evaluating it would leave more than one value on the stack, or if evaluating it would cause some
operator to try to pop an empty stack. Your method should return -999 if expr is malformed.
|