1 前綴表達式介紹

前綴表達式又稱波蘭式，前綴表達式的運算符位于操作數之前
舉例說明： (3+4)×5-6 對應的前綴表達式就是 - × + 3 4 5 6

1.1 前綴表達式的計算機求值過程

從右至左掃描表達式，遇到數字時，將數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（棧頂元素和次頂元素），并將結果入棧；重復上述過程直到表達式最左端，最后運算得出的值即為表達式的結果。

1.2 前綴表達式的計算過程舉例說明

例如: (3+4)×5-6 對應的前綴表達式就是 - × + 3 4 5 6 , 針對前綴表達式求值步驟如下:

從右至左掃描，將6、5、4、3壓入堆棧

遇到+運算符，因此彈出3和4（3為棧頂元素，4為次頂元素），計算出3+4的值，得7，再將7入棧

接下來是×運算符，因此彈出7和5，計算出7×5=35，將35入棧

最后是-運算符，計算出35-6（先彈出的數—后彈出的數）的值，即29，由此得出最終結果

2 中綴表達式介紹

中綴表達式就是常見的運算表達式，如(3+4)×5-6
中綴表達式的求值是我們人最熟悉的，但是對計算機來說卻不好操作(前面我們講的案例就能看的這個問題)，因此，在計算結果時，往往會將中綴表達式轉成其它表達式來操作(一般轉成后綴表達式.)

關于用中綴表達式實現簡單四則運算計算器情況下面鏈接對應的博文

https://blog.csdn.net/weixin_40139164/article/details/108964924

3 后綴表達式介紹

后綴表達式又稱逆波蘭表達式,與前綴表達式相似，只是運算符位于操作數之后
舉例說明： (3+4)×5-6 對應的后綴表達式就是 3 4 + 5 × 6 –

3.1 后綴表達式的計算機求值過程

從左至右掃描表達式，遇到數字時，將數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（次頂元素 和 棧頂元素），并將結果入棧；重復上述過程直到表達式最右端，最后運算得出的值即為表達式的結果。

3.2 后綴表達式的計算過程舉例說明

例如: (3+4)×5-6 對應的后綴表達式就是 3 4 + 5 × 6 - , 針對后綴表達式求值步驟如下:

從左至右掃描，將3和4壓入堆棧；

遇到+運算符，因此彈出4和3（4為棧頂元素，3為次頂元素），計算出3+4的值，得7，再將7入棧；

將5入棧；

接下來是×運算符，因此彈出5和7，計算出7×5=35，將35入棧；

將6入棧；

最后是-運算符，計算出35-6（后彈出的數—先彈出的數）的值，即29，由此得出最終結果

3.3 實現逆波蘭計算器

代碼實現：

import java.util.ArrayList; import java.util.List; import java.util.Stack;public class PolandNotation {public static void main(String[] args) {//先定義給逆波蘭表達式//(30+4)×5-6 => 30 4 + 5 × 6 - => 164// 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + //測試 //說明為了方便，逆波蘭表達式 的數字和符號使用空格隔開//String suffixExpression = "30 4 + 5 * 6 -";String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76//思路//1. 先將 "3 4 + 5 × 6 - " => 放到ArrayList中//2. 將 ArrayList 傳遞給一個方法，遍歷 ArrayList 配合棧 完成計算List<String> list = getListString(suffixExpression);System.out.println("rpnList=" + list);int res = calculate(list);System.out.println("計算的結果是=" + res);}//將一個逆波蘭表達式， 依次將數據和運算符 放入到 ArrayList中public static List<String> getListString(String suffixExpression) {//將 suffixExpression 分割String[] split = suffixExpression.split(" ");List<String> list = new ArrayList<String>();for(String ele: split) {list.add(ele);}return list;}//完成對逆波蘭表達式的運算/** 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，由此得出最終結果*/public static int calculate(List<String> ls) {// 創建棧, 只需要一個棧即可Stack<String> stack = new Stack<String>();// 遍歷 lsfor (String item : ls) {// 這里使用正則表達式來取出數if (item.matches("\\d+")) { // 匹配的是多位數// 入棧stack.push(item);} else {// pop出兩個數，并運算， 再入棧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("運算符有誤");}//把res 入棧stack.push("" + res);}}//最后留在stack中的數據是運算結果return Integer.parseInt(stack.pop());}}

4 中綴表達式轉后綴表達式

思路分析：

1、初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；
2、從左至右掃描中綴表達式；
3、遇到操作數時，將其壓s2；
4、遇到運算符時，比較其與s1棧頂運算符的優先級：
?? 4.1如果s1為空，或棧頂運算符為左括號“(”，則直接將此運算符入棧；
?? 4.2否則，若優先級比棧頂運算符的高，也將運算符壓入s1；
?? 4.3否則，將s1棧頂的運算符彈出并壓入到s2中，再次轉到(4.1)與s1中新的棧頂運算符相比較；
5、遇到括號時： (1) 如果是左括號“(”，則直接壓入s1 (2) 如果是右括號“)”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄
6、重復步驟2至5，直到表達式的最右邊
7、將s1中剩余的運算符依次彈出并壓入s2
8、依次彈出s2中的元素并輸出，結果的逆序即為中綴表達式對應的后綴表達式

舉例說明：

將中綴表達式“1+((2+3)×4)-5”轉換為后綴表達式的過程如下

結果為："1 2 3 + 4 × + 5 –"

代碼實現：

import java.util.ArrayList; import java.util.List; import java.util.Stack;public class PolandNotation {public static void main(String[] args) {// 完成將一個中綴表達式轉成后綴表達式的功能// 說明// 1. 1+((2+3)×4)-5 => 轉成 1 2 3 + 4 × + 5 –// 2. 因為直接對str 進行操作，不方便，因此 先將 "1+((2+3)×4)-5" =》 中綴的表達式對應的List// 即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]// 3. 將得到的中綴表達式對應的List => 后綴表達式對應的List// 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]String expression = "1+((2+3)*4)-5";// 注意表達式List<String> infixExpressionList = toInfixExpressionList(expression);System.out.println("中綴表達式對應的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);System.out.println("后綴表達式對應的List" + suffixExpreesionList); // ArrayList [1,2,3,+,4,*,+,5,–]System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?// 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]// 方法：將得到的中綴表達式對應的List => 后綴表達式對應的Listpublic static List<String> parseSuffixExpreesionList(List<String> ls) {// 定義兩個棧Stack<String> s1 = new Stack<String>(); // 符號棧// 說明：因為s2 這個棧，在整個轉換過程中，沒有pop操作，而且后面我們還需要逆序輸出// 因此比較麻煩，這里我們就不用 Stack<String> 直接使用 List<String> s2// Stack<String> s2 = new Stack<String>(); // 儲存中間結果的棧s2List<String> s2 = new ArrayList<String>(); // 儲存中間結果的Lists2// 遍歷lsfor (String item : ls) {// 如果是一個數，加入s2if (item.matches("\\d+")) {s2.add(item);} // 如果s1為空,則直接將此運算符入棧；else if (s1.size() == 0) {s1.push(item);} // 如果是左括號“(”，則直接壓入s1else if (item.equals("(")) {s1.push(item);// 如果是右括號“)”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄} else if (item.equals(")")) {while (!s1.peek().equals("(")) {s2.add(s1.pop());}s1.pop();// !!! 將 ( 彈出 s1棧， 消除小括號} //棧頂運算符為左括號“(”，則直接將此運算符入棧；else if (s1.peek().equals("(")) {s1.push(item);} else {// 當item的優先級小于等于s1棧頂運算符, 將s1棧頂的運算符彈出并加入到s2中，再次轉到(4.1)與s1中新的棧頂運算符相比較 // 問題：我們缺少一個比較優先級高低的方法while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {s2.add(s1.pop());}// 否則，若優先級比棧頂運算符的高，也將運算符壓入s1；// 還需要將item壓入棧s1.push(item);}}// 將s1中剩余的運算符依次彈出并加入s2while (s1.size() != 0) {s2.add(s1.pop());}return s2; // 注意因為是存放到List, 因此按順序輸出就是對應的后綴表達式對應的List}// 方法：將 中綴表達式轉成對應的List// s="1+((2+3)×4)-5";public static List<String> toInfixExpressionList(String s) {// 定義一個List,存放中綴表達式 對應的內容List<String> ls = new ArrayList<String>();int i = 0; // 這時是一個指針，用于遍歷 中綴表達式字符串String str; // 對多位數的拼接char c; // 每遍歷到一個字符，就放入到cdo {// 如果c是一個非數字，我需要加入到lsif ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {ls.add("" + c);i++; // i需要后移} else { // 如果是一個數，需要考慮多位數str = ""; // 先將str 置成"" '0'[48]->'9'[57]while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {str += c;// 拼接i++;}ls.add(str);}} while (i < s.length());return ls;// 返回}// 將一個逆波蘭表達式， 依次將數據和運算符 放入到 ArrayList中public static List<String> getListString(String suffixExpression) {// 將 suffixExpression 分割String[] split = suffixExpression.split(" ");List<String> list = new ArrayList<String>();for (String ele : split) {list.add(ele);}return list;}// 完成對逆波蘭表達式的運算/** 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，由此得出最終結果*/public static int calculate(List<String> ls) {// 創建棧, 只需要一個棧即可Stack<String> stack = new Stack<String>();// 遍歷 lsfor (String item : ls) {// 這里使用正則表達式來取出數if (item.matches("\\d+")) { // 匹配的是多位數// 入棧stack.push(item);} else {// pop出兩個數，并運算， 再入棧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("運算符有誤");}// 把res 入棧stack.push("" + res);}}// 最后留在stack中的數據是運算結果return Integer.parseInt(stack.pop());}}//編寫一個類 Operation 可以返回一個運算符 對應的優先級 class Operation {private static int ADD = 1;private static int SUB = 1;private static int MUL = 2;private static int DIV = 2;// 寫一個方法，返回對應的優先級數字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:System.out.println("不存在該運算符" + operation);break;}return result;}}

?

總結

以上是生活随笔為你收集整理的前缀表达式（波兰表达式）介绍及其代码实现（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。