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á)式的功能//說明//1. 1+((2+3)×4)-5 => 轉(zhuǎn)成 1 2 3 + 4 × + 5 –//2. 因?yàn)橹苯訉tr 進(jìn)行操作，不方便，因此 先將 "1+((2+3)×4)-5" =》 中綴的表達(dá)式對應(yīng)的List// 即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]//3. 將得到的中綴表達(dá)式對應(yīng)的List => 后綴表達(dá)式對應(yīng)的List// 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]String expression = "1+((2+3)*4)-5";//注意表達(dá)式 List<String> infixExpressionList = toInfixExpressionList(expression);System.out.println("中綴表達(dá)式對應(yīng)的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);System.out.println("后綴表達(dá)式對應(yīng)的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–] System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?/*//先定義給逆波蘭表達(dá)式//(30+4)×5-6 => 30 4 + 5 × 6 - => 164// 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + //測試 //說明為了方便，逆波蘭表達(dá)式 的數(shù)字和符號使用空格隔開//String suffixExpression = "30 4 + 5 * 6 -";String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76//思路//1. 先將 "3 4 + 5 × 6 - " => 放到ArrayList中//2. 將 ArrayList 傳遞給一個方法，遍歷 ArrayList 配合棧 完成計(jì)算List<String> list = getListString(suffixExpression);System.out.println("rpnList=" + list);int res = calculate(list);System.out.println("計(jì)算的結(jié)果是=" + res);*/}//即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]//方法：將得到的中綴表達(dá)式對應(yīng)的List => 后綴表達(dá)式對應(yīng)的Listpublic static List<String> parseSuffixExpreesionList(List<String> ls) {//定義兩個棧Stack<String> s1 = new Stack<String>(); // 符號棧//說明：因?yàn)閟2 這個棧，在整個轉(zhuǎn)換過程中，沒有pop操作，而且后面我們還需要逆序輸出//因此比較麻煩，這里我們就不用 Stack<String> 直接使用 List<String> s2//Stack<String> s2 = new Stack<String>(); // 儲存中間結(jié)果的棧s2List<String> s2 = new ArrayList<String>(); // 儲存中間結(jié)果的Lists2//遍歷lsfor(String item: ls) {//如果是一個數(shù)，加入s2if(item.matches("\\d+")) {s2.add(item);} else if (item.equals("(")) {s1.push(item);} else if (item.equals(")")) {//如果是右括號“)”，則依次彈出s1棧頂?shù)倪\(yùn)算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄while(!s1.peek().equals("(")) {s2.add(s1.pop());}s1.pop();//!!! 將 ( 彈出 s1棧， 消除小括號} else {//當(dāng)item的優(yōu)先級小于等于s1棧頂運(yùn)算符, 將s1棧頂?shù)倪\(yùn)算符彈出并加入到s2中，再次轉(zhuǎn)到(4.1)與s1中新的棧頂運(yùn)算符相比較//問題：我們?nèi)鄙僖粋€比較優(yōu)先級高低的方法while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) {s2.add(s1.pop());}//還需要將item壓入棧s1.push(item);}}//將s1中剩余的運(yùn)算符依次彈出并加入s2while(s1.size() != 0) {s2.add(s1.pop());}return s2; //注意因?yàn)槭谴娣诺絃ist, 因此按順序輸出就是對應(yīng)的后綴表達(dá)式對應(yīng)的List}//方法：將 中綴表達(dá)式轉(zhuǎn)成對應(yīng)的List// s="1+((2+3)×4)-5";public static List<String> toInfixExpressionList(String s) {//定義一個List,存放中綴表達(dá)式 對應(yīng)的內(nèi)容List<String> ls = new ArrayList<String>();int i = 0; //這時是一個指針，用于遍歷 中綴表達(dá)式字符串String str; // 對多位數(shù)的拼接char c; // 每遍歷到一個字符，就放入到cdo {//如果c是一個非數(shù)字，我需要加入到lsif((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57) {ls.add("" + c);i++; //i需要后移} else { //如果是一個數(shù)，需要考慮多位數(shù)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;//返回}//將一個逆波蘭表達(dá)式， 依次將數(shù)據(jù)和運(yùn)算符 放入到 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;}//完成對逆波蘭表達(dá)式的運(yùn)算/** 1)從左至右掃描，將3和4壓入堆棧；2)遇到+運(yùn)算符，因此彈出4和3（4為棧頂元素，3為次頂元素），計(jì)算出3+4的值，得7，再將7入棧；3)將5入棧；4)接下來是×運(yùn)算符，因此彈出5和7，計(jì)算出7×5=35，將35入棧；5)將6入棧；6)最后是-運(yùn)算符，計(jì)算出35-6的值，即29，由此得出最終結(jié)果*/public static int calculate(List<String> ls) {// 創(chuàng)建給棧, 只需要一個棧即可Stack<String> stack = new Stack<String>();// 遍歷 lsfor (String item : ls) {// 這里使用正則表達(dá)式來取出數(shù)if (item.matches("\\d+")) { // 匹配的是多位數(shù)// 入棧stack.push(item);} else {// pop出兩個數(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ù)據(jù)是運(yùn)算結(jié)果return Integer.parseInt(stack.pop());}}//編寫一個類 Operation 可以返回一個運(yùn)算符 對應(yīng)的優(yōu)先級 class Operation {private static int ADD = 1;private static int SUB = 1;private static int MUL = 2;private static int DIV = 2;//寫一個方法，返回對應(yīng)的優(yōu)先級數(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:System.out.println("不存在該運(yùn)算符" + operation);break;}return result;}} //來源——尚硅谷韓順平老師

總結(jié)

以上是生活随笔為你收集整理的逆波兰计算器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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