package ch05;
 
public interface SStack <T>{
    boolean isEmpty();  // 判斷棧是否為空
    void push(T x);		// 元素x入棧
    T pop();			// 出棧，返回棧頂元素
    T peek();			// 返回棧頂元素，但不出棧
}

?2.?定義順序棧類SeqStack<T>，包括數(shù)據(jù)元素的對象數(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è)空棧，存儲容量大小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)綏ｎ怢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.括號匹配

package ch07;
 
import java.util.Scanner;
 
public class Bracket {
	// 括號匹配
	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 )";
	}
 
	// 測試?yán)ㄌ柶ヅ渌惴?
	public static void main(String[] args) {
		// 括號匹配
		Scanner r = new Scanner(System.in);
		System.out.print("輸入括號表達(dá)式：");
		String infix = r.nextLine();
		System.out.println(isMatched(infix));
	}
}

6.表達(dá)式求值（后綴表達(dá)式）：

package ch05;
 
import java.util.Scanner;
 
public class ExpressionPoland {
    // 括號匹配
    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()){ // 對表達(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)先級高時(shí)，包括+、-、*、/
                    while(!stack.isEmpty() && !stack.peek().equals('(')){ // 棧中的'('優(yōu)先級最低
                        postfix.append(stack.pop()+" ");  // 將出棧的運(yùn)算符追加到后綴表達(dá)式中（空格間隔）
                    }
                    stack.push(ch); // 第i個(gè)字符入棧
                    i++;
                    break;
                case '*':
                case '/':
                    // 當(dāng)棧不空且棧頂運(yùn)算符優(yōu)先級高時(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é)果
    }
 
    // 測試表達(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("")){// 括號匹配
            StringBuffer postfix=toPostfix(infix);
            System.out.println("\n后綴表達(dá)式:"+postfix);
            System.out.println("\n計(jì)算結(jié)果："+toValue(postfix));
        }else{// 括號不匹配
            System.out.println("表達(dá)式錯(cuò)誤："+match);
        }
    }
}

運(yùn)行結(jié)果如下：

到此這篇關(guān)于java數(shù)據(jù)結(jié)構(gòu)關(guān)于棧的實(shí)例應(yīng)用的文章就介紹到這了,更多相關(guān)java數(shù)據(jù)結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: