数据结构和算法-栈

  • 开发
  • 52

数据结构和算法-栈

1. 栈的介绍

栈的介绍：

  1. 栈的英文为(stack)
  2. 栈是一个先入后出的有序列表
  3. 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。
  4. 根据栈的定义可知，最先放入栈中元素的栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
  5. 出栈(POP)和入栈(PUSH)的概念

==注意：==栈和上次介绍的队列是不同的

  1. 栈的栈底是固定的，先入后出。一个指针
  2. 而队列的首尾都是不固定的，先入先出。两个指针

在这里插入图片描述

图1 出栈和入栈示意图

2. 栈的应用场景

  1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
  2. 处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
  3. 表达式的转换[中缀表达式转后缀表达式]与求值（实际解决）。
  4. 二叉树的遍历
  5. 图形的深度优先（depth-first）搜索法。

3. 栈的快速入门

3.1 用数组模拟栈

用数组模拟栈的使用，由于栈是一种有序列表，可以使用数组的结构来存储栈的数据内容。下面用数组模拟栈的出栈、入栈等操作

  实现栈的思路分析

  1. 使用栈的思路分析
  2. 定义一个top来表示栈顶，初始化为-1
  3. 入栈的操作，当有数据加入到栈时，top++;stack[top]=data;
  4. 出栈的操作，int value = stack[top];top–;return value;

韩老师代码如下

//定义一个ArrayStack 表示栈
class ArrayStack {
   
    private int maxSize;    //栈的大小
    private int[] stack;    //数组 数组模拟栈 数据就放在该数组
    private int top = -1;   //top表示栈顶 初始化为-1 arr[top] 是栈的最后一个有效数据

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

    //栈满
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    //栈空
    public boolean isEmpty() {
   
        return top == -1;
    }

    //入栈-push
    public void push(int value) {
   
        //先判断是否满
        if (isFull()) {
   
            System.out.println("栈满");
            return;
        }
        stack[++top] = value;
    }

    //出栈-pop 将栈顶的数据返回
    public int pop() {
   
        //先判断栈是否空
        if (isEmpty()) {
   
            //抛出异常处理
            throw new RuntimeException("栈为空");
        }
        return stack[top--];
    }

    //显示栈的情况 遍历时 需要从栈顶开始显示
    public void list() {
   
        //先判断栈是否空
        if (isEmpty()) {
   
            //抛出异常处理
            throw new RuntimeException("栈为空");
        }
        for (int i = top; i >= 0; i--) {
   
            System.out.println(stack[i]);
        }
    }
}

3.2 课堂作业-用链表模拟栈

自己写的代码如下

//无头结点的单链表模拟栈
class ListStack {
   
    private final int maxSize;    //栈的最大容量
    private Node list = new Node(0);    //栈的第一个存储空间
    private int top = -1;   //指向栈顶

    public ListStack(int maxSize) {
   //maxSize 最大容量
        this.maxSize = maxSize;
        Node temp = list;
        for (int i = 1; i < maxSize; i++) {
   
            temp.setNext(new Node(i));  //将上一个节点连接新节点
            temp = temp.getNext();  //将temp指向新节点(链表的最后一个节点)
        }
    }

    //判断栈是否满了
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    //判断栈是否为空
    public boolean isEmpty() {
   
        return top == -1;
    }

    //入栈
    public void push(int value) {
   
        if (isFull()) {
      //如果满了
            System.out.println("满了兄弟");
            return;//退出函数
        }

        Node temp = list;
        ++top;
        while (temp.getNo() != top) {
   //当找到时退出循环
            temp = temp.getNext();
        }
        //当退出循环时 temp就是目标
        temp.setValue(value);
    }

    //出栈-pop 将栈顶的数据返回
    public int pop(){
   
        if (isEmpty()){
    //说明为空
            throw new RuntimeException("空了");
        }
        Node temp = list;
        while (temp.getNo() != top) {
   //当找到时退出循环
            temp = temp.getNext();
        }
        top--;
        return temp.getValue();
    }

    //显示栈的情况 遍历时 需要从栈顶开始显示
    public void show(){
   
        if (isEmpty()){
    //说明为空
            System.out.println("空的");
        }
        for (int i = 0; i < top + 1; i++) {
   
            Node temp = list;
            for (int j = 0; j < top - i; j++) {
   
                temp = temp.getNext();
            }
            System.out.println(temp.getValue());
        }
    }
}


//单链表的节点
class Node {
   

    private int no; //编号
    private int value;  //保存的值
    private Node next;  //next域

    public Node(int no) {
   
        this.no = no;
    }

    public int getNo() {
   
        return no;
    }

    public void setNo(int no) {
   
        this.no = no;
    }

    public int getValue() {
   
        return value;
    }

    public void setValue(int value) {
   
        this.value = value;
    }

    public Node getNext() {
   
        return next;
    }

    public void setNext(Node next) {
   
        this.next = next;
    }

    @Override
    public String toString() {
   
        return "Node{" +
                "no=" + no +
                ", value=" + value +
                ", next=" + ((next == null) ? "null" : next.hashCode()) +
                '}';
    }
}

看到弹幕说有直接头插法，试了一下，发现确实更好

//有头结点的单链表模拟栈
class ListStack2 {
   
    private final int maxSize;    //栈的最大容量
    private Node2 head = new Node2(); //头节点
    private int top = -1;   //指向栈顶

    public ListStack2(int maxSize) {
   
        this.maxSize = maxSize;
    }

    //判断栈是否满了
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    //判断栈是否为空
    public boolean isEmpty() {
   
        return top == -1;
    }

    //入栈
    public void push(int value) {
   
        if (isFull()) {
      //如果满了
            System.out.println("满了兄弟");
            return;//退出函数
        }
        Node2 temp = new Node2(value);//创建新节点
        //将此节点插入到头节点和旧的第一个节点中 成为新的第一个节点(栈顶)
        temp.setNext(head.getNext());
        head.setNext(temp);
        top++;//计数加一
    }

    //出栈-pop 将栈顶的数据返回
    public int pop() {
   
        if (isEmpty()) {
    //说明为空
            throw new RuntimeException("空了");
        }
        top--;  //计数减一
        int value = head.getNext().getValue();  //得到返回值
        //将第一个节点从链表中删除
        head.setNext(head.getNext().getNext()); //将头节点的next指向第二个节点 作为新的第一个节点
        return value;
    }

    //显示栈的情况 遍历时 需要从栈顶开始显示
    public void show() {
   
        if (isEmpty()) {
    //说明为空
            System.out.println("空的");
            return;
        }
        Node2 temp = head.getNext();
        while (temp != null) {
   //遍历完所有节点
            System.out.println(temp.getValue());
            temp = temp.getNext();//节点后移
        }
    }
}

//单链表的节点
class Node2 {
   

    private int value;  //保存的值
    private Node2 next;  //next域

    public Node2(int value) {
   
        this.value = value;
    }

    public Node2() {
   
    }

    public int getValue() {
   
        return value;
    }

    public void setValue(int value) {
   
        this.value = value;
    }

    public Node2 getNext() {
   
        return next;
    }

    public void setNext(Node2 next) {
   
        this.next = next;
    }
}

4. 栈实现综合计算器

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

图2 思路图

使用栈完成表达式的计算思路

  1. 通过一个index值（索引），来遍历我们的表达式
  2. 如果我们发现是一个数字,就直接入数栈
  3. 如果发现扫描到是一个符号,就分如下情况
    • 如果发现当前的符号栈为空，就直接入栈
    • 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈.
  4. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相的数和符号，并运行.
  5. 最后在数栈只有一个数字，就是表达式的结果

自己写的多位数代码如下

package com.atguigu.stack;

/**
 * @author 小小低头哥
 * @version 1.0
 */

public class Calculator {
   
    public static void main(String[] args) {
   
        //根据前面思路 完成表达式的运算
//        String expression = "2+2*3-2*1-1+2-3-2-3";
//        String expression = "2+3+1-4-3-2+2*20*450/50+6+4-3-4-2*2";
        String expression = "30*2-6*9+1";
        //创建两个栈 数栈、符号栈
        ArrayStack2 numStack = new ArrayStack2(30);
        ArrayStack2 operStack = new ArrayStack2(50);
        //定义需要的相关变量
        int index = 0;  //用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' ';  //将每次扫描得到char保存到ch
        int count = 0;  //计数器 记录是几位数 放在符号栈的符号中
        //开始while循环的扫描expression
        while (true) {
   
            //依次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //判断ch是什么 然后做出相应的处理
            if (operStack.isOper(ch)) {
      //如果是运算符
                //判断当前的符号栈是否为空
                if (!operStack.isEmpty()) {
    //不为空则一个个判断
                    operStack.push(count);  //先放进去
                    //if (operStack.priority(ch) < operStack.priority(operStack.peek()))
                    while (operStack.priority(ch) < operStack.priority(operStack.peek())) {
   
                        //下面num1、oper、num2弹出的顺序不能变
                        num1 = numStack.popN(operStack.pop());  //得到符号位前面的整数 并弹出符号栈中对应的数字标志
                        oper = operStack.pop(); //出栈
                        num2 = numStack.popN(operStack.pop());
                        res = numStack.cal(num1, num2, oper);
                        //把运算的结果放入数栈
                        numStack.push(res);
                        count = 1;
                        if (!operStack.isEmpty()) {
      //说明前面没有运算符了 自然也不需要更新了
                            operStack.pop();   //把前一个运算符后面的数字位数去掉 因为此时已经变成res了 由于res是一个整体 所以相当于count=1
                            operStack.push(count);   //更新前一个运算符后面的数字位数
                        }else {
   
                            break;
                        }
                    }
                }
                //为空或者判断完毕后 把当前符号入符号栈
                operStack.push(count);  //把符号前面的数是几位数记录下来 并放在ch的前面
                operStack.push(ch);
                count = 0;  //重新置零
            } else {
   //如果是数 则直接入数栈
                count++;    //数字数加一
                numStack.push(ch - 48); //转换为数字
            }
            //让index + 1 ，并判断是否扫描到expression最后
            index++;
            if (index >= expression.length()) {
      //扫描结束
                operStack.push(count);  //扫描结束最后一个肯定是数字 需要把此数字的位数压入到符号栈
                break;
            }
        }
        while (true) {
   
            //下面num1、oper、num2弹出的顺序不能变
            num1 = numStack.popN(operStack.pop());  //得到符号位前面的整数 并弹出符号栈中对应的数字标志
            oper = operStack.pop(); //出栈
            num2 = numStack.popN(operStack.pop());
            if (!operStack.isEmpty() && oper == '-' && operStack.peek() == '-') {
      //如果此时的操作符和上一个操作符都是负号
                //那么说明此时不是相减 而是相加
                res = numStack.cal(num1, num2, '+');
            } else if (!operStack.isEmpty() && oper == '+' && operStack.peek() == '-') {
      //则应是num2-num1
                res = numStack.cal(num1, num2, '-');
            } else {
   
                res = numStack.cal(num1, num2, oper);
            }
            numStack.push(res); //入栈
            //如果符号栈为空 则计算到最后的结果，数栈中只有一个数字
            if (operStack.isEmpty()) {
   
                break;
            }
            operStack.pop();   //把前一个运算符后面的数字位数去掉 因为此时已经变成res了
            operStack.push(1);   //更新前一个运算符后面的数字位数
        }
        System.out.println(expression + "表达式的结果是:" + numStack.pop());
    }
}

//先定义一个栈 直接使用前面创建好
//定义一个ArrayStack表示栈

class ArrayStack2 {
   
    private int maxSize;    //栈的大小
    private int[] stack;    //数组 数组模拟栈 数据就放在该数组
    private int top = -1;   //top表示栈顶 初始化为-1 arr[top] 是栈的最后一个有效数据

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

    //栈满
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    //栈空
    public boolean isEmpty() {
   
        return top == -1;
    }

    //入栈-push
    public void push(int value) {
   
        //先判断是否满
        if (isFull()) {
   
            System.out.println("栈满");
            return;
        }
        stack[++top] = value;
    }

    //出栈 连续出栈几个并组成数字 为数栈准备
    public int popN(int n) {
   
        int res = 0;
        for (int i = 0; i < n; i++) {
   
            if (i == 0) {
   
                res = res + pop();
            } else {
   
                res = res + pop() * (int) Math.pow(10, i); //从个位、十位等依次入手
            }
        }
        return res;
    }

    //出栈-pop 将栈顶的数据返回
    public int pop() {
   
        //先判断栈是否空
        if (isEmpty()) {
   
            //抛出异常处理
            throw new RuntimeException("栈为空");
        }
        return stack[top--];
    }

    //显示栈的情况 遍历时 需要从栈顶开始显示
    public void list() {
   
        //先判断栈是否空
        if (isEmpty()) {
   
            //抛出异常处理
            throw new RuntimeException("栈为空");
        }
        for (int i = top; i >= 0; i--) {
   
            System.out.println(stack[i]);
        }
    }

    //返回运算符的优先级 优先级是程序员确定的 优先级使用数组表示
    //数字越大 则优先级越高
    public int priority(int oper) {
   
        if (oper == '*' || oper == '/') {
   
            return 1;
        } else if (oper == '+' || oper == '-') {
   
            return 0;
        } else {
   
            return -1;  //假定目前表达式只有加减乘除
        }
    }

    //增加一个方法 可以返回当前栈顶的值 但是不是真正的pop
    public int peek() {
   
        return stack[top - 1];
    }

    //判断是不是一个运算符
    public boolean isOper(char val) {
   
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //计算方法
    public int cal(int num1, int num2, int oper) {
   
        int res = 0;    //res用于存放计算的结果
        switch (oper) {
   
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;  //注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }

}

韩老师写的多位数代码如下

package com.atguigu.stack;

/**
 * @author 小小低头哥
 * @version 1.0
 */
public class Calculator2 {
   
    public static void main(String[] args) {
   
        //根据前面思路 完成表达式的运算
        String expression = "30*2-6*9+1";
        //创建两个栈 数栈、符号栈
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        //定义需要的相关变量
        int index = 0;  //用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' ';  //将每次扫描得到char保存到ch
        String keepNum = "";   //用于拼接多位数
        //开始while循环的扫描expression
        while (true) {
   
            //依次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //判断ch是什么 然后做出相应的处理
            if (operStack.isOper(ch)) {
      //如果是运算符
                //判断当前的符号栈是否为空
                if (!operStack.isEmpty()) {
    //不为空则一个个判断
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
   
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop(); //出栈
                        res = numStack.cal(num1, num2, oper);
                        //把运算的结果放入数栈
                        numStack.push(res);
                        operStack.push(ch);
                    } else {
   
                        operStack.push(ch);
                    }
                } else {
   
                    operStack.push(ch);
                }
            } else {
   //如果是数 则直接入数栈
                //分析思路
                //1. 当处理多位数时 不能发现一个数就立即入栈 因为可能是多位数
                //2. 在处理数，需要翔expression的表达式的index后再看一位 如果是数就进行扫描 如果是符号才入栈
                //3. 因此需要定义一个变量 用于拼接

                //处理多位数
                keepNum += ch;
                //如果ch已经是expression的最后一位 就直接入栈
                if (index == expression.length() - 1) {
   
                    numStack.push(Integer.parseInt(keepNum));
                } else {
   
                    //判断下一个字符是不是数字 如果是数字 就继续扫描 如果是运算符 则入栈
                    //注意看后一位 不是index++
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
   
                        //如果后一位是运算符 则入栈
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";   //清空！！
                    }
                }
            }
            //让index + 1 ，并判断是否扫描到expression最后
            index++;
            if (index >= expression.length()) {
      //扫描结束
                break;
            }
        }
        while (true) {
   
            //如果符号栈为空 则计算到最后的结果，数栈中只有一个数字
            if (operStack.isEmpty()) {
   
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop(); //出栈
            res = numStack.cal(num1, num2, oper);
            numStack.push(res); //入栈
        }
        System.out.println(expression + "表达式的结果是:" + numStack.pop());
    }
}

//先定义一个栈 直接使用前面创建好
//定义一个ArrayStack表示栈

class ArrayStack2 {
   
    private int maxSize;    //栈的大小
    private int[] stack;    //数组 数组模拟栈 数据就放在该数组
    private int top = -1;   //top表示栈顶 初始化为-1 arr[top] 是栈的最后一个有效数据

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

    //栈满
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    //栈空
    public boolean isEmpty() {
   
        return top == -1;
    }

    //入栈-push
    public void push(int value) {
   
        //先判断是否满
        if (isFull()) {
   
            System.out.println("栈满");
            return;
        }
        stack[++top] = value;
    }

    //出栈-pop 将栈顶的数据返回
    public int pop() {
   
        //先判断栈是否空
        if (isEmpty()) {
   
            //抛出异常处理
            throw new RuntimeException("栈为空");
        }
        return stack[top--];
    }

    //显示栈的情况 遍历时 需要从栈顶开始显示
    public void list() {
   
        //先判断栈是否空
        if (isEmpty()) {
   
            //抛出异常处理
            throw new RuntimeException("栈为空");
        }
        for (int i = top; i >= 0; i--) {
   
            System.out.println(stack[i]);
        }
    }

    //返回运算符的优先级 优先级是程序员确定的 优先级使用数组表示
    //数字越大 则优先级越高
    public int priority(int oper) {
   
        if (oper == '*' || oper == '/') {
   
            return 1;
        } else if (oper == '+' || oper == '-') {
   
            return 0;
        } else {
   
            return -1;  //假定目前表达式只有加减乘除
        }
    }

    //增加一个方法 可以返回当前栈顶的值 但是不是真正的pop
    public int peek() {
   
        return stack[top];
    }

    //判断是不是一个运算符
    public boolean isOper(char val) {
   
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //计算方法
    public int cal(int num1, int num2, int oper) {
   
        int res = 0;    //res用于存放计算的结果
        switch (oper) {
   
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;  //注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }

}

4.1 课堂作业-加入小括号

在前面的基础上加上了判断小括号的功能，觉得还行 不过没加入判断负数的功能

package com.atguigu.stack;

/**
 * @author 小小低头哥
 * @version 1.0
 */

public class Calculator {
   
    public static void main(String[] args) {
   
        //根据前面思路 完成表达式的运算
//        String expression = "2+2*3-2*1-1+2-3-2-3";
//        String expression = "2+3+1-4-3-2+2*20*450/50+6+4-3-4-2*2";
        String expression = "30*2-(6*9)-(1+5*4)+(4*6)";
        //创建两个栈 数栈、符号栈
        ArrayStack2 numStack = new ArrayStack2(30);
        ArrayStack2 operStack = new ArrayStack2(50);
        //定义需要的相关变量
        int index = 0;  //用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' ';  //将每次扫描得到char保存到ch
        int count = 0;  //计数器 记录是几位数 放在符号栈的符号中
        boolean flag = false;   //flag为真时 说明接收到了左、右括号 且还没有接收到符号位
        //开始while循环的扫描expression
        while (true) {
   
            //依次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //判断ch是什么 然后做出相应的处理
            if (operStack.isOper(ch)) {
      //如果是运算符
                //判断当前的符号栈是否为空
                if (!operStack.isEmpty()) {
    //不为空则一个个判断
                    if (!flag) {
   //如果上一个是 ( 则不用放进去
                        operStack.push(count);  //先放进去
                    }
                    flag = false;
                    //if (operStack.priority(ch) < operStack.priority(operStack.peek()))
                    while (operStack.priority(ch) < operStack.priority(operStack.peek(1))) {
   //0的优先权最小 不会进入循环 正要如此
                        //下面num1、oper、num2弹出的顺序不能变
                        num1 = numStack.popN(operStack.pop());  //得到符号位前面的整数 并弹出符号栈中对应的数字标志
                        oper = operStack.pop(); //出栈
                        num2 = numStack.popN(operStack.pop());
                        res = numStack.cal(num1, num2, oper);
                        //把运算的结果放入数栈
                        numStack.push(res);
                        count = 1;
                        //前面还有运算符了 需要更新 或者计算完括号中的数
                        if (!operStack.isEmpty() && operStack.peek(0) != 0) {
   
                            operStack.pop();   //把前一个运算符后面的数字位数去掉 因为此时已经变成res了 由于res是一个整体 所以相当于count=1
                            operStack.push(count);   //更新前一个运算符后面的数字位数
                        } else {
   
                            break;
                        }
                    }
                }
                //为空或者判断完毕后 把当前符号入符号栈
                operStack.push(count);  //把符号前面的数是几位数记录下来 并放在ch的前面
                operStack.push(ch);
                count = 0;  //重新置零
            } else if (ch == '(') {
      //按数学规矩 (的前面一个肯定是运算符
                flag = true;
                operStack.push(0);  //把零送进去当作是起点
            } else if (ch == ')') {
   
                flag = true;
                operStack.push(count);  //)前必然是数字 所以这里先送进去一个计数器
                while (true) {
   //说明还没计算完括号内的运算
                    //下面num1、oper、num2弹出的顺序不能变
                    num1 = numStack.popN(operStack.pop());  //得到符号位前面的整数 并弹出符号栈中对应的数字标志
                    oper = operStack.pop(); //出栈
                    num2 = numStack.popN(operStack.pop());
                    if (operStack.peek(0)!= 0 && oper == '-' && operStack.peek(1) == '-') {
      //如果此时的操作符和上一个操作符都是负号
                        //那么说明此时不是相减 而是相加
                        res = numStack.cal(num1, num2, '+');
                    } else if (operStack.peek(0)!= 0 && oper == '+' && operStack.peek(1) == '-') {
      //则应是num2-num1
                        res = numStack.cal(num1, num2, '-');
                    } else {
   
                        res = numStack.cal(num1, num2, oper);
                    }
                    numStack.push(res); //入栈
                    //如果括号中的数计算完毕
                    if (operStack.peek(0) == 0) {
   
                        operStack.pop();    //把标志位给弹出来
                        operStack.push(1);  //因为()的结果是一个整数 所以把1送进去作为()整体的数的个数
                        break;
                    }
                    operStack.pop();   //把前一个运算符后面的数字位数去掉 因为此时已经变成res了
                    operStack.push(1);   //更新前一个运算符后面的数字位数
                }
            } else {
   //如果是数 则直接入数栈
                count++;    //数字数加一
                numStack.push(ch - 48); //转换为数字
            }
            //让index + 1 ，并判断是否扫描到expression最后
            index++;
            if (index >= expression.length() ) {
      //扫描结束
                //扫描结束最后一个肯定是数字 需要把此数字的位数压入到符号栈
                if( ch != ')'){
    //但是如果最后是以)结束 则由于括号计算中已经把1插进去了 不需要了
                    operStack.push(count);
                }
                break;
            }
        }
        while (true) {
   
            //下面num1、oper、num2弹出的顺序不能变
            num1 = numStack.popN(operStack.pop());  //得到符号位前面的整数 并弹出符号栈中对应的数字标志
            oper = operStack.pop(); //出栈
            num2 = numStack.popN(operStack.pop());
            if (!operStack.isEmpty() && oper == '-' && operStack.peek(1) == '-') {
      //如果此时的操作符和上一个操作符都是负号
                //那么说明此时不是相减 而是相加
                res = numStack.cal(num1, num2, '+');
            } else if (!operStack.isEmpty() && oper == '+' && operStack.peek(1) == '-') {
      //则应是num2-num1
                res = numStack.cal(num1, num2, '-');
            } else {
   
                res = numStack.cal(num1, num2, oper);
            }
            numStack.push(res); //入栈
            //如果符号栈为空 则计算到最后的结果，数栈中只有一个数字
            if (operStack.isEmpty()) {
   
                break;
            }
            operStack.pop();   //把前一个运算符后面的数字位数去掉 因为此时已经变成res了
            operStack.push(1);   //更新前一个运算符后面的数字位数
        }
        System.out.println(expression + "表达式的结果是:" + numStack.pop());
    }
}

//先定义一个栈 直接使用前面创建好
//定义一个ArrayStack表示栈

class ArrayStack2 {
   
    private int maxSize;    //栈的大小
    private int[] stack;    //数组 数组模拟栈 数据就放在该数组
    private int top = -1;   //top表示栈顶 初始化为-1 arr[top] 是栈的最后一个有效数据

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

    //栈满
    public boolean isFull() {
   
        return top == maxSize - 1;
    }

    //栈空
    public boolean isEmpty() {
   
        return top == -1;
    }

    //入栈-push
    public void push(int value) {
   
        //先判断是否满
        if (isFull()) {
   
            System.out.println("栈满");
            return;
        }
        stack[++top] = value;
    }

    //出栈 连续出栈几个并组成数字 为数栈准备
    public int popN(int n) {
   
        int res = 0;
        for (int i = 0; i < n; i++) {
   
            if (i == 0) {
   
                res = res + pop();
            } else {
   
                res = res + pop() * (int) Math.pow(10, i); //从个位、十位等依次入手
            }
        }
        return res;
    }

    //出栈-pop 将栈顶的数据返回
    public int pop() {
   
        //先判断栈是否空
        if (isEmpty()) {
   
            //抛出异常处理
            throw new RuntimeException("栈为空");
        }
        return stack[top--];
    }

    //显示栈的情况 遍历时 需要从栈顶开始显示
    public void list() {
   
        //先判断栈是否空
        if (isEmpty()) {
   
            //抛出异常处理
            throw new RuntimeException("栈为空");
        }
        for (int i = top; i >= 0; i--) {
   
            System.out.println(stack[i]);
        }
    }

    //返回运算符的优先级 优先级是程序员确定的 优先级使用数组表示
    //数字越大 则优先级越高
    public int priority(int oper) {
   
        if (oper == '*' || oper == '/') {
   
            return 1;
        } else if (oper == '+' || oper == '-') {
   
            return 0;
        } else {
   
            return -1;  //假定目前表达式只有加减乘除
        }
    }

    //增加一个方法 可以返回当前栈顶的第n个值 但是不是真正的pop
    public int peek(int n) {
   
        return stack[top - n];
    }

    //判断是不是一个运算符
    public boolean isOper(char val) {
   
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //计算方法
    public int cal(int num1, int num2, int oper) {
   
        int res = 0;    //res用于存放计算的结果
        switch (oper) {
   
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;  //注意顺序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }

}
阅读全部

相关推荐

  3. 数据结构与算法——栈和队列

    2023-12-08 10:08:03       32 阅读

  4. 【算法集训】基础数据结构：六、栈和队列

    2023-12-08 10:08:03       54 阅读

  10. 数据结构---栈和队列

    2023-12-08 10:08:03       60 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-08 10:08:03       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-08 10:08:03       100 阅读

  9. 在Django里面运行非项目文件

    2023-12-08 10:08:03       82 阅读

  19. Python语言-面向对象

    2023-12-08 10:08:03       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2023-12-08 10:08:03       85 阅读

热门阅读

  1. 移除、混淆静态库中多余的符号(待续)

    2023-12-08 10:08:03       60 阅读

  2. 九、C#笔记

    2023-12-08 10:08:03       46 阅读

  6. Docker创建RocketMQ和RocketMQ控制台

    2023-12-08 10:08:03       62 阅读

  9. CEPH搭建

    2023-12-08 10:08:03       57 阅读

  11. 【Docker】安装Jenkins 亲测 傻瓜式安装

    2023-12-08 10:08:03       61 阅读

  13. 苍穹外卖项目(黑马)学习笔记

    2023-12-08 10:08:03       448 阅读

  14. 面试经典150题(3-4)

    2023-12-08 10:08:03       66 阅读

  17. Linux环境变量export命令笔记231207

    2023-12-08 10:08:03       70 阅读

  18. HttpURLConnection OOM问题记录

    2023-12-08 10:08:03       70 阅读

  20. ChatGPT（INSCODE AI 创作助手自动创作的）

    2023-12-08 10:08:03       102 阅读

  23. 深入探索HTTPS加密技术与新兴安全趋势：保卫隐私的未来之路

    2023-12-08 10:08:03       54 阅读

  24. GEE——利用Landsat系列数据集进行1984-2023EVI指数趋势分析

    2023-12-08 10:08:03       60 阅读

  26. stm32中滴答定时器与普通定时器的区别

    2023-12-08 10:08:03       63 阅读

  27. 基于微信小程序的智慧校园导航系统研究

    2023-12-08 10:08:03       64 阅读

  28. AWS EC2使用 instance profile 访问S3

    2023-12-08 10:08:03       62 阅读

  30. C语言指针和内存管理

    2023-12-08 10:08:03       56 阅读