您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“java數(shù)據(jù)結(jié)構(gòu)中棧怎么應(yīng)用”,感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“java數(shù)據(jù)結(jié)構(gòu)中棧怎么應(yīng)用”吧!
1.聲明一個(gè)棧接口SStack
package ch05; public interface SStack <T>{ boolean isEmpty(); // 判斷棧是否為空 void push(T x); // 元素x入棧 T pop(); // 出棧,返回棧頂元素 T peek(); // 返回棧頂元素,但不出棧 }
2. 定義順序棧類SeqStack<T>,包括數(shù)據(jù)元素的對(duì)象數(shù)組和棧頂元素下標(biāo)兩個(gè)私有成員變量,構(gòu)造方法可實(shí)例化容量為size大小的空順序棧,調(diào)用類中成員方法實(shí)現(xiàn)順序棧的入棧、出棧、獲取棧頂元素等操作,重寫toString()方法獲取順序棧的字符串描述。
package ch05; public class SeqStack <T> implements SStack<T>{ Object[] element; int top; // 構(gòu)造方法,創(chuàng)建一個(gè)空棧,存儲(chǔ)容量大小size public SeqStack(int size){ element=new Object[size]; top=-1; } // 判斷棧是否為空 @Override public boolean isEmpty() { return top==-1; } // 元素x入棧 @Override public void push(T x) { if (x==null){ return; } // 若棧滿,則擴(kuò)充棧容量 if (this.top==element.length-1){ Object[] temp=this.element; element=new Object[temp.length*2]; for (int i=0;i<temp.length;i++){ element[i]=temp[i]; } } //入棧 this.element[++top]=x; } // 出棧,返回棧頂元素 @Override public T pop() { if (top!=-1){ return (T) this.element[this.top--]; } return null; } // 返回棧頂元素,但不出棧 @Override public T peek() { if (top!=-1){ return (T) this.element[this.top]; } return null; } // 返回順序棧中所有元素的描述字符串,形式為"(,)",覆蓋Object類的toString()方法 public String toString(){// 自棧頂輸出到棧底 String str=""; if (top>=0){ str="("; for (int i=top;i>=0;i--){ str+=element[i]+","; } str=str.substring(0,str.length()-1); str+=")"; }else {//空棧 str="()"; } return str; } }
3.定義結(jié)點(diǎn)類Node<T>,包括數(shù)據(jù)域和地址域兩個(gè)成員變量,構(gòu)造方法實(shí)例化結(jié)點(diǎn),重寫toString()方法獲取結(jié)點(diǎn)的字符串描述。
package ch05; public class Node <T>{ public T data; public Node<T> next; public Node(T data, Node<T> next) { this.data = data; this.next = next; } public Node(){ this(null,null); } }
4. 定義鏈?zhǔn)綏n怢inkedStack<T>:
package ch05; public class LinkedStack<T> implements SStack<T>{ private Node<T> top; public LinkedStack() { top=new Node<>(); } @Override public boolean isEmpty() { return top.next==null ? true:false; } @Override public void push(T x) { if (x==null){ return; } //生成新結(jié)點(diǎn) Node<T> q=new Node<>(x,null); q.next=top.next; top.next=q; } @Override public T pop() { T elem=null; if (top.next!=null){ elem=top.next.data; top.next=top.next.next; } return elem; } @Override public T peek() { T elem=null; if (top.next!=null){ elem=top.next.data; } return elem; } // 返回順序棧中所有元素的描述字符串,形式為"(,)",覆蓋Object類的toString()方法 public String toString(){ String str=""; Node<T> p=top.next; if (p!=null){ str="("; while (p!=null){ str+=p.data+","; p=p.next; } str=str.substring(0,str.length()-1); str+=")"; }else { str="()"; } return str; } }
5.括號(hào)匹配
package ch07; import java.util.Scanner; public class Bracket { // 括號(hào)匹配 public static String isMatched(String infix) { SeqStack<Character> stack = new SeqStack<Character>(infix.length()); for (int i = 0; i < infix.length(); i++) { char ch = infix.charAt(i); switch (ch) { case '(': stack.push(ch); break; case ')': if (stack.isEmpty() || !stack.pop().equals('(')) { return "expect ("; } } } return stack.isEmpty() ? "" : "expect )"; } // 測(cè)試?yán)ㄌ?hào)匹配算法 public static void main(String[] args) { // 括號(hào)匹配 Scanner r = new Scanner(System.in); System.out.print("輸入括號(hào)表達(dá)式:"); String infix = r.nextLine(); System.out.println(isMatched(infix)); } }
6.表達(dá)式求值(后綴表達(dá)式):
package ch05; import java.util.Scanner; public class ExpressionPoland { // 括號(hào)匹配 public static String isMatched(String infix) { SeqStack<Character> stack = new SeqStack<Character>(infix.length()); for (int i = 0; i < infix.length(); i++) { char ch = infix.charAt(i); switch (ch) { case '(': stack.push(ch); break; case ')': if (stack.isEmpty() || !stack.pop().equals('(')) { return "expect ("; } } } return stack.isEmpty() ? "" : "expect )"; } // 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 public static StringBuffer toPostfix(String infix){ SeqStack<Character> stack=new SeqStack<Character>(infix.length()); StringBuffer postfix=new StringBuffer(infix.length()*2); int i=0; System.out.println("\n求后綴表達(dá)式過程:"); System.out.println("字符"+"\tstack\t\tpostfix"); while(i<infix.length()){ // 對(duì)表達(dá)式中的每個(gè)字符進(jìn)行處理 char ch=infix.charAt(i); // 第i個(gè)字符 System.out.print(ch+"\t"); // 輸出第i個(gè)字符 switch(ch){ // 判斷字符類別 // +、-運(yùn)算符 case '+': case '-': // 當(dāng)棧不空且棧頂運(yùn)算符優(yōu)先級(jí)高時(shí),包括+、-、*、/ while(!stack.isEmpty() && !stack.peek().equals('(')){ // 棧中的'('優(yōu)先級(jí)最低 postfix.append(stack.pop()+" "); // 將出棧的運(yùn)算符追加到后綴表達(dá)式中(空格間隔) } stack.push(ch); // 第i個(gè)字符入棧 i++; break; case '*': case '/': // 當(dāng)棧不空且棧頂運(yùn)算符優(yōu)先級(jí)高時(shí),包括*、/ while(!stack.isEmpty() && (stack.peek().equals('*') || stack.peek().equals('/'))){ postfix.append(stack.pop()+" "); // 將出棧的運(yùn)算符追加到后綴表達(dá)式中(空格間隔) } stack.push(ch); // 第i個(gè)字符入棧 i++; break; case '(': stack.push(ch); // '('入棧 i++; break; case ')': Character out=stack.pop(); while(out!=null && !out.equals('(')){ // 若干運(yùn)算符出棧,直到'('出棧 postfix.append(out+" "); // 將出棧的運(yùn)算符追加到后綴表達(dá)式中(空格間隔) out=stack.pop(); } i++; break; default: while(i<infix.length() && ch>='0' && ch<='9'){ // 獲取運(yùn)算的整數(shù) postfix.append(ch); // 將數(shù)字追加到后綴表達(dá)式中 i++; if(i<infix.length()){ ch=infix.charAt(i); // 下一位字符 } } postfix.append(" "); // 運(yùn)算數(shù)以空格間隔 } System.out.printf("%-18s",stack.toString()); // 輸出每個(gè)運(yùn)算符或運(yùn)算數(shù)處理后棧中的內(nèi)容 System.out.println(postfix); // 輸出每個(gè)運(yùn)算符或運(yùn)算數(shù)處理后的后綴表達(dá)式 } while(!stack.isEmpty()){ // 棧中運(yùn)算符全部出棧 postfix.append(stack.pop()); } return postfix; } // 計(jì)算后綴表達(dá)式的值 public static int toValue(StringBuffer postfix){ LinkedStack<Integer> stack=new LinkedStack<Integer>(); int value=0; System.out.println("\n計(jì)算過程:"); for(int i=0;i<postfix.length();i++){ char ch=postfix.charAt(i); if(ch>='0' && ch<='9'){ String s=""; while(ch!=' '){// 求運(yùn)算數(shù) s+=ch; i++; ch=postfix.charAt(i); } stack.push(Integer.parseInt(s)); // 將運(yùn)算數(shù)入棧 }else{ if(ch!=' '){ int y=stack.pop(); // 第二個(gè)運(yùn)算數(shù) int x=stack.pop(); // 第一個(gè)運(yùn)算數(shù) switch(ch){ case '+': value=x+y; break; case '-': value=x-y; break; case '*': value=x*y; break; case '/': value=x/y; break; }//switch // 輸出計(jì)算表達(dá)式 if(y>=0){ System.out.println(x+(ch+"")+y+"="+value); }else{ System.out.println(x+(ch+"")+"("+y+")"+"="+value); } // 計(jì)算結(jié)果入棧 stack.push(value); } } } return stack.pop(); // 返回棧中計(jì)算的最終結(jié)果 } // 測(cè)試表達(dá)式求值算法 public static void main(String[] args) { Scanner r=new Scanner(System.in); // 表達(dá)式求值 System.out.print("輸入表達(dá)式:"); String infix = r.nextLine(); String match=isMatched(infix); if(match.equals("")){// 括號(hào)匹配 StringBuffer postfix=toPostfix(infix); System.out.println("\n后綴表達(dá)式:"+postfix); System.out.println("\n計(jì)算結(jié)果:"+toValue(postfix)); }else{// 括號(hào)不匹配 System.out.println("表達(dá)式錯(cuò)誤:"+match); } } }
運(yùn)行結(jié)果如下:
到此,相信大家對(duì)“java數(shù)據(jù)結(jié)構(gòu)中棧怎么應(yīng)用”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。