逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）

定义：

1. 如果E是一个变量或常量则E的后缀式是E本身。
2. 如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1'E2' op，这里E1'和E2'分别为E1和E2的后缀式
3. 如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。

例：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+

实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？因为计算机进行表达式运算普遍采用的内存结构是栈式结构，依托栈的先进先出特性，可以直接对逆波兰表达式进行运算。如果是我们日常使用的表达式，需要使用两个栈，一个存操作数，一个存操作符。

将一个普通的中缀表达式转换为逆波兰表达式的步骤：

我们需要定义好各个运算符的优先级，这一步很重要，转换为精确的定义可以避免歧义

ICP: in comming priority -栈外优先级
ISP: in stack priority- 栈内优先级

接下来，从左到右扫描中缀表达式，循环执行下面的动作

1. 若为操作数，直接输出
2. 若是操作符且栈为空，直接进栈
3. 若是操作符且栈不为空，判断 该操作符（ch）的优先级icp 与栈顶的操作符op的优先级
   If icp(ch)>isp(op) ,ch进栈，进入下一循环
   If icp(ch)<isp(op) ,op出栈并输出，继续当前循环
   If icp(ch)=isp(op) ,op出栈但不输出，若op为（，进入下一循环，否则继续当前循环
   以上动作完成后，按序输出栈中元素。

举个栗子

a*(b+c-d*f)/e+g

好的，上代码

定义优先级

public static int getIcp(char op){
        if(op=='(')
            return 6;
        else if (op=='*'||op=='/')
            return 4;
        else if(op=='+'||op=='-')
            return 2;
        else if(op==')')
            return 1;
        else
            throw new RuntimeException("unsupported operation");
    }
    public static int getIsp(char op){
        if(op=='(')
            return 1;
        else if (op=='*'||op=='/')
            return 5;
        else if(op=='+'||op=='-')
            return 3;
        else if(op==')')
            return 6;
        else
            throw new RuntimeException("unsupported operation");

    }

判断是否操作符

public static boolean notOp(char val){
        if(val=='*'||val=='/'||val=='('||val=='+'||val=='-'||val==')'){
            return false ;
        }else{
            return true;
        }
  }

转换RPN

public static String transferRPN(String in ) {
        Stack<Character> stack = new Stack<>(in.length());
        StringBuilder rpn = new StringBuilder();
        char[] valChars= in.toCharArray();
        char blank = ' ';//使用空格分隔开操作数与操作符
        for(int i=0;i<valChars.length;i++){
            char ch = valChars[i];
            if(notOp(ch)){
                rpn.append(ch);
                //分隔操作数==========================
                if(i==valChars.length-1){
                      rpn.append(blank);
                }else{
                    if(!notOp(valChars[i+1])){
                        rpn.append(blank);
                    }
                }
                //=============================
            }else if (stack.empty()){
                stack.push(ch);
            }else{
                char op = stack.peek();
                if(getIsp(op)<getIcp(ch)){
                    stack.push(ch);
                }else if(getIsp(op)>getIcp(ch)){
                    stack.pop();
                    rpn.append(op);
                    //分隔操作符
                    rpn.append(blank);
                    i--;
                }else {
                    stack.pop();
                    if(op!='('){
                        i--;
                    }
                }
            }
        }
       while(!stack.empty()){
            rpn.append(stack.pop());
           //分隔操作符
            rpn.append(blank);
        }

     return rpn.toString();
    }

测试

 public static void main(String[] args) {
        String in = "a*(b+c-d*f)/e+g";//abc+df*-*e/g+
        System.out.println(transferRPN(in));

    }

结果

a b c + d f * - * e / g + 

Process finished with exit code 0