百度百科

??逆波蘭表達(dá)式又叫做后綴表達(dá)式奋渔。在通常的表達(dá)式中张足，二元運(yùn)算符總是置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間笨枯，這種表示法也稱(chēng)為中綴表示蛙讥。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了另一種表示表達(dá)式的方法锯蛀，按此方法，每一運(yùn)算符都置于其運(yùn)算對(duì)象之后次慢，故稱(chēng)為后綴表示旁涤。

用途

??逆波蘭表達(dá)式是一種十分有用的表達(dá)式，它將復(fù)雜表達(dá)式轉(zhuǎn)換為可以依靠簡(jiǎn)單的操作得到計(jì)算結(jié)果的表達(dá)式迫像。例如(a+b)(c+d)轉(zhuǎn)換為ab+cd+

優(yōu)勢(shì)

??它的優(yōu)勢(shì)在于只用兩種簡(jiǎn)單操作劈愚，入棧和出棧就可以搞定任何普通表達(dá)式的運(yùn)算。其運(yùn)算方式如下：
??如果當(dāng)前字符為變量或者為數(shù)字侵蒙，則壓棧造虎，如果是運(yùn)算符，則將棧頂兩個(gè)元素彈出作相應(yīng)運(yùn)算纷闺，結(jié)果再入棧算凿，最后當(dāng)表達(dá)式掃描完后，棧里的就是結(jié)果犁功。

運(yùn)算方法

1.創(chuàng)建兩個(gè)棧氓轰，一個(gè)用來(lái)存放運(yùn)算符stack1，一個(gè)用來(lái)存放最終結(jié)果stack2浸卦，遍歷字符串署鸡；
a>如果是數(shù)字，直接壓入stack2限嫌；
b>如果是是運(yùn)算符且棧為空靴庆，直接壓入stack1，如果棧不為空怒医，當(dāng)前運(yùn)算符與棧頂運(yùn)算符比較炉抒，如果優(yōu)先級(jí)高于棧頂運(yùn)算符直接壓入，小于等于則稚叹，先把小于等于部分的運(yùn)算符彈出到stack2中焰薄，再把掃描到的運(yùn)算符壓入到stack1中拿诸；
c>如果是'(',則無(wú)條件入棧，當(dāng)遇到')'的時(shí)候塞茅，直接把括號(hào)內(nèi)的部分彈出到stack2中亩码，且括號(hào)不能入棧，輸出的棧中是沒(méi)有括號(hào)這個(gè)運(yùn)算符的野瘦；

舉例說(shuō)明

a+bc +(d-e)f,運(yùn)算符棧為s1,存放輸出結(jié)果的棧為s2描沟；

1.遇到數(shù)字a，直接入棧s2;此時(shí)s1：null ?;? s2:a

2.遇到+號(hào)且s1為空鞭光，直接入棧s1;此時(shí)：s1:+?;? s2:a

3.遇到數(shù)字b啊掏，直接入棧s2;此時(shí)：s1:+?;? s2:ab

4.遇到*號(hào)，優(yōu)先級(jí)高于+號(hào)衰猛，直接入棧s1;此時(shí)：s1:+* ?;? s2:ab

5.遇到數(shù)字b，直接入棧s2;此時(shí)：s1:+* ?;? s2:abc

6.遇到+號(hào),且運(yùn)算符優(yōu)先級(jí)低于s1棧頂符號(hào)刹孔，號(hào)彈出到s2;此時(shí)：s1:+ ?;? s2:abc;又等于此時(shí)s1的棧頂元素+號(hào)啡省，繼續(xù)彈出到s2;此時(shí)：s1:null ?;? s2:abc+;然后把+號(hào)直接壓入s1;此時(shí)：s1:+ ?;? s2:abc*+

7.遇到（的時(shí)候，無(wú)條件壓入s1;此時(shí)：s1:+( ?;? s2:abc*+

8.遇到d的時(shí)候髓霞，壓入s2;此時(shí)：s1:+（ ?;? s2:abc*+d

9.遇到-號(hào)的時(shí)候，壓入s1；此時(shí)：s1:+（- ?;? s2:abc*+

10.遇到e的時(shí)候搬卒，直接壓入s2弯院；此時(shí)：s1:+（- ?;? s2:abc*+e

11.遇到）的時(shí)候，把括號(hào)內(nèi)部分還存在的運(yùn)算符壓入到 s2;此時(shí)：s1:+?;? s2:abc*+-

12.遇到號(hào)的時(shí)候纵潦，運(yùn)算符優(yōu)先級(jí)比s1棧頂元素+號(hào)高徐鹤，直接壓入s1;此時(shí)：s1:+?;? s2:abc*+-

13.遇到數(shù)字f直接壓入s2;此時(shí)：s1:+?;? s2:abc+-f

14.此時(shí)把s1中的運(yùn)算符號(hào)依次壓入到s2;此時(shí)：s1:null ?;? s2:abc+-f+

此時(shí)，一個(gè)運(yùn)算結(jié)束邀层，其他表達(dá)式同樣的操作進(jìn)行即可返敬；

代碼實(shí)現(xiàn)

import java.util.Stack;

/**
 * 逆波蘭表達(dá)式
 */
public class ReversePolishNotation {
    public static void main(String[] args) {
        //測(cè)試用例
        //String str = "1+2*3-4*5-6+7*8-9"; //123*+45*-6-78*+9-
        String str = "a*(b-c*d)+e-f/g*(h+i*j-k)"; // abcd*-*e+fg/hij*+k-*-
        //String str = "6*(5+(2+3)*8+3)"; //6523+8*+3+*
        //String str = "a+b*c+(d*e+f)*g"; //abc*+de*f+g*f

        Stack<Character> operators = new Stack<>(); //運(yùn)算符
        Stack output = new Stack(); //輸出結(jié)果
        rpn(operators, output, str);
        System.out.println(output);
    }

    public static void rpn(Stack<Character> operators, Stack output, String str) {
        char[] chars = str.toCharArray();
        int pre = 0;
        boolean digital; //是否為數(shù)字（只要不是運(yùn)算符，都是數(shù)字）寥院，用于截取字符串
        int len = chars.length;
        int bracket = 0; // 左括號(hào)的數(shù)量

        for (int i = 0; i < len; ) {
            pre = i;
            digital = Boolean.FALSE;
            //截取數(shù)字
            while (i < len && !Operator.isOperator(chars[i])) {
                i++;
                digital = Boolean.TRUE;
            }

            if (digital) {
                output.push(str.substring(pre, i));
            } else {
                char o = chars[i++]; //運(yùn)算符
                if (o == '(') {
                    bracket++;
                }
                if (bracket > 0) {
                    if (o == ')') {
                        while (!operators.empty()) {
                            char top = operators.pop();
                            if (top == '(') {
                                break;
                            }
                            output.push(top);
                        }
                        bracket--;
                    } else {
                        //如果棧頂為 ( 劲赠，則直接添加，不顧其優(yōu)先級(jí)
                        //如果之前有 ( 秸谢，但是 ( 不在棧頂凛澎，則需判斷其優(yōu)先級(jí)，如果優(yōu)先級(jí)比棧頂?shù)牡凸捞悖瑒t依次出棧
                        while (!operators.empty() && operators.peek() != '(' && Operator.cmp(o, operators.peek()) <= 0) {
                            output.push(operators.pop());
                        }
                        operators.push(o);
                    }
                } else {
                    while (!operators.empty() && Operator.cmp(o, operators.peek()) <= 0) {
                        output.push(operators.pop());
                    }
                    operators.push(o);
                }
            }
        }
        //遍歷結(jié)束塑煎，將運(yùn)算符棧全部壓入output
        while (!operators.empty()) {
            output.push(operators.pop());
        }
    }
}

enum Operator {
    ADD('+', 1), SUBTRACT('-', 1),
    MULTIPLY('*', 2), DIVIDE('/', 2),
    LEFT_BRACKET('(', 3), RIGHT_BRACKET(')', 3); //括號(hào)優(yōu)先級(jí)最高
    char value;
    int priority;

    Operator(char value, int priority) {
        this.value = value;
        this.priority = priority;
    }

    /**
     * 比較兩個(gè)符號(hào)的優(yōu)先級(jí)
     *
     * @param c1
     * @param c2
     * @return c1的優(yōu)先級(jí)是否比c2的高，高則返回正數(shù)元媚，等于返回0轧叽，小于返回負(fù)數(shù)
     */
    public static int cmp(char c1, char c2) {
        int p1 = 0;
        int p2 = 0;
        for (Operator o : Operator.values()) {
            if (o.value == c1) {
                p1 = o.priority;
            }
            if (o.value == c2) {
                p2 = o.priority;
            }
        }
        return p1 - p2;
    }

    /**
     * 枚舉出來(lái)的才視為運(yùn)算符苗沧，用于擴(kuò)展
     *
     * @param c
     * @return
     */
    public static boolean isOperator(char c) {
        for (Operator o : Operator.values()) {
            if (o.value == c) {
                return true;
            }
        }
        return false;
    }
}