前言
看這篇文章之前袱箱，我們先要明確一些概念庆揪。
1.前綴表達式又稱波蘭式式曲，前綴表達式的運算符位于操作數(shù)之前。比如:- × + 3 4 5 6
2.中綴表達式就是常見的運算表達式缸榛，如(3+4)×5-6
3.后綴表達式又稱逆波蘭表達式,與前綴表達式相似吝羞，只是運算符位于操作數(shù)之后,比如:3 4 + 5 × 6 -
人類最熟悉的一種表達式1+2，(1+2)3仔掸，3+42+4等都是中綴表示法脆贵。對于人們來說，也是最直觀的一種求值方式起暮，先算括號里的卖氨，然后算乘除筒捺，最后算加減系吭，但是，計算機處理中綴表達式卻并不方便则吟。
然后我們還需明確一些概念，下面通過我們最熟悉的中綴表達式畫出一棵語法樹來直觀認識一下前后綴表達式的生成敬扛。以A+B*(C-D)-E*F為例：
中綴表達式得名于它是由相應(yīng)的語法樹的中序遍歷的結(jié)果得到的谍珊。上面的二叉樹中序遍歷的結(jié)果就是A+B*(C-D)-E*F。
前綴表達式是由相應(yīng)的語法樹的前序遍歷的結(jié)果得到的。上圖的前綴表達式為- + A * B - C D * E F
后綴表達式又叫做逆波蘭式陕悬。它是由相應(yīng)的語法樹的后序遍歷的結(jié)果得到的。上圖的后綴表達式為：A B C D - * + E F * -
下面我們關(guān)注兩個點：
1.如何根據(jù)一個逆波蘭表達式求出運算結(jié)果？
2.如果將一個中綴表達式轉(zhuǎn)換成后綴表達式（逆波蘭表達式）
一.通過逆波蘭表達式計算結(jié)果
我們先看一個例子...后綴表達式3 4 + 5 × 6 -的計算
1.從左至右掃描，將3和4壓入堆棧耐版；
2.遇到+運算符，因此彈出4和3（4為棧頂元素腺阳，3為次頂元素，注意與前綴表達式做比較）痛侍，計算出3+4的值赵哲，得7，再將7入棧；
3.將5入棧扒最；
4.接下來是×運算符，因此彈出5和7强挫，計算出7×5=35，將35入棧；
5.將6入棧；
6.最后是-運算符劝萤，計算出35-6的值，即29，由此得出最終結(jié)果缆娃。
從上面的過程我們?nèi)绾尉帉懘a實現(xiàn)呢椭住？
可以采用一個輔助的棧來實現(xiàn)計算，掃描表達式從左往右進行，如果掃描到數(shù)值兽肤，則壓進輔助棧中，如果掃描到運算符绪抛，則從輔助棧中彈出兩個數(shù)值參與運算，并將結(jié)果壓進到棧中电禀，當掃描表達式結(jié)束后幢码，棧頂?shù)臄?shù)值就是表達式結(jié)果。
下面是代碼實現(xiàn)(Java）
/**
* 通過逆波蘭表達式計算結(jié)果
* @param ls
* @return
*/
//求逆波蘭表達式的值
public static int calcRevPolishNotation(String express){
Stack<String> stack = new Stack<>();
for (int i = 0; i <express.length() ;i++) {
// 普通數(shù)值的處理
if ((express.charAt(i) + "").matches("\\d")){
stack.push(express.charAt(i) + "");
// + - * / 運算符的處理
}else if ((express.charAt(i) + "").matches("[\\+\\-\\*\\/]")){
String k1 = stack.pop();
String k2 = stack.pop();
// 計算結(jié)果
int res = calcValue(k1, k2, (express.charAt(i) + ""));
stack.push(res+"");
}
}
return Integer.valueOf(stack.pop());
}
//根據(jù)運算符計算結(jié)果
private static int calcValue(String k1, String k2, String c) {
switch(c){
case "+":
return Integer.valueOf(k1)+Integer.valueOf(k2);
case "-":
return Integer.valueOf(k2)-Integer.valueOf(k1);
case "*":
return Integer.valueOf(k1)*Integer.valueOf(k2);
case "/":
return Integer.valueOf(k2)/Integer.valueOf(k1);
default:
throw new RuntimeException("沒有該類型的運算符尖飞！");
}
}
二.中綴表達式轉(zhuǎn)換為后綴表達式（逆波蘭表達式）
中綴表達式轉(zhuǎn)后綴表達式主要用到了棧進行運算符處理症副，隊列進行排序輸出，規(guī)則為：
1.數(shù)字直接入隊列
2.運算符要與棧頂元素比較
?①棧為空直接入棧
?②運算符優(yōu)先級大于棧頂元素優(yōu)先級則直接入棧
?③小于或等于則出棧入列政基，再與棧頂元素進行比較贞铣，直到運算符優(yōu)先級小于棧頂元
????素優(yōu)先級后，操作符再入棧
3.操作符是 ( 則無條件入棧
4.操作符為 )沮明，則依次出棧入列辕坝，直到匹配到第一個(為止，此操作符直接舍棄荐健，(直接出棧舍棄
代碼實現(xiàn)(Java)
/**
* 將中綴表達式轉(zhuǎn)換為后綴表達式（逆波蘭表達式）
* @param express
* @return
*/
public static String transfer(String express){
Stack<String> stack = new Stack<>();
List<String> list= new ArrayList<>();
for (int i=0;i<express.length();i++){
if ((express.charAt(i)+"").matches("\\d")){
list.add(express.charAt(i)+"");
}else if((express.charAt(i)+"").matches("[\\+\\-\\*\\/]")){
//如果stack為空
if (stack.isEmpty()){
stack.push(express.charAt(i)+"");
continue;
}
//不為空
//上一個元素不為（酱畅，且當前運算符優(yōu)先級小于上一個元素則，將比這個運算符優(yōu)先級大的元素全部加入到隊列中
while (!stack.isEmpty()&&!stack.lastElement().equals("(")&&!comparePriority(express.charAt(i)+"",stack.lastElement())){
list.add(stack.pop());
}
stack.push(express.charAt(i)+"");
}else if(express.charAt(i)=='('){
//遇到左小括號無條件加入
stack.push(express.charAt(i) + "");
}else if(express.charAt(i)==')'){
//遇到右小括號江场，則尋找上一堆小括號纺酸，然后把中間的值全部放入隊列中
while(!("(").equals(stack.lastElement())){
list.add(stack.pop());
}
//上述循環(huán)停止，這棧頂元素必為"("
stack.pop();
}
}
//將棧中剩余元素加入到隊列中
while (!stack.isEmpty()){
list.add(stack.pop());
}
StringBuffer stringBuffer = new StringBuffer();
//變成字符串
for (String s : list) {
stringBuffer.append(s);
}
return stringBuffer.toString();
}
/**
* 比較運算符的優(yōu)先級
* @param o1
* @param o2
* @return
*/
public static boolean comparePriority(String o1,String o2){
return getPriorityValue(o1)>getPriorityValue(o2);
}
/**
* 獲得運算符的優(yōu)先級
* @param str
* @return
*/
private static int getPriorityValue(String str) {
switch(str){
case "+":
return 1;
case "-":
return 1;
case "*":
return 2;
case "/":
return 2;
default:
throw new RuntimeException("沒有該類型的運算符址否！");
}
}
