数据结构入门教程-栈的应用实例1

在这篇文章中数据结构入门教程-栈,我们了解了栈的基本操作,如入栈(push)和出栈(pop)这两个重要的特性,本篇我们来说说栈的应用实例

需求

• 我们利用栈的特点来实现表达式6+2*6-3的计算

当然我们可以直接利用计算机来得出该表达式的结果,这里只是简单的表达式,说白了,我们来实现计算器的简单计算功能,因为我们的表达式中既有数字也有运算符,因此示意图如下:

微信截图_20200201120143.png

这是我的图,我需要两个栈分别用来保存数字和操作符,下面简单的分析下思路

• 首先我们需要一个指针index也就是图中所示,index主要用来遍历我们的表达式
• 如果遍历的过程是数字,那么直接入数栈即可
• 如果遍历的过程中是操作符,需要分情况判断:
• 1.1 如果当前符号栈为null,就直接入栈
• 1.2 如果当前符号栈中不为null,首先就行比较,如果当前操作符的优先级小于等于符号栈中的操作符,此时需要我们从数栈中pop两个数,同时从符号栈中pop一个操作符,接着进行计算,将得到的结果入数栈,将当前的操作符入符号栈.
• 1.3 如果当前的操作符大于符号栈中的操作符,那么直接入符号栈即可
• 当我们的表达式扫描完成时,顺序从数栈和符号栈中pop对应的数和符号,就行计算.
• 那么最后在数栈中的数字就是我们最终所得的结果.

接着我们来看代码实现

代码实现

• 首先我们创建栈和常用的方法

 //定义栈结构类
class ArrayStack {
private int maxSize; //表示栈的最大容量
private int[] stack; //stack实际用来保存数据的
private int top = -1; //top表示栈顶，初始值为-1，表示此时栈中是没有数据的

public ArrayStack(int maxSize) {
    this.maxSize = maxSize;
    stack = new int[this.maxSize];
}

//栈满的条件
public boolean isFull(){
    return top == maxSize -1;
}
//栈空的条件
public boolean isEmpty(){
    return top == -1;
}
//返回栈顶的值,但不自增
public int peek(){
    return stack[top];
}
//入栈操作
public void push(int element){
    if (isFull()){
        throw new ArrayIndexOutOfBoundsException("栈已经满了~");
    }
    top ++;
    stack[top] = element;
}
//出栈操作
public int pop(){
    if (isEmpty()){
        throw new RuntimeException("栈空~");
    }
    int element = stack[top];
    top --;
    return element;
}
//打印操作
public void print(){
    if (isEmpty()){
        System.out.println("栈空~");
        return;
    }
    for (int i = top; i >= 0 ; i--) {

        System.out.printf("stack[%d]=%d\n",i,stack[i]);
    }

}


//返回操作符的优先级,这里规定乘除的优先级为1,加减为0

/**
 *
 * @param optional 传入的操作符
 * @return
 */
public int priority(int optional){
    if (optional == '*' || optional == '/'){
        return 1;
    }
    if (optional == '+' || optional == '-'){
        return 0;
    }else {
        return -1; //这里的操作符默认W为+ - * /这四种.
    }
}
//判断是否是一个操作符
public boolean isOper(char value){
    return value == '+'|| value == '-' || value == '*'|| value == '/';
}
//计算方法

/**
 *
 * @param num1 数字num1
 * @param num2 数字num2
 * @param oper 操作符包括(+ - * /)
 * @return
 */
public int cal(int num1,int num2,int oper){
    //定义一个临时的变量用来存放计算的结果值,默认为0
    int result = 0;
    switch (oper){

        case '+':
            result = num1 + num2;
            break;
        case '-':
            result = num2 - num1;
            break;
        case '*':
            result = num1 * num2;
            break;
        case '/':
            result = num2 / num1;
            break;
        default:
            break;
    }
    return result;
  }
}

上述是我们栈的定义,其中里面的方法最重要的是计算方法和操作符的判断的方法,代码简单这里不多说了,接着我们看测试代码:

测试代码

public class Calculator {

public static void main(String[] args) {
    //计算表达式
    String expression = "56+2*6-3";
    //分别创建数栈和操作符栈
    ArrayStack numStack = new ArrayStack(10);
    ArrayStack operStack = new ArrayStack(10);
    //定义相关需要的临时变量
    int index = 0; //用于遍历expression的指针
    int num1 = 0; //用于存储从数栈中取出的第一个计算的数字
    int num2 = 0; //用于存储从数栈中取出的第二个计算的数字
    int oper = 0 ; //临时存储从operStack中取出计算的操作符
    int result = 0; //保存我们的计算的结果值
    char ch = ' '; //临时存储从expression中的分割的每一个字符
    String keepNum = ""; //用于拼接多位数的字符

    //循环扫描expression
    while (true){
        //substring(index,index+1) 获取当前index的位置的字符串, charAt(0)转为对应的字符
        ch = expression.substring(index,index+1).charAt(0);
        //判断ch是什么,然后进行相应的处理
        if (operStack.isOper(ch)){ //如果是操作符
            //判断当前符号栈是否为null
            if (!operStack.isEmpty()){ //不为null
                //首先进行比较,如果当前操作符的优先级小于等于operStack中:
                //1. 从numStack取出两个数字
                //1.1. 从operStack中去取出操作符
                //1.2.进行计算,然后将结果入numStack,将当前比较的操作符入operStack即可
                if (operStack.priority(ch) <= operStack.priority(operStack.peek())){
                    num1 = numStack.pop(); //获取第一个计算的数字
                    num2 = numStack.pop(); //获取第二个计算的数字
                    oper = operStack.pop(); //从字符栈中获取操作符
                    //进行计算
                    result = numStack.cal(num1,num2,oper);
                    //将result保存到numStack中
                    numStack.push(result);
                    //将当前的操作符入栈
                    operStack.push(ch);
                }else {
                    //如果当前的操作符的优先级大于operStack中的优先级,直接入栈
                    operStack.push(ch);
                }

            }else {
                //如果当前operStack为null,直接入栈即可
                operStack.push(ch);
            }

        }else {
            //处理多位数字时:
            //1. 不能一扫描到数字就入栈,可能后面还是数字,所以需要我们的index继续向后移动一位,如果时候操作符的话可以入栈了
            keepNum += ch;
            //判断是否已经是expression的最后一个
            if (index == expression.length()-1){
                numStack.push(Integer.parseInt(keepNum));
            }else {
                //判断下一个字符是否是数字,如果是数字的话继续扫描,如果是操作符的话直接入栈
                //index+1 和index+2表示向后看一位不等于index++
                if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                    //入栈
                    numStack.push(Integer.parseInt(keepNum));
                    //注意:将原先的keepNum的值清空
                    keepNum = "";
                }
            }
        }
        //让index +1,判断是否扫描到了expression的最后expression
        index ++;
        if (index >= expression.length()){
            break;
        }
    }
    //当扫描完成时,就顺序从numStack和operStack取出值进行计算操作
    while (true){
        //当我们的operStack中没有了操作符时,就表示我们的numStack中只有一个数字那就是最后的计算结果result
        if (operStack.isEmpty()){
            break;
        }
        num1 = numStack.pop(); //获取第一个计算的数字
        num2 = numStack.pop(); //获取第二个计算的数字
        oper = operStack.pop(); //从字符栈中获取操作符
        //进行计算
        result = numStack.cal(num1,num2,oper);
        //将result保存到numStack中
        numStack.push(result);
    }
    System.out.printf("表达式%s = %d",expression,numStack.pop());
}

来看测试结果如下图:

测试结果.png

从上述结果可以看出时没有问题的,本节所讲的是利用栈实现中缀表达式的计算,关于中缀表达式可以自己百度找找相关资料