一、栈

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

二、栈的应用场景

1、子程序的调用

在调往子程序前,会先将下个指令的地址存放到堆栈中,直到子程序执行完后再将地址抛出,以回到原来的程序。

2、处理递归调用

和子程序的调用类似,除了村下个指令的地址外,还要存放参数,区域变量等数据。

3、表达式的转换

中缀表达式转后缀表达式

4、二叉树的遍历

5、图形的深度优先搜索法

三、栈实现综合计算器(中缀表达式)

1、思路分析

* 通过一个index值(索引),来遍历我们的表达式
* 如果发现是一个数字直接入数栈
* 如果发现当前的符号栈是空,就直接入栈
*
如果发现符号栈有操作符,就进行比较,如果当前的操作符的优先级小于或等于栈中的操作符,就需要从数栈中pop出一个符号,进行运算,将得到结果,入数栈,然后将当前的操作符入符号栈,如果当前的操作符的优先级大于栈中的操作符,就直接入符号栈。
* 当表达式扫描完毕,就顺序的从数栈和符号栈中pop出相应的数和符号,并进行运算。
* 最后在数栈中只有一个数字,就是表达式的结果。
2、代码实例

(1)ArrayStack工具类
package dataStructure.stack; public class ArrayStack { private int maxSize; //
栈的大小 private int[] stack; // 数组,数组模拟栈,数据就放在该数组 private int top = -1;//
top表示栈顶,初始化为-1 //构造器 public ArrayStack(int maxSize) { this.maxSize = maxSize;
stack = new int[this.maxSize]; } //增加一个方法,可以返回当前栈顶的值, 但是不是真正的pop public int
peek() { return stack[top]; } //栈满 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; } top++; stack[top] = value; } //出栈-pop,
将栈顶的数据返回 public int pop() { //先判断栈是否空 if(isEmpty()) { //抛出异常 throw new
RuntimeException("栈空,没有数据~"); } int value = stack[top]; top--; return value; }
//显示栈的情况[遍历栈], 遍历时,需要从栈顶开始显示数据 public void list() { if(isEmpty()) {
System.out.println("栈空,没有数据~~"); return; } //需要从栈顶开始显示数据 for(int i = top; i >=
0 ; i--) { System.out.printf("stack[%d]=%d\n", i, stack[i]); } }
//返回运算符的优先级,优先级是程序员来确定, 优先级使用数字表示 //数字越大,则优先级就越高. public int priority(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; // 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;
} }
(2)测试类
package dataStructure.stack; public class Calculator { public static void
main(String[] args) { //根据前面老师思路,完成表达式的运算 String expression = "100/5+2*3-1"; //
25 //创建两个栈,数栈,一个符号栈 ArrayStack numStack = new ArrayStack(10); ArrayStack
operStack = new ArrayStack(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()) {
//如果符号栈有操作符,就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
//在从符号栈中pop出一个符号,进行运算,将得到结果,入数栈,然后将当前的操作符入符号栈 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); // 1 + 3 } } else { //如果是数,则直接入数栈 //numStack.push(ch - 48);
//? "1+3" '1' => 1 //分析思路 //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))) {
//如果后一位是运算符,则入栈 keepNum = "1" 或者 "123"
numStack.push(Integer.parseInt(keepNum)); //重要的!!!!!!, keepNum清空 keepNum = "";
} } } //让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); } }
3、控制台输出

技术
©2019-2020 Toolsou All rights reserved,
PYTHON入门期末复习汇总Python+OpenCV人脸识别技术详解员工网上晒腾讯年终奖:每人100股公司股票 价值超6万元!中国最长高铁正式开通!跑完全程最快30.5小时Unity 场景异步加载(加载界面的实现)NOI2019 游记用C++跟你聊聊“原型模式” (复制/拷贝构造函数)比尔·盖茨:疫情后彻底恢复正常可能要到2022年末这些歌,程序员千万万万万别听!随机森林篇 R语言实现