粗淺看 逆波蘭式算法
來源：程序員人生 發布時間：2016-07-20 08:49:51 閱讀次數：3663次
簡介
逆波蘭表達式是1種10分有用的表達式，它將復雜表達式轉換為可以依托簡單的操作得到計算結果的表達式。它的優勢在于只用兩種簡單操作，入棧和出棧就能夠弄定任何普通表達式的運算。
實現逆波蘭式的算法，難度其實不大，但為何要將看似簡單的中序表達式轉換為復雜的逆波蘭式？緣由就在于這個簡單是相對人類的思惟結構來講的，對計算機而言中序表達式是非常復雜的結構。相對的，逆波蘭式在計算機看來卻是比較簡單易懂的結構。由于計算機普遍采取的內存結構是棧式結構，它履行先進后出的順序。
在程序設計中，可能碰到需要對字符串數學表達式求值的問題，經常使用的方法是解析表達式，生成2叉樹，然落后行計算。編譯器就是使用這類方法來解析程序中的表達式的。這類方法實現起來有點難度，需要斟酌運算符的優先級，括號的配對，堆棧的使用等等。我們正常情況下看到的數學表達式如果用2叉樹遍歷的話，恰好是中序遍歷，故叫做中序表達式。除此以外，還有前序表達式，后序表達式。如：a+b+c(中序)，++abc(前序)，ab+c+(后序)，如果表達式含有×，／，（）等就更復雜了。
后綴表達式也稱逆波蘭表達式 因其使表達式求值變得輕松，所以被普遍使用。
優先級
優先級分為棧內優先級isp(In stack priority)和棧外優先級icp(In coming priority)。除括號之外，其他運算符進棧后優先級都升1，這樣可以體現在中綴表達式中相同優先級的操作符自左向右計算的要求，讓位于棧頂的操作符先退棧并輸出。各運算符及符號優先級：
逆波蘭式
逆波蘭式（Reverse Polish Notation, RPN）同樣成為后綴表達式，更加廣為人知1些，和前綴表達式恰好相反，是將操作符號放置于操作數以后，比如2 + 3 * (5 - 1)用逆波蘭式來表示則是：2 3 5 1 - * +。
逆波蘭式的計算也是從左往右順次讀取，當讀到操作符時，將之前的兩個操作數做計算，然后替換這兩個操作數和操作符，接著讀取，重復此步驟。對這個表達式，讀到5 1 -，得到4，然后讀取乘號，取出前面的3和上1步的計算結果4，并計算，到12，接著讀取加號+，計算2 12 +得到14，計算結束。
上面這個步驟可以很容易的用棧來實現：
從左往右順次讀取表達式，如果是數字則將該數字壓棧，如果是符號，則將之前的兩個數字出棧，做計算后，將計算結果壓棧，直到表達式讀取結束。棧中剩下的1個數就是計算結果。
逆波蘭式看起來像波蘭式反過來，比如5 + 1的波蘭式是+ 5 1，逆波蘭式為5 1 +或1 5 +。也很明顯，逆波蘭式其實不是簡單的將波蘭式反過來，由于，減法和除法中減數和被減數、除數與被除數是不能交換的，即- 10 5和- 5 10就完全不1樣。
Demo
基于JAVA語言
public class InversePoland {
// 9+(3⑴)*3+10/2 = 20
//private static String[] ss = new String[]{"9","+","(","3","-","1",")","*","3","+","10","/","2"};
//24+3⑻*(6⑶)*2+10⑶
private static String[] ss = new String[]{"24","+","3","-","8","*","(","6","-","3",")","*","2","+","10","-","3"};
private static Stack<String> stack = new Stack<String>();
//判斷是不是為數字
private boolean isNum(String s) {
if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("(") || s.equals(")")) {
return false;
}
return true;
}
//獲得符號優先級
private int getPriority(String s) {
if (s.equals("+") || s.equals("-")) {
return 1;
} else if (s.equals("*") || s.equals("/")) {
return 2;
}
return ⑴;
}
//輸出字符串
private void print(String s) {
System.out.print(s + " ");
}
//符號操作
private void symbolOperation(String s) {
if (stack.size() == 0 || s.equals("(")) { //棧為空，直接進棧
stack.push(s);
} else if (s.equals(")")) { //當前字符為“）”,則將棧中（以上的全部出棧輸出
while (stack.size() > 0) {
String pop_s = stack.pop();
if(pop_s.equals("(")) {
break;
} else {
print(pop_s);
}
}
} else {
int pri_s = getPriority(s);
while (stack.size() > 0 ) {
String top_s = stack.lastElement();
if (top_s.equals("(")) {
stack.push(s);
return;
} else {
int top_pri = getPriority(top_s);
if (pri_s <= top_pri) {
String pop_s = stack.pop();
print(pop_s);
} else {
break;
}
}
}
stack.push(s);
}
}
public void test() {
for (String s : ss) {
if (isNum(s)) {
print(s);
} else {
symbolOperation(s);
}
}
while (stack.size() > 0) {
String pop_s = stack.pop();
print(pop_s);
}
}
}
輸出結果
24 3 + 86 3 - * 2 * - 10 + 3 –
業務思想
關于逆波蘭式的學習，是對堆和棧的深入理解，對學習數據結構和算法是必要的。
感受1下逆波蘭式的思考方式，你收獲甚多！
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
