一.中綴變后綴過程分析

給定一個(gè)中綴,最后變?yōu)楹缶Y的過程其實(shí)并不算復(fù)雜,下面分析一下過程:

1. 首先面對(duì)一個(gè)中綴表達(dá)式,我們需要兩個(gè)棧,一個(gè)用來存放運(yùn)算符,即符號(hào)棧 operatorstack,一個(gè)用來存放數(shù)字,運(yùn)算符,即數(shù)字棧 numStack

2. 開始掃描中綴表達(dá)式

3.遇到操作數(shù)時(shí),我們直接壓入數(shù)字棧,即numStack;

4.遇到運(yùn)算符時(shí),需要我們比較一下當(dāng)前符號(hào)與棧頂符號(hào)的優(yōu)先級(jí),這里分以下三種情況

　　4.1 operatorStack為空,好的,我們直接壓入

　　4.2 operatorStack不為空,且當(dāng)前符號(hào)的優(yōu)先級(jí)大于棧頂符號(hào)的優(yōu)先級(jí),我們也直接壓入符號(hào)棧

　　4.3 operatorStack不為空,且當(dāng)前符號(hào)的優(yōu)先級(jí)小于或者等于棧頂符號(hào)的優(yōu)先級(jí),這是我們需要先將operatorStack的棧頂pop出并push到numStack,此處是一個(gè)while循環(huán),直到找出當(dāng)前符號(hào)的優(yōu)先級(jí)大于符號(hào)棧棧頂符 　　　號(hào)的優(yōu)先級(jí)為止,再將當(dāng)前符號(hào)壓入operatorStack.

5.遇到括號(hào)時(shí),有如下操作

　　5.1 如果是? "("? ,直接壓入符號(hào)棧.operatorStack;

　　5.2 如果是? ")"? ,則將符號(hào)棧棧內(nèi)符號(hào)依次彈出,push進(jìn)numStack,直到遇見? "("? 為止,注意的是,這一對(duì)括號(hào)進(jìn)入丟棄狀態(tài),即? "(" 彈出,不會(huì)入任何棧,")" 也不會(huì)入任何棧

6.重復(fù)2-5,掃描中綴表達(dá)式,直到最后結(jié)束

7.最后將符號(hào)棧中符號(hào)順序彈出并加入數(shù)字棧

8.數(shù)字棧numStack輸出,結(jié)果的逆序就是我們要的后綴表達(dá)式

二. 代碼實(shí)現(xiàn)

通過一中的過程分析我們可以看到,數(shù)字棧從頭到輸出之前并沒有進(jìn)行任何彈棧操作,所以為了便于書寫,下面將數(shù)字棧采用arrayList來代替,且易于輸出

并且,如果采用索引去對(duì)中隊(duì)表達(dá)式進(jìn)行掃描的話,會(huì)十分麻煩,所以我們采用以下思路,進(jìn)行轉(zhuǎn)換并計(jì)算結(jié)果

中綴表達(dá)式 -->順序存放中綴表達(dá)式中數(shù)字,操作符以及括號(hào)的list集合 --> 根據(jù)上面一的思路轉(zhuǎn)成存放后綴表達(dá)式的元素的集合 rearList-->遍歷rearList進(jìn)行計(jì)算

代碼如下:

package com.ebiz.stack;import java.util.ArrayList; import java.util.List; import java.util.Stack;/*** @author YHj* @create 2019-07-24 15:51** 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式*/ public class MiddleToRear {public static void main(String[] args) {//不用索引掃描表達(dá)式,將表達(dá)式加入到list中String expression="1+((2+3)*4)-5";//得到中綴表達(dá)式轉(zhuǎn)為list的集合List<String> list=getList(expression);//將中綴表達(dá)式的集合轉(zhuǎn)到后綴表達(dá)式的集合List<String> rearList=getRearList(list);System.out.println("rearList = " + rearList);//輸出計(jì)算結(jié)果 System.out.println(getResult(rearList));}//中綴表達(dá)式的集合轉(zhuǎn)為后綴表達(dá)式的集合private static List<String> getRearList(List<String> list) {ArrayList<String> rearList = new ArrayList<>();//定義符號(hào)棧Stack<String> operatorStack = new Stack<>();//定義集合代替數(shù)字棧,數(shù)字棧本身并沒有pop操作,并且最后要倒敘輸出,隨意用list代替ArrayList<String> numList = new ArrayList<>();for (String s : list) {//如果是個(gè)數(shù)字if (s.matches("\\d+")){numList.add(s);}else if (s.equals("(")){operatorStack.push(s);}else if (s.equals(")")){//符號(hào)棧棧頂直到左括號(hào)之前的符號(hào)放入數(shù)字棧while (!"(".equals(operatorStack.peek())){numList.add(operatorStack.pop());}//把左括號(hào)彈出來 operatorStack.pop();//判斷優(yōu)先級(jí),當(dāng)前符號(hào)優(yōu)先級(jí)小于等于符號(hào)棧棧頂優(yōu)先級(jí),將符號(hào)棧棧頂彈出加入數(shù)字棧,//直到找到當(dāng)前符號(hào)優(yōu)先級(jí)大于符號(hào)棧棧頂優(yōu)先級(jí)為止,再將當(dāng)前符號(hào)加入符號(hào)棧}else{while (operatorStack.size()!=0 && (OperPriority.getPriority(s) <= OperPriority.getPriority(operatorStack.peek()))){numList.add(operatorStack.pop());}//將當(dāng)前符號(hào)加入符號(hào)棧 operatorStack.push(s);}}//將符號(hào)棧中剩余符號(hào)加入數(shù)字棧while (operatorStack.size()!=0){numList.add(operatorStack.pop());}return numList;}//將中綴表達(dá)式的各個(gè)字符存到list集合,方面遍歷private static List<String> getList(String expression) {ArrayList<String> list = new ArrayList<>();int index=0;String str=""; //多位數(shù)的拼接char c; //用于存放每次掃描到的結(jié)果do {//判斷是否為數(shù)字,非數(shù)字直接加入listc=expression.charAt(index);if (c < 48 || c >57){list.add(""+c);}else {//數(shù)字.考慮可能不是一位數(shù),字符串拼接str+=c;if (index == expression.length()-1){list.add(str);}else {if (expression.charAt(index+1) < 48 || expression.charAt(index+1) > 57){list.add(str);str="";}}}index++;}while (index < expression.length());return list;}//輸出計(jì)算結(jié)果private static int getResult(List<String> list) {Stack<String> stack = new Stack<>();for (String s : list) {//匹配數(shù)字if (s.matches("\\d+")){stack.push(s);}else {int num01=Integer.parseInt(stack.pop());int num02=Integer.parseInt(stack.pop());int result=0;if (s.equals("+")){result=num01+num02;}else if (s.equals("-")){result=num02-num01;}else if (s.equals("*")){result=num02*num01;}else if (s.equals("/")){result=num02/num01;}else {throw new RuntimeException("無法解析的字符串");}stack.push(""+result);}}return Integer.parseInt(stack.pop());}}

?上面涉及到的判斷符號(hào)優(yōu)先級(jí)的類

package com.ebiz.stack;/*** @author YHj* @create 2019-07-24 18:14*/ public class OperPriority {private static int AAD =1; //加;private static int SUB =1; //減private static int MUL =2; //乘private static int DIV =2; //除public static int getPriority(String operator){int result=0;switch (operator){case "+":result=AAD;break;case "-":result=SUB;break;case "*":result=MUL;break;case "/":result=DIV;break;default:break;}return result;}}

?

有待完善...

轉(zhuǎn)載于:https://www.cnblogs.com/jiushixihuandaqingtian/p/11241370.html

總結(jié)

以上是生活随笔為你收集整理的数据结构之栈实现中缀转后缀并计算结果的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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