原文在這里

表達式

前綴表達式(波蘭表達式)

前綴表達式又稱波蘭式,前綴表達式的運算符位于操作數之前

舉例說明： (3+4)×5-6 對應的前綴表達式就是 - × + 3 4 5 6

前綴表達式求值

前綴表達式的計算機求值

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

例如: (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，由此得出最終結果

中綴表達式

中綴表達式

中綴表達式就是常見的運算表達式，如(3+4)×5-6

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

中綴表達式對于我們人來好搞,計算機他算不算明白,就離譜

計算機不知道怎么算這個優先級

后綴表達式(逆波蘭表達式)

后綴表達式

后綴表達式又稱逆波蘭表達式,與前綴表達式相似，只是運算符位于操作數之后

中舉例說明： (3+4)×5-6 對應的后綴表達式就是 3 4 + 5 × 6 –

再比如:

正常的表達式逆波蘭表達式

a+b	a b +
a+(b-c)	a b c - +
a+(b-c)*d	a b c – d * +
a+d*(b-c)	a d b c - * +
a=1+3	a 1 3 + =

后綴表達式的計算機求值

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

例如: (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，由此得出最終結果

我們完成一個逆波蘭計算器，要求完成如下任務:

輸入一個逆波蘭表達式(后綴表達式)，使用棧(Stack), 計算其結果

支持小括號和多位數整數，因為這里我們主要講的是數據結構，因此計算器進行簡化，只支持對整數的計算。

思路分析

代碼完成

package com.atguigu.stack;/*** ClassName: <br/>* Description: <br/>* Date: 2021-02-20 14:27 <br/>* @project data_algorithm* @package com.atguigu.stack*/import java.util.ArrayList; import java.util.List; import java.util.Stack;public class PolandNotation {} //編寫一個類 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;}} //完成對逆波蘭表達式的運算 /** 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()); } //將一個逆波蘭表達式， 依次將數據和運算符 放入到 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;} //方法：將 中綴表達式轉成對應的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 [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–] //方法：將得到的中綴表達式對應的List => 后綴表達式對應的List public 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);} else if (item.equals("(")) {s1.push(item);} else if (item.equals(")")) {//如果是右括號“)”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄while(!s1.peek().equals("(")) {s2.add(s1.pop());}s1.pop();//!!! 將 ( 彈出 s1棧， 消除小括號} else {//當item的優先級小于等于s1棧頂運算符, 將s1棧頂的運算符彈出并加入到s2中，再次轉到(4.1)與s1中新的棧頂運算符相比較//問題：我們缺少一個比較優先級高低的方法while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) {s2.add(s1.pop());}//還需要將item壓入棧s1.push(item);}}//將s1中剩余的運算符依次彈出并加入s2while(s1.size() != 0) {s2.add(s1.pop());}return s2; //注意因為是存放到List, 因此按順序輸出就是對應的后綴表達式對應的List}

執行

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)); // ?/*//先定義給逆波蘭表達式//(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);*/ }

原文在這里

總結

以上是生活随笔為你收集整理的前缀中缀后缀表达式的计算求值的全部內容，希望文章能夠幫你解決所遇到的問題。

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