目錄

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

圖解

代碼實(shí)現(xiàn)過程：

完整代碼：?

利用后綴表達(dá)式求值：

完整代碼：

---

?

首先我們得先了解逆波蘭表達(dá)式。

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

所謂的中綴表達(dá)式其實(shí)就是我們平時(shí)寫的例如：；而它的后綴表達(dá)式（也成為逆波蘭表達(dá)式）為?；

后綴表達(dá)式：指的是不包含括號，運(yùn)算符放在兩個(gè)運(yùn)算對象的后面，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行（不再考慮運(yùn)算符的優(yōu)先規(guī)則）。

我們?nèi)绻贸绦騺?span style="color:#956fe7;">進(jìn)行四則混合運(yùn)算最重要的就是將輸入的中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式。

首先我們假設(shè)運(yùn)算符中只有 加 減 乘 除 和 括號不然的話程序太復(fù)雜了（其實(shí)是我不會寫【哭】）。

圖解

代碼實(shí)現(xiàn)過程：

首先我們先寫一個(gè)方法 返回值是動態(tài)字符串?dāng)?shù)組（為了后面好計(jì)算），形參為字符串類型（因?yàn)檩斎胫挡恢挥袛?shù)字還有運(yùn)算符）。這里會用到棧所以也定義一個(gè)棧。

    public ArrayList<String> midChangeEng(String str) {//這里用動態(tài)數(shù)組就不用擔(dān)心不夠用ArrayList<String> ret = new ArrayList<String>();Stack<Character> stack = new Stack<>();}

此時(shí)再創(chuàng)建一個(gè)新方法用來判斷傳入字符是不是運(yùn)算符?

    public boolean isOperator(char s) {if (s == '+' || s == '-' || s == '*' || s == '/' || s == '(' || s == ')') {return true;}return false;}

我們再利用運(yùn)算符再ASCII碼中的位置，創(chuàng)建一個(gè)數(shù)組用來表示它們的優(yōu)先級

int[] able = {1,0,0,0,0,1};//分別代表 * + (null) - (null) / 的優(yōu)先級 

?利用循環(huán)遍歷字符串

        //遍歷字符串for (int i = 0; i < str.length(); i++) {char a = str.charAt(i);String tmp = "";//用來暫時(shí)存儲出棧的數(shù)字if (isOperator(a)) {//是操作數(shù)}else{//如果是數(shù)字就放到ret中}}return ret;

對操作數(shù)的操作 ，可是此段代碼中重復(fù)代碼過多，所以可以將其封裝成一個(gè)方法。

            if (isOperator(a)) {//是操作數(shù)switch (a) {case '+'://判斷如果優(yōu)先級不大于棧頂?shù)脑啬敲淳拖瘸鰲Ｔ谌霔f(!stack.isEmpty()) {//出棧while(!stack.isEmpty() && stack.peek() != '(' && able[(int)stack.peek() - 42] >= able[(int)a-42]) {String b = "";b += stack.pop();ret.add(b);}}stack.push(a);break;case '-':if(!stack.isEmpty()) {//出棧while(!stack.isEmpty() && stack.peek() != '(' && able[(int)stack.peek() - 42] >= able[(int)a-42]) {String b = "";b += stack.pop();ret.add(b);}}stack.push(a);break;case '*':if(!stack.isEmpty()) {//出棧while(!stack.isEmpty() && stack.peek() != '(' && able[(int)stack.peek() - 42] >= able[(int)a-42]) {String b = "";b += stack.pop();ret.add(b);}}stack.push(a);break;case '/':if(!stack.isEmpty()) {//出棧while(!stack.isEmpty() && stack.peek() != '(' && able[(int)stack.peek() - 42] >= able[(int)a-42]) {String b = "";b += stack.pop();ret.add(b);}}stack.push(a);break;case '(':stack.push(a);break;case ')':while(!stack.isEmpty() && stack.peek() != '(') {String b = "";b += stack.pop();ret.add(b);}stack.pop();//刪除‘(’break;}}

?如果是數(shù)字就進(jìn)行以下操作

            else{//如果是數(shù)字就放到ret中String tmp = "";while(i < str.length() && !isOperator(str.charAt(i))) {//數(shù)字有可能是多位的tmp += str.charAt(i);i++;}i--;ret.add(tmp);}

再出函數(shù)之前要先將棧里面的全部導(dǎo)出來

        //將棧里面剩余的全部出棧while(!stack.isEmpty()) {String b = "";b += stack.pop();ret.add(b);}return ret;

完整代碼：?

    public static ArrayList<String> midChangeEng(String str) {//這里用動態(tài)數(shù)組就不用擔(dān)心不夠用ArrayList<String> ret = new ArrayList<String>();Stack<Character> stack = new Stack<>();int[] able = {1,0,0,0,0,1};//分別代表 * + (null) - (null) / 的優(yōu)先級//遍歷字符串for (int i = 0; i < str.length(); i++) {char a = str.charAt(i);if (isOperator(a)) {//是操作數(shù)switch (a) {case '+'://判斷如果優(yōu)先級不大于棧頂?shù)脑啬敲淳拖瘸鰲Ｔ谌霔bcd(ret, stack, able, a);break;case '-':abcd(ret, stack, able, a);break;case '*':abcd(ret, stack, able, a);break;case '/':abcd(ret, stack, able, a);break;case '(':stack.push(a);break;case ')':while(!stack.isEmpty() && stack.peek() != '(') {String b = "";b += stack.pop();ret.add(b);}stack.pop();//刪除‘(’break;}}else{//如果是數(shù)字就放到ret中String tmp = "";while(i < str.length() && !isOperator(str.charAt(i))) {//數(shù)字有可能是多位的tmp += str.charAt(i);i++;}i--;ret.add(tmp);}}//將棧里面剩余的全部出棧while(!stack.isEmpty()) {String b = "";b += stack.pop();ret.add(b);}return ret;}

利用后綴表達(dá)式求值：

這部分比較簡單所以就直接展示了

完整代碼：

        public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (int i = 0; i < tokens.length; i++) {if (isOperator(tokens[i])) {int num2 = stack.pop();int num1 = stack.pop();switch(tokens[i].charAt(0)) {case '+':stack.push(num1 + num2);break;case '-':stack.push(num1 - num2);break;case '*':stack.push(num1 * num2);break;case '/':stack.push(num1 / num2);break;}}else {stack.push(Integer.parseInt(tokens[i]));}}return stack.pop();}public boolean isOperator(String str) {if (str.length() != 1) {return false;}if (str.charAt(0) == '+' || str.charAt(0) == '-' || str.charAt(0) == '*' || str.charAt(0) == '/') {return true;}return false;}