原文在這里
表達式
前綴表達式(波蘭表達式)
- 前綴表達式又稱波蘭式,前綴表達式的運算符位于操作數之前
- 舉例說明： (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);*/
}
原文在這里
)
+://+request.getServerName()+:+request.getServer)
