Statistics

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.