棧的三種表達(dá)式：前綴、中綴和后綴表達(dá)式，后綴也叫逆波蘭表達(dá)式

前綴（波蘭表達(dá)式）

中綴（對(duì)人來(lái)講很好理解，對(duì)于計(jì)算機(jī)來(lái)講就方便了，一般會(huì)把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式）

后綴（逆波蘭表達(dá)式）

計(jì)算過(guò)程

例字

這里就用java自帶的棧了Stack（多位數(shù)也可以）（自己寫(xiě)個(gè)棧也可以，這里為了方便）

（這里輸入的是后綴表達(dá)式，中綴轉(zhuǎn)后綴往下看）

package stack;import java.util.ArrayList; import java.util.List; import java.util.Stack;public class PolandNotation {public static void main(String []args){//先定義一個(gè)逆波蘭表達(dá)式//（3+4）*5-6 => 3 4 + 5 * 6 -//為了方便數(shù)字和符號(hào)使用空格隔開(kāi)String suffixExpression = "3 4 + 5 * 6 -";//思路// 1.先將3 4 + 5 * 6 -放入ArrayList中// 2.將ArrayList 傳遞給一個(gè)方法，遍歷ArrayList 配合棧完成計(jì)算List<String> list = getListString(suffixExpression);int res = calculate(list);System.out.println(res);}//將表達(dá)式，依次將輸入和運(yùn)算符 方法歐ArrayList中public static List<String> getListString(String suffixExperssion){//分割String[] split = suffixExperssion.split(" ");ArrayList<String> list = new ArrayList<>();for (String ele : split){list.add(ele);}return list;}public static int calculate(List<String> ls){//創(chuàng)建棧，只需要一個(gè)棧Stack<String> stack = new Stack<>();//遍歷for (String item : ls){//使用正則取出數(shù)if (item.matches("\\d+")){ //匹配多位數(shù)stack.push(item);}else {//pop出兩個(gè)數(shù)運(yùn)算int num2 = Integer.parseInt(stack.pop());int num1 = Integer.parseInt(stack.pop());int res = 0;if (item.equals("+")){res = num1+num2;}else if (item.equals("-")){res = num1 - num2;}else if (item.equals("*")){res = num1 * num2;}else if (item.equals("/")){res = num1 / num2;}else {throw new RuntimeException("運(yùn)算符有誤");}//res 入棧stack.push(res + "");}}//最后留在stack中的數(shù)是結(jié)果return Integer.parseInt(stack.pop());} }

中綴表達(dá)式 轉(zhuǎn) 后綴表達(dá)式

1）操作步驟：

2）例

代碼幾乎每行都有注釋，根據(jù)思路一步一步分析來(lái)自己實(shí)現(xiàn)一下。

1）中綴轉(zhuǎn)后綴代碼

public static List<String> parseSuffixExpressionList(List<String> ls){//定義兩個(gè)棧Stack<String> s1 = new Stack<>(); //符號(hào)棧//說(shuō)明：因?yàn)镾2棧，并沒(méi)有用到pop，而且后面還需要逆序說(shuō)出，比較麻煩//Stack<String> stack2 = new Stack<>(); //中間結(jié)果的棧//這里就用List來(lái)代替ArrayList<String> s2 = new ArrayList<String>();//遍歷lsfor (String item : ls){//如果是數(shù)就入棧if (item.matches("\\d+")){s2.add(item);} else if (item.equals("(")){s1.push(item);} else if (item.equals(")")){while (!s1.peek().equals("(")){//s1內(nèi)容加入s2s2.add(s1.pop());}s1.pop(); // 將（彈出s1棧} else {//當(dāng)s1棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí) 大于等于 item運(yùn)算符的優(yōu)先級(jí) ，將s1棧頂?shù)倪\(yùn)算符彈出并壓入到s2中，再次轉(zhuǎn)到(4-1)與s1中新的棧頂運(yùn)算符相比較；//這里缺少一個(gè)比較優(yōu)先級(jí)高低的方法while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){s2.add(s1.pop());}//最后還需要將item壓入棧中s1.push(item);}}//將s1中剩下的運(yùn)算符依次彈出加入s2中while (s1.size() != 0){s2.add(s1.pop());}//因?yàn)榇娣帕薒ist里，直接順序輸入就是對(duì)應(yīng)的逆波蘭表達(dá)式return s2;}

2）判斷符號(hào)優(yōu)先級(jí)

//編寫(xiě)一個(gè)類，Operation 可以返回一個(gè)運(yùn)算符 對(duì)應(yīng)的優(yōu)先級(jí) class Operation{private static int ADD = 1;private static int SUB = 1;private static int MUL = 2;private static int DIV = 2;//寫(xiě)一個(gè)方法，返回對(duì)應(yīng)優(yōu)先級(jí)數(shù)字public static int getValue(String operation){int result = 0;switch (operation) {case "+":result = ADD;break;case "-":result = SUB;break;case "*":result = MUL;break;case "/":result = DIV;break;default:result = 0;//這里是棧中是(,那么結(jié)果設(shè)成0，不管什么運(yùn)算符都存進(jìn)來(lái)break;}return result;} }

完整代碼（以及上面的運(yùn)算）

package stack;import java.util.ArrayList; import java.util.List; import java.util.Stack;public class PolandNotation {public static void main(String []args){//完成中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式//說(shuō)明// 1.因?yàn)橹苯訉?duì)str 進(jìn)行操作，不方便， 因此先將"1+((2+3)*4)-5" =》中綴表達(dá)式轉(zhuǎn)成對(duì)應(yīng)的List// 2.即"1+((2+3)*4)-5" =》 ArrayList[1,+,(,(,2,+,3,*,4,),-,5]String expression = "1+((2+3)*4)-5";//中綴表達(dá)式轉(zhuǎn)成ListList<String> list = toInfixExpressionList(expression);System.out.println("中綴表達(dá)式：" + list);//中綴表達(dá)式：[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]//把ArrayList[1,+,(,(,2,+,3,*,4,),-,5] =》"1 2 3 + 4 × + 5 –"List<String> parseSuffixExpressionList = parseSuffixExpressionList(list);System.out.println("后綴表達(dá)式：" + parseSuffixExpressionList);//后綴表達(dá)式：[1, 2, 3, +, 4, *, +, 5, -]//計(jì)算轉(zhuǎn)換后的后綴表達(dá)式int calculate = calculate(parseSuffixExpressionList);System.out.println("后綴表達(dá)式計(jì)算結(jié)果：" + calculate);/*//先定義一個(gè)逆波蘭表達(dá)式//（3+4）*5-6 => 3 4 + 5 * 6 -//測(cè)試(30+4)*5-6//為了方便數(shù)字和符號(hào)使用空格隔開(kāi)String suffixExpression = "30 4 + 5 * 6 -";//思路// 1.先將3 4 + 5 * 6 -放入ArrayList中// 2.將ArrayList 傳遞給一個(gè)方法，遍歷ArrayList 配合棧完成計(jì)算List<String> list = getListString(suffixExpression);int res = calculate(list);System.out.println(res);*/}//方法：將得到的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式具體步驟如下:// //初始化兩個(gè)棧：運(yùn)算符棧s1和儲(chǔ)存中間結(jié)果的棧s2；// //從左至右掃描中綴表達(dá)式；// //遇到操作數(shù)時(shí)，將其壓s2；// //遇到運(yùn)算符時(shí)，比較其與s1棧頂運(yùn)算符的優(yōu)先級(jí)：// //如果s1為空，或棧頂運(yùn)算符為左括號(hào)“(”，則直接將此運(yùn)算符入棧；// //否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的高，也將運(yùn)算符壓入s1；// //否則，將s1棧頂?shù)倪\(yùn)算符彈出并壓入到s2中，再次轉(zhuǎn)到(4-1)與s1中新的棧頂運(yùn)算符相比較；// //遇到括號(hào)時(shí)：(1) 如果是左括號(hào)“(”，則直接壓入s1(2) 如果是右括號(hào)“)”，則依次彈出s1棧頂?shù)倪\(yùn)算符，并壓入s2，直到遇到左括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄// //重復(fù)步驟2至5，直到表達(dá)式的最右邊// //將s1中剩余的運(yùn)算符依次彈出并壓入s2// //依次彈出s2中的元素并輸出，結(jié)果的逆序即為中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式public static List<String> parseSuffixExpressionList(List<String> ls){//定義兩個(gè)棧Stack<String> s1 = new Stack<>(); //符號(hào)棧//說(shuō)明：因?yàn)镾2棧，并沒(méi)有用到pop，而且后面還需要逆序說(shuō)出，比較麻煩//Stack<String> stack2 = new Stack<>(); //中間結(jié)果的棧//這里就用List來(lái)代替ArrayList<String> s2 = new ArrayList<String>();//遍歷lsfor (String item : ls){//如果是數(shù)就入棧if (item.matches("\\d+")){s2.add(item);} else if (item.equals("(")){s1.push(item);} else if (item.equals(")")){while (!s1.peek().equals("(")){//s1內(nèi)容加入s2s2.add(s1.pop());}s1.pop(); // 將（彈出s1棧} else {//當(dāng)s1棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí) 大于等于 item運(yùn)算符的優(yōu)先級(jí) ，將s1棧頂?shù)倪\(yùn)算符彈出并壓入到s2中，再次轉(zhuǎn)到(4-1)與s1中新的棧頂運(yùn)算符相比較；//這里缺少一個(gè)比較優(yōu)先級(jí)高低的方法while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){s2.add(s1.pop());}//最后還需要將item壓入棧中s1.push(item);}}//將s1中剩下的運(yùn)算符依次彈出加入s2中while (s1.size() != 0){s2.add(s1.pop());}//因?yàn)榇娣帕薒ist里，直接順序輸入就是對(duì)應(yīng)的逆波蘭表達(dá)式return s2;}//方法：將字符串中綴表達(dá)式轉(zhuǎn)為L(zhǎng)istpublic static List<String> toInfixExpressionList(String s){//電影以一個(gè)List，存放中綴表達(dá)式ArrayList<String> list = new ArrayList<>();int i = 0;//相當(dāng)于一個(gè)指針，用于遍歷字符串String str;//對(duì)多位數(shù)進(jìn)行拼接char c; //每遍歷到一個(gè)字符就放到c中do {//如果c是一個(gè)非數(shù)字，我們就需要加入到list里if ((c = s.charAt(i)) < 48 || (c= s.charAt(i)) >57){list.add("" + c);i++; //i后移} else { // 如果是一個(gè)數(shù)，需要考慮多位數(shù)str = ""; //str清空while (i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57){str += c; //拼接i++;}list.add(str);}}while(i < s.length());return list;}//將表達(dá)式，依次將輸入和運(yùn)算符 方法歐ArrayList中public static List<String> getListString(String suffixExperssion){//分割String[] split = suffixExperssion.split(" ");ArrayList<String> list = new ArrayList<>();for (String ele : split){list.add(ele);}return list;}public static int calculate(List<String> ls){//創(chuàng)建棧，只需要一個(gè)棧Stack<String> stack = new Stack<>();//遍歷for (String item : ls){//使用正則取出數(shù)if (item.matches("\\d+")){ //匹配多位數(shù)stack.push(item);}else {//pop出兩個(gè)數(shù)運(yùn)算int num2 = Integer.parseInt(stack.pop());int num1 = Integer.parseInt(stack.pop());int res = 0;if (item.equals("+")){res = num1+num2;}else if (item.equals("-")){res = num1 - num2;}else if (item.equals("*")){res = num1 * num2;}else if (item.equals("/")){res = num1 / num2;}else {throw new RuntimeException("運(yùn)算符有誤");}//res 入棧stack.push(res + "");}}//最后留在stack中的數(shù)是結(jié)果return Integer.parseInt(stack.pop());} }//編寫(xiě)一個(gè)類，Operation 可以返回一個(gè)運(yùn)算符 對(duì)應(yīng)的優(yōu)先級(jí) class Operation{private static int ADD = 1;private static int SUB = 1;private static int MUL = 2;private static int DIV = 2;//寫(xiě)一個(gè)方法，返回對(duì)應(yīng)優(yōu)先級(jí)數(shù)字public static int getValue(String operation){int result = 0;switch (operation) {case "+":result = ADD;break;case "-":result = SUB;break;case "*":result = MUL;break;case "/":result = DIV;break;default:result = 0;break;}return result;} } 結(jié)果： 中綴表達(dá)式：[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] 后綴表達(dá)式：[1, 2, 3, +, 4, *, +, 5, -] 后綴表達(dá)式計(jì)算結(jié)果：16

總結(jié)

以上是生活随笔為你收集整理的数据结构 - 栈 （逆波兰计算器）（栈的三种表达式）（前缀、中缀和后缀表达式，后缀也叫逆波兰表达式）（中缀表达式转后缀表达式实现步骤及完整代码）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。