栈
我们这里将一个场景带入学习
请输入一个表达式
计算式:[722-5+1-5+3-3] 点击计算 计算出结果
请问: 计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。----> 栈
栈的介绍
栈的英文为(stack)
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的 一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元 素最先删除，最先放入的元素最后删除
图解方式说明出栈(pop)和入栈(push)的概念
入栈与出栈 ： 栈 数据结构的特性 先入后出
栈的应用场景
子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以 回到原来的程序中。
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆 栈中。
表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
二叉树的遍历。
图形的深度优先(depth 一 first)搜索法。
栈 快速入门（数组模拟栈）
实现思路
详细的每一部分的思路 都在代码的注释当中，想要详细理解可以参考代码中的注释
package com.hyc.DataStructure.Stack; import java.util.Scanner; /** * @projectName: DataStructure * @package: com.hyc.DataStructure.Stack * @className: ArrayStackDemo * @author: 冷环渊 doomwatcher * @description: TODO 用数组来模拟栈 * @date: 2021/12/23 18:08 * @version: 1.0 */ public class ArrayStackDemo { public static void main(String[] args) { //测试一下 ArrayStack 是否正确 //先创建一个 ArrayStack 对象->表示栈 ArrayStack stack = new ArrayStack(4); String key = ""; boolean loop = true; //控制是否退出菜单 Scanner scanner = new Scanner(System.in); while (loop) { System.out.println("show: 表示显示栈"); System.out.println("exit: 退出程序"); System.out.println("push: 表示添加数据到栈(入栈)"); System.out.println("pop: 表示从栈取出数据(出栈)"); System.out.println("请输入你的选择"); key = scanner.next(); switch (key) { case "show": stack.list(); break; case "push": System.out.println("请输入一个数"); int value = scanner.nextInt(); stack.push(value); break; case "pop": try { int res = stack.pop(); System.out.printf("出栈的数据是 %d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case "exit": scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~~"); } } class ArrayStack { //栈的最大长度 private int MaxSize; //模拟栈 数据就放在这个数组里 private int[] stack; // 等于栈顶 默认等于-1 代表最底部分 private int top = -1; public ArrayStack() { } // 初始化栈 public ArrayStack(int maxSize) { MaxSize = maxSize; stack = new int[maxSize]; } //返回栈顶 只是显示 并不是 pop 不会改变栈的结构 public int peek() { return stack[top]; } //判断栈是否是满的 public boolean isFull() { return top == MaxSize - 1; } //判断栈 是否是空的 public boolean isempty() { return top == -1; } //将数据压入栈 public void push(int data) { if (isFull()) { System.out.println("栈满"); return; } top++; stack[top] = data; } // 将数据取出栈 public int pop() { if (isempty()) { throw new RuntimeException("栈是空的 无法取出"); } int value = stack[top]; top--; return value; } //遍历栈 遍历的时候需要从栈顶开始显示数据 public void list() { if (isempty()) { System.out.println("栈是空的"); } // 从栈顶开始输出 其实就是倒序的输出数组 for (int i = top; i >= 0; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } } }
小总结
这里我们用数组模拟了栈的一些基础操作，入栈出栈遍历内容，
除了使用数组，我们还可以使用链表来实现栈，这里我也写了这种写法有详细的注释，代码如下
package com.hyc.DataStructure.Stack; /** * @projectName: DataStructure * @package: com.hyc.DataStructure.Stack * @className: ListStackDemo * @author: 冷环渊 doomwatcher * @description: TODO 用链表来模拟栈 * @date: 2021/12/23 18:23 * @version: 1.0 */ public class ListStackDemo { public static void main(String[] args) { listStack listStack = new listStack(); listStack.push(5); listStack.push(6); listStack.push(9); System.out.println("出栈前"); listStack.list(); System.out.println("出栈后"); System.out.println("出栈：" + listStack.pop()); System.out.println("出栈：" + listStack.pop()); listStack.list(); } } class listStack { //创建一个头结点 StackNode head = new StackNode(0); StackNode temp = head; //判断是否为空 public boolean isempty() { return head.next == null; } //压入栈 public void push(int value) { //创建节点对象 StackNode newnode = new StackNode(value); //改变头节点指针的指向 temp.next = newnode; //指针后移 temp = temp.next; } //出栈 public int pop() { if (isempty()) { throw new RuntimeException("栈空"); } StackNode Before = head; //将 before 节点遍历到 temp也就是最后一个节点的上一个节点，让temp指针想前遍历 while (true) { if (Before.next == temp) { break; } Before = Before.next; } //将before的下一个节点为空相当于出栈之后 删除引用 Before.next = null; //取值 int value = temp.data; //此时 before指向的这个节点就是上一个节点的位置，将temp前移动，重复操作实现出栈 temp = Before; return value; } //遍历栈 public void list() { // 判断非空 if (isempty()) { System.out.println("栈是空的"); return; } StackNode temp = head; while (true) { if (temp.next == null) { break; } System.out.println(temp.next.data); temp = temp.next; } } } //单向链表节点 class StackNode { // 数据 public int data; //下一个节点 public StackNode next; public StackNode(int data) { this.data = data; } //方便输出语句输出 @Override public String toString() { return "StackNode{" + ", data='" + data + '\'' + ", next=" + next + '}'; } }
中缀表达式计算器
使用栈来实现综合计算器
计算机底层是如何处理这种公式的呢，思路如下
我们需要使用两个栈，一个记录数字，一个记录符号，根据这个栈的数据特性来通过符号和数据的出现规则来实现公式的计算
思路
1.通过一个index值（素引）,来遍历我们的表达式
2.如果我们发现是一个数字，就直接入数栈
3.如果发现扫描到是一个符号，就分如下情况
3.1如果发现当前的符号栈为空，就直接入栈
3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中
的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算，
将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大
于栈中的操作符，就直接入符号找。
4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行.
5.最后在数栈只有一个数字，就是表达式的结果
验证：3+2*6-2=13
这里我们就根据上面的思路实现接下来的思路
代码实现
package com.hyc.DataStructure.Stack; /** * @projectName: DataStructure * @package: com.hyc.DataStructure.Stack * @className: Calculator * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/24 20:39 * @version: 1.0 */ public class Calculator { public static void main(String[] args) { // 根据文章的思路 我们这里完成对一串计算只包含加减乘除的表达式运算操作 String expression = "3+2*6-2"; /** 计算思路 使用栈完成表达式的计算思路 * 1.通过一个index值（素引）,来遍历我们的表达式 * 2.如果我们发现是一个数字，就直接入数栈 * 3.如果发现扫描到是一个符号，就分如下情况 * 3.1如果发现当前的符号栈为空，就直接入栈 * 3.2如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中 * 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算， * 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大 * 于栈中的操作符，就直接入符号找。 * 4.当表达式扫描完毕，就顺序的从数楼和符号栈中pop出相应的数和符号，并运行. * 5.最后在数栈只有一个数字，就是表达式的结果 * 验证：3+2*6-2=13 * 这里我们就根据上面的思路实现接下来的思路 * */ // 创建两个栈 一个存放需要计算的数字 一个存放需要运算的符号 ArrayCalStack numStack = new ArrayCalStack(10); ArrayCalStack operStack = new ArrayCalStack(10); // 定义相关变量 int index = 0; //用于指针扫描 int num1 = 0; int num2 = 0; int oper = 0; int res = 0; //将每次扫描得到的char保存到ch char ch; //用于萍姐多位数 String keepNums = ""; //开始while 循环扫描表达式 expression while (true) { // 一次得到expression的每一个字符 ch = expression.substring(index, index + 1).charAt(0); // 判断ch 是什么（数字或者符号）之后进行操作 if (operStack.isOper(ch)) { /* 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中 * 的操作符，就需要从数栈中pop出两个数在从符号栈中pop出一个符号，进行运算， * 将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大 * 于栈中的操作符，就直接入符号找。*/ //非空判断 if (!operStack.isempty()) { if (operStack.priotrity(ch) <= operStack.priotrity(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 { // 如果是数字 就直接进入数字栈 /*思路 * 这里我们要考虑到多位数 在处理多位数的时候 * 我们需要扫描这个数的下一位一直到找到下一个符号 * 这个时候我们定义一个字符串用于拼接找到的数 * */ // 处理多位数 keepNums += ch; // 如果ch已经是 expression 最后一位name就直接入栈 if (index == expression.length() - 1) { numStack.push(Integer.parseInt(keepNums)); } else { // 判断下一个字符是不是数字 ，如果是就继续向下判断 是运算符则入栈，这里我们要看的是结束的地方是不是符号 if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) { //如果最后一位事原酸父则如入栈 这里我们的操作变化就是 keepnums =1 或者是 keepnums = 123 numStack.push(Integer.parseInt(keepNums)); // 加入之后能讲 keepnunms清空 用于下一位的判断 keepNums = ""; } } } // 让 index +1 并判断是否扫描到expression 最后 index++; if (index >= expression.length()) { break; } } // 当表达式扫描完毕，就循序的从数栈和符号栈中 pop出相应的数和符号，并且运行 while (true) { // 如果符号为空，则计算到最后的结果，数栈中只有一个数字【结果】 if (operStack.isempty()) { break; } num1 = numStack.pop(); num2 = numStack.pop(); oper = operStack.pop(); res = numStack.cal(num1, num2, oper); //入栈 numStack.push(res); } // 将数栈最后的数，pop出，就是结果 int res2 = numStack.pop(); System.out.printf("表达式%s = %d", expression, res2); } } /* * 应为要实现计算器 我们需要编写一些新的功能， * */ class ArrayCalStack { //栈的最大长度 private int MaxSize; //模拟栈 数据就放在这个数组里 private int[] stack; // 等于栈顶 默认等于-1 代表最底部分 private int top = -1; public ArrayCalStack() { } // 初始化栈 public ArrayCalStack(int maxSize) { MaxSize = maxSize; stack = new int[maxSize]; } //返回栈顶 只是显示 并不是 pop 不会改变栈的结构 public int peek() { return stack[top]; } //判断栈是否是满的 public boolean isFull() { return top == MaxSize - 1; } //判断栈 是否是空的 public boolean isempty() { return top == -1; } //将数据压入栈 public void push(int data) { if (isFull()) { System.out.println("栈满"); return; } top++; stack[top] = data; } // 将数据取出栈 public int pop() { if (isempty()) { throw new RuntimeException("栈是空的 无法取出"); } int value = stack[top]; top--; return value; } //遍历栈 遍历的时候需要从栈顶开始显示数据 public void list() { if (isempty()) { System.out.println("栈是空的"); } // 从栈顶开始输出 其实就是倒序的输出数组 for (int i = top; i >= 0; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } } /* 返回运算符的优先级 这个规则我们可以自己来设定 优先级使用数字来表示 * 数字越大优先级约高 * */ public int priotrity(int oper) { if (oper == '*' || oper == '/') { return 1; } else if (oper == '+' || oper == '-') { return 0; } else { return -1; } } // 判断是不是一个字符 public boolean isOper(char val) { return val == '*' || val == '/' || val == '+' || val == '-'; } // 计算操作 用于执行运算 public int cal(int num1, int num2, int oper) { // 存放计算的结果 int res = 0; switch (oper) { case '+': res = num1 + num2; break; case '-': res = num2 - num1; break; case '/': res = num2 / num1; break; case '*': res = num1 * num2; break; default: break; } return res; } }
这里我们实现了基础的表达式运算，但是我们没有考虑的事
我们实现了基本计算，但是没有考虑小括号等
中缀表达式对我们来说是十分的好算的，但是对于计算机计算是不方便的，之后会给大家更新适合计算机计算的后缀表达式
