逆波兰范式RPN全称reverse Polish notation，

简单的说：

   Equation with parenthesis       (1 + 2) * 3
   Prefix notation                 * 3 + 1 2       or      * + 1 2 3
   Postfix notation                1 2 + 3 *       or      3 1 2 + *
第一个表达式是通常带括号的算术表达式，第二是波兰范式，后一种就是逆波兰范式

使用（逆）波兰范式可以省去括号，让表达式顺序执行。

逆波兰范式这个网页介绍得比较清楚：http://users.ece.gatech.edu/~mleach/revpol/

把嵌套括号的表达式翻译成RPN表达式可以减少循环，加快求值速度。

把普通算术表达式翻译成RPN表达式方法如下（转贴自http://www.cs.utsa.edu/~wagner/CS1723/fall01/eval/trans.html）：

Here is a translator to RPN that uses the Java Stack class. This program also uses two other classes: Eval and GetNext that are listed here.

// Trans: translate input arith expr to RPN string
// Rules for each input char
//  (go on to next input char unless otherwise stated)
// Fetch next char, call it ch
// 1. if ch is an operand, move it to output.
// From now on ch is an operator or '(' or ')'.
// 2. if stack is empty, add ch to stack.
// 3. if ch is '(', add ch to stack.
// From now on, stack is not empty. Use top for its top char.
// 4. if ch is ')', remove chars from stack and output down
//    to '(' on stack, which is thrown away.
// 5. if top is '(', add ch to stack.
// From now on, both ch and top are regular operators.
// 6. if prec(ch) > prec(top), add ch to stack.
// 7. if prec(ch) < prec(top), move top to output, and
//    DO NOT MOVE ON TO NEXT INPUT CHAR.
// 8. if prec(ch) == prec(top) and left-to-right associativity,
//    move top to output, and DO NOT MOVE ON TO NEXT INPUT CHAR.
// 9. if prec(ch) == prec(top) and right-to-left associativity,
//    add top to stack.
// 10. at end, move everything on stack to output.
import java.util.*;
public class Trans { 

   Stack stack; // java library stack of objects
   public Trans() {
      stack = new Stack();
   }

   // translate: an arith expr to RPN
   public String translate(String s) {
      double op1 = 0.0, op2 = 0.0, res = 0.0; // = 0.0, for compiler
      String outStr = ""; // output string
      char ch, top;
      int i = 0; // index in input string
      while (i < s.length()) {
         boolean moveOn = true;
         ch = s.charAt(i); // before Rule 1
         if (Character.isDigit(ch) )  // Rule 1: digit to output
            outStr += ch;
         else if (stack.empty() || ch == '(') // Rules 2 and 3
            stack.push(new Character(ch));
         else { // stack is not empty
            top = ((Character)(stack.peek())).charValue(); // before Rule 4
            if (ch == ')') // Rule 4
               while (true) {
                  if ((top=((Character)(stack.pop())).charValue()) == '(')
                     break; // normal termination
                  outStr += top;
                  if (stack.empty()) error(1);
               }
            else if (top == '(') // Rule 5
               stack.push(new Character(ch));
            else if (prec(ch) > prec(top) || (prec(ch) == prec(top) &&
                        assoc(ch) == 'r') ) // Rules 6 and 9
               stack.push(new Character(ch));
            else if (prec(ch) < prec(top) || (prec(ch) == prec(top) &&
                        assoc(ch) == 'l') ) { // Rules 7 and 8
               outStr += top;
               stack.pop();
               moveOn = false;
            }
         }
         if (moveOn) i++;
      } // while
      while (!stack.empty()) // Rule 10
         outStr += ((Character)(stack.pop())).charValue();
      return outStr;
   }

   // prec: return int precedence of operators
   private int prec(char ch) {
      switch (ch) {
         case '+': case '-': return 1;
         case '*': case '/': return 2;
         case '^': return 3;
         default: return -1;
      }
   }

   // assoc: return 'l' for left-to-right, and 'r' for right-to-left
   private char assoc(char ch) {
      switch (ch) {
         case '+': case '-': case '*': case '/': return 'l';
         case '^': return 'r';
         default: return '?';
      }
   }

   // error: in case of an error
   private void error(int num) {
      System.out.println("Error number: " + num);
      System.exit(0);
   }

   public static void main(String[] args) {
      GetNext getNext = new GetNext(); // input class
      Trans trans = new Trans(); // new translater
      Eval eval = new Eval(); // new evaluator
      while (true) { // read and translate indefinitely
         String s = getNext.getNextString(); // fetch string
         System.out.println("Input: " + s);
         String resStr = trans.translate(s); // produce RPN
         System.out.println("RPN string: " + resStr); // print RPN
         double res = eval.evaluateRPN(resStr);
         System.out.println("Value: " + res); // print value
      }
   }
}

Sample run. Here each translation to RPN is carried out, and then the evaluator from RPN evaluator is called to calculate a final value.

% java Trans
2+3*4
Input: 2+3*4
RPN string: 234*+
Value: 14.0
2*3+4
Input: 2*3+4
RPN string: 23*4+
Value: 10.0
2^3^4
Input: 2^3^4
RPN string: 234^^
Value: 2.4178516392292583E24
2*(3+4)
Input: 2*(3+4)
RPN string: 234+*
Value: 14.0
2+(3*4)
Input: 2+(3*4)
RPN string: 234*+
Value: 14.0
((2)+(((3))))*((((4))))
Input: ((2)+(((3))))*((((4))))
RPN string: 23+4*
Value: 20.0
2+3*4^5*6+7
Input: 2+3*4^5*6+7
RPN string: 2345^*6*+7+
Value: 18441.0
2^3*4+5*6^7
Input: 2^3*4+5*6^7
RPN string: 23^4*567^*+
Value: 1399712.0
2-3-4
Input: 2-3-4
RPN string: 23-4-
Value: -5.0
2/3/4
Input: 2/3/4
RPN string: 23/4/
Value: 0.16666666666666666
2+3*4^5
Input: 2+3*4^5
RPN string: 2345^*+
Value: 3074.0
2^3*4+5
Input: 2^3*4+5
RPN string: 23^4*5+
Value: 37.0
2+3*4^5+6
Input: 2+3*4^5+6
RPN string: 2345^*+6+
Value: 3080.0
1+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2))))))))))))))))))))
Input: 1+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2+1/(2))))))))))))))))))))
RPN string: 11212121212121212121212121212121212121212/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+
Value:          1.414213562373095
(Note:sqrt(2) = 1.414213562373095048801688724209...)
2+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1/(1+1/(1+1/(2*5+1/(1+1/(1+1/(2*6+1/(1+1/(1+1/(2*7+1))))))))))))))))))))
Input: 2+1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1/(1+1/(1+1/(2*5+1/(1+1/(1+1/(2*6+1/(1+1/(1+1/(2*7+1))))))))))))))))))))
RPN string: 211121111141111161111181111125*1111126*1111127*1+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+
Value:     2.7182818284590455
(Note:e =  2.718281828459045235260287471352...)
3+1/(7+1/(5*3+1/(1+1/((4*(9*8+1))))))
Input: 3+1/(7+1/(5*3+1/(1+1/((4*(9*8+1))))))
RPN string: 317153*111498*1+*/+/+/+/+
Value: 3.1415926530119025
3+1/(7+1/(5*3+1/(1+1/((4*(9*8+1))+1/(1+1/(1+1/(1+1/(2+1/(1+1/(3+1/(1+1/(2*7+1/(2+1)))))))))))))
Input: 3+1/(7+1/(5*3+1/(1+1/((4*(9*8+1))+1/(1+1/(1+1/(1+1/(2+1/(1+1/(3+1/(1+1/(2*7+1/(2+1)))))))))))))
RPN string: 317153*111498*1+*11111112111311127*121+/+/+/+/+/+/+/+/+/+/+/+/+/+
Value:     3.141592653589793
(Note:pi = 3.141592653589793238462643383279...)
1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1)))))))))))))))))))))))))))))))))))
Input: 1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1/(1+1)))))))))))))))))))))))))))))))))))
RPN string: 111111111111111111111111111111111111111111111111111111111111111111111111+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+/+
Value:     1.618033988749894
(Note: f = 1.618033988749894848204586834365 ...
        = 	(0.5)*(1 + sqrt(5)) )

^C   (ctrl-C)

Revision date: 2001-09-29. (Please use ISO 8601, the International Standard.)