后綴表達式(Java中綴表達式怎么轉后綴表達式)

一、棧

1、棧的基本介紹

棧是?個先?后出的有序列表。棧(stack)是限制線性表中元素的插?和刪除只能在線性表的同?端進?的?種特殊線性表。允許插?和刪除的?端,為變化的?端,稱為棧頂(Top),另?端為固定的?端,稱為棧底(Bottom)。

根據棧的定義可知,最先放?棧中元素在棧底,最后放?的元素在棧頂,?刪除元素剛好相反,最后放?的元素最先刪除,最先放?的元素最后刪除。

2、棧的底層實現

(1)創建一個類,模擬棧

maxSize :棧的最大容量

top :表示棧頂

stack :數組用來存儲數據

publicclassStacks{publicintmaxSize;publicinttop;publicint[]stack;//構造器,傳入棧的最大容量publicStacks(intmaxSize){this.maxSize=maxSize;//初始化棧頂的位置為-1,?？誸op=-1;//初始化數組,最大容量為棧的容量stack=newint[maxSize];}}

(2)判斷?？蘸蜅M

? 棧滿

//因為底層是數組存儲數據,所以索引從0開始,//判斷條件為top==maxSize-1publicbooleanisFull(){returntop==maxSize-1;}

? ?？?/p>

publicbooleanisempty(){returntop==-1;}

(3)入棧操作

首先判斷是否棧滿,棧滿后則不能繼續添加,先對棧頂進行加一,然后再放入數據。

publicvoidpush(intdata){//判斷是否棧滿if(isFull()){System.out.println("棧滿,無法入棧");return;}top++;stack[top]=data;}

(4)出棧操作

首先判斷?？?出棧操作其實就是將top減一即可,return stack[top--]; 這樣操作是為了讓我們知道出棧的數據是什么。

publicintpop(){if(isEmpty()){thrownewRuntimeException("?？?無法出棧!");}//先出棧,后減減returnstack[top--];}

(5)顯示棧數據

publicvoidshow(){if(isEmpty()){System.out.println("?？?無法顯示!");return;}for(inti=top;i>=0;i--){System.out.printf("stack[%d]=%d\n",i,stack[i]);}}

二、中綴表達式轉后綴表達式

1、拆解中綴表達式

首先將中綴表達式拆解成一個一個的字符,存放到集合中,方便后面我們將中綴轉后綴時的遍歷操作。

首先用split分割操作將原數據分割到數組中存放,然后用增強for循環遍歷并同時存放到創建好的stringList集合中。

publicstaticList<String>endList(Strings){String[]s1=s.split("");List<String>stringList=newArrayList<>();for(Strings2:s1){stringList.add(s2);}returnstringList;}

補充運算符優先級的判斷

后面我們轉換成后綴表達式時,需要判斷運算符的優先級。

publicstaticintCalcu(Strings){charch=s.charAt(0);if(ch=='-'||ch=='+'){return0;}elseif(ch=='*'||ch=='/'){return1;}return-1;}

2、中綴轉后綴的算法

• 初始化兩個棧:運算符棧s1和儲存中間結果的棧s2

• 從左至右掃描中綴表達式

• 遇到操作數時,將其壓s2

• 遇到運算符時, 比較其與s1棧頂運算符的優先級

?如果s1為空,或棧頂運算符為左括號“(”,則直接將此運算符入棧

?否則,若優先級比棧項運算符的高,也將運算符壓入s1

?否則,將s1棧頂的運算符彈出并壓入到s2中 ,再次與s1中新的棧頂運算符相比較

• 遇到括號時:

? 如果是左括號“(”,則直接壓入s1

? 如果是右括號“)”,則依次彈出s1棧頂的運算符, 并壓入s2,直到遇到左括號為止,此時將這一對括號丟棄

• 重復步驟2至5,直到表達式的最右邊

• 將s1中剩余的運算符依次彈出并壓入s2

• 依次彈出s2中的元素并輸出,結果的逆序即為中綴表達式對應的后綴表達式

3、中綴轉后綴代碼解析

前面的算法說到,首先創建兩個棧一個運算符棧和一個中間結果棧,但是根據上面算法的介紹,中間結果棧沒有出棧操作,就是數據全部是存入,于是在寫代碼的時候我們可以將中間結果棧換成集合來存放數據。

首先用增強for循環遍歷原數據集合,然后進行判斷,如果是數字就放入右方的集合中,如果是運算符就放入左方的符號棧中。

進行運算符判斷,如果是左括號“( ” 就直接放入符號棧中,如果是右括號“ )”,就取出符號棧棧頂的符號放入集合中,直到遇到左括號“( ”,停止將棧頂的符號放入集合中,此時將棧頂出棧也就是去掉括號。

然后繼續進行遍歷放入數據和符號,如果是符號,就與符號棧的棧頂的符號進行比較,要放入運算符的運算級如果小于等于棧頂運算符的運算級,就將棧頂的運算符放入集合中,但下面的圖中,運算符為括號,所以不用管,因為括號有單獨的判斷條件,所以直接放入。

遇到右括號又繼續重復前面的操作。

放入運算符的優先級小于等于棧頂運算符的優先級,于是將棧頂的運算符放入集合中,然后放入的運算符繼續放入符號棧中。

最后循環結束,將符號棧中的運算符依次放入到集合中。

publicstaticList<String>MiddleToEndExpress(List<String>strings){//創建棧,存放運算符Stack<String>operStack=newStack<>();//因為這個棧不需要出棧,所以使用集合List<String>sumList=newArrayList<>();for(Strings:strings){//判斷是否是數據if(s.matches("\\d+")){sumList.add(s);//是數據直接加入}elseif(s.equals("(")){//判斷是否是左括號operStack.push(s);//是,直接放入符號棧}elseif(s.equals(")")){//判斷是否是右括號while(!operStack.peek().equals("(")){//如果棧頂是左括號,退出循環sumList.add(operStack.pop());//不是左括號,就將棧頂的符號依次放入集合}//循環結束,表示棧頂是左括號,把左括號去掉,就去掉了一對括號operStack.pop();}else{//前面的判斷都不是,那就是運算符//如果符號棧為空,并且運算符小于等于棧頂的運算符優先級while(operStack.size()!=0&&Calcu(s)<=Calcu(operStack.peek())){//就將棧頂的運算符放入集合中sumList.add(operStack.pop());}//然后將符號放入符號棧中operStack.push(s);}}//遍歷結束,將符號棧剩余的符號依次取出放入集合中while(operStack.size()!=0){sumList.add(operStack.pop());}//最后將集合返回returnsumList;}

最后結果為:結果中不能含括號,否則轉換錯誤!

4、對后綴表達式進行計算

前面我們已經將中綴轉成后綴表達式了,那么我們只需要直接計算了,首先還是遍歷我們的集合(存放后綴表達式的)將數據暫時放入棧中方便我們操作,然后在遍歷過程中進行判斷,如果是數據就直接放入棧中,如果是運算符就從棧中取出兩個數據進行運算,運算結果又放入棧中,直到棧中只存在一個數據時,就是最后的運算結果。

publicstaticintendCalculator(List<String>stringList){//創建棧,存放數據Stack<String>dataStack=newStack<>();//循環遍歷集合for(Strings:stringList){//正則表達式判斷是否是數據,如果是,就放入棧中if(s.matches("\\d+")){dataStack.push(s);}else{//否則就是運算符//取出兩個數據intnum1=Integer.parseInt(dataStack.pop());intnum2=Integer.parseInt(dataStack.pop());//存放運算結果的變量intres=0;//判斷運算符繼續相應的運算if(s.equals("+")){res=num1+num2;}elseif(s.equals("-")){res=num2-num1;}elseif(s.equals("*")){res=num1*num2;}elseif(s.equals("/")){res=num2/num1;}else{thrownewRuntimeException("運算符異常!");}//運算過后將結果又放入棧中dataStack.push(""+res);}}//最后返回棧中唯一的數據既是結果returnInteger.parseInt(dataStack.pop());}

到此,關于“Java中綴表達式怎么轉后綴表達式”的學習就結束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習,快去試試吧!若想繼續學習更多相關知識,請繼續關注本站網站,小編會繼續努力為大家帶來更多實用的文章!