java数据结构关于栈的实例应用

此文章介绍关于顺序栈，链式栈的实例操作，括号匹配，表达式求值（后缀表达式）

1.声明一个栈接口sstack

package ch05;
 
public interface sstack <t>{
    boolean isempty();  // 判断栈是否为空
    void push(t x);		// 元素x入栈
    t pop();			// 出栈，返回栈顶元素
    t peek();			// 返回栈顶元素，但不出栈
}

 2. 定义顺序栈类seqstack<t>，包括数据元素的对象数组和栈顶元素下标两个私有成员变量，构造方法可实例化容量为size大小的空顺序栈，调用类中成员方法实现顺序栈的入栈、出栈、获取栈顶元素等操作，重写tostring()方法获取顺序栈的字符串描述。

package ch05;
 
public class seqstack <t> implements sstack<t>{
    object[] element;
    int top;
    // 构造方法，创建一个空栈，存储容量大小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;
        }
        // 若栈满，则扩充栈容量
        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.定义结点类node<t>，包括数据域和地址域两个成员变量，构造方法实例化结点，重写tostring()方法获取结点的字符串描述。

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.  定义链式栈类linkedstack<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;
        }
        //生成新结点
        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 )";
	}
 
	// 测试括号匹配算法
	public static void main(string[] args) {
		// 括号匹配
		scanner r = new scanner(system.in);
		system.out.print("输入括号表达式：");
		string infix = r.nextline();
		system.out.println(ismatched(infix));
	}
}

6.表达式求值（后缀表达式）：

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 )";
    }
    // 将中缀表达式转换为后缀表达式
    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求后缀表达式过程：");
        system.out.println("字符"+"\tstack\t\tpostfix");
        while(i<infix.length()){ // 对表达式中的每个字符进行处理
            char ch=infix.charat(i); // 第i个字符
            system.out.print(ch+"\t"); // 输出第i个字符
            switch(ch){ // 判断字符类别
                // +、-运算符
                case '+':
                case '-':
                    // 当栈不空且栈顶运算符优先级高时，包括+、-、*、/
                    while(!stack.isempty() && !stack.peek().equals('(')){ // 栈中的'('优先级最低
                        postfix.append(stack.pop()+" ");  // 将出栈的运算符追加到后缀表达式中（空格间隔）
                    }
                    stack.push(ch); // 第i个字符入栈
                    i++;
                    break;
                case '*':
                case '/':
                    // 当栈不空且栈顶运算符优先级高时，包括*、/
                    while(!stack.isempty() && (stack.peek().equals('*') || stack.peek().equals('/'))){
                        postfix.append(stack.pop()+" "); // 将出栈的运算符追加到后缀表达式中（空格间隔）
                    }
                    stack.push(ch); // 第i个字符入栈
                    i++;
                    break;
                case '(':
                    stack.push(ch); // '('入栈
                    i++;
                    break;
                case ')':
                    character out=stack.pop();
                    while(out!=null && !out.equals('(')){ // 若干运算符出栈，直到'('出栈
                        postfix.append(out+" ");  // 将出栈的运算符追加到后缀表达式中（空格间隔）
                        out=stack.pop();
                    }
                    i++;
                    break;
                default:
                    while(i<infix.length() && ch>='0' && ch<='9'){ // 获取运算的整数
                        postfix.append(ch); // 将数字追加到后缀表达式中
                        i++;
                        if(i<infix.length()){
                            ch=infix.charat(i); // 下一位字符
                        }
                    }
                    postfix.append(" ");  // 运算数以空格间隔
            }
            system.out.printf("%-18s",stack.tostring()); // 输出每个运算符或运算数处理后栈中的内容
            system.out.println(postfix);  // 输出每个运算符或运算数处理后的后缀表达式
        }
        while(!stack.isempty()){ // 栈中运算符全部出栈
            postfix.append(stack.pop());
        }
        return postfix;
    }
 
    // 计算后缀表达式的值
    public static int tovalue(stringbuffer postfix){
        linkedstack<integer> stack=new linkedstack<integer>();
        int value=0;
        system.out.println("\n计算过程：");
        for(int i=0;i<postfix.length();i++){
            char ch=postfix.charat(i);
            if(ch>='0' && ch<='9'){
                string s="";
                while(ch!=' '){// 求运算数
                    s+=ch;
                    i++;
                    ch=postfix.charat(i);
                }
                stack.push(integer.parseint(s)); // 将运算数入栈
            }else{
                if(ch!=' '){
                    int y=stack.pop(); // 第二个运算数
                    int x=stack.pop(); // 第一个运算数
                    switch(ch){
                        case '+':
                            value=x+y;
                            break;
                        case '-':
                            value=x-y;
                            break;
                        case '*':
                            value=x*y;
                            break;
                        case '/':
                            value=x/y;
                            break;
                    }//switch
                    // 输出计算表达式
                    if(y>=0){
                        system.out.println(x+(ch+"")+y+"="+value);
                    }else{
                        system.out.println(x+(ch+"")+"("+y+")"+"="+value);
                    }
                    // 计算结果入栈
                    stack.push(value);
                }
            }
        }
        return stack.pop(); // 返回栈中计算的最终结果
    }
 
    // 测试表达式求值算法
    public static void main(string[] args) {
        scanner r=new scanner(system.in);
        // 表达式求值
        system.out.print("输入表达式：");
        string infix = r.nextline();
        string match=ismatched(infix);
        if(match.equals("")){// 括号匹配
            stringbuffer postfix=topostfix(infix);
            system.out.println("\n后缀表达式:"+postfix);
            system.out.println("\n计算结果："+tovalue(postfix));
        }else{// 括号不匹配
            system.out.println("表达式错误："+match);
        }
    }
}

运行结果如下：

到此这篇关于java数据结构关于栈的实例应用的文章就介绍到这了,更多相关java数据结构内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！