栈的一个实际需求
请输入一个表达式
计算式: [722-5+1-53-3] 点击计算[如下图]
请问: 计算机底层是如何运算得到结果的? 注意: 不是简单地把算式列出运算,因为我们看这个算式 [722-5+1-53-3] 但是计算机是则么理解这个算式的(对计算机而言, 他接收到的就是一个字符串), 我们讨论的是这个问题, -> 栈
栈的介绍
- 栈的英文为Stack
- 栈是一个先入后出(FILO-First In Last Out)的有序列表
- 栈是限制线性表中元素的插入和删除,只能在线性表的同一端进行的一种特殊线性表, 允许插入和删除的一端为变化的一端,称为栈顶(TOP), 另一端为固定的一端,称为栈底(Bottom).
- 根据栈的定义可知, 最先放入栈中元素在栈底, 最后放入的元素在栈顶, 而删除元素刚好相反, 最后放入的元素最先被删除,最先放入的元素,最后被删除
- 图解方式说明出栈(POP), 和入栈(PUSH)的概念
栈的应用场景
- 子程序的调用: 在跳往子程序之前, 会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出以回到原来的程序中(我是没有看懂这个…)
- 处理递归调用: 和子程序的调用类似, 只是除了储存下一个指令的地址外,也将参数,区域变量等数据存入堆栈中
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)
- 二叉树的遍历
-
栈的快速入门
需求
用数组模拟栈的使用,由于栈是一种有序列表,当然可以使用数组的结构来存储栈的数据内容,下面我们就使用数组模拟栈的出栈,入栈等操作
思路分析
实际思路分析并画出示意图
实现栈的思路分析使用数组模拟栈
- 定义一个top来表示栈顶初始化为-1
- 入栈的操作: 当 有数据加入到栈时, Top++, stack[top] = data
- 出栈的操作: int value = stack[top]; top—;return value
代码实现(使用数组模拟栈)
```java package com.dance.stack;
public class ArrayStackDemo { public static void main(String[] args) { ArrayStack arrayStack = new ArrayStack(10); arrayStack.show(); for (int i = 0; i < 12; i++) { arrayStack.push(i+1); } arrayStack.show(); while (!arrayStack.isEmpty()){ System.out.println(“出栈:” + arrayStack.pop()); } arrayStack.show(); } }
/**
定义一个数组栈 */ class ArrayStack{
/**
栈 */ private final int[] stack;
/**
栈顶 */ private int top = -1;
/**
栈的最大容量 */ private final int maxSize;
public ArrayStack(int size) { this.maxSize = size; stack = new int[size]; }
/**
- 是否栈满
@return true:满了 false:没满 */ public boolean isFull(){ return top == maxSize -1; }
/**
- 是否栈空
@return ture:空了 false:没空 */ public boolean isEmpty(){ return top == -1; }
/**
- 压栈
@param newValue 值 */ public void push(int newValue){ if(isFull()){
System.out.println("栈满了,无法加入数据:"+newValue);return;
} top++; stack[top] = newValue; }
/**
- 弹出
@return 栈顶数据 */ public int pop(){ if(isEmpty()){
throw new RuntimeException("栈空了,无法弹出数据");} int value = stack[top]; top—; return value; }
/**
- 遍历栈
*/
public void show(){
if(isEmpty()){
} for (int i = top; i >= 0; i—) {System.out.println("栈为空,无法遍历"); return;
} System.out.println(); }System.out.print(stack[i] + "\t");
}
执行结果
```java
栈为空,无法遍历
栈满了,无法加入数据:11
栈满了,无法加入数据:12
10 9 8 7 6 5 4 3 2 1
出栈:10
出栈:9
出栈:8
出栈:7
出栈:6
出栈:5
出栈:4
出栈:3
出栈:2
出栈:1
栈为空,无法遍历
栈实现综合计算器(中缀表达式)
需求
思路分析
代码实现
package com.dance.stack;
public class CalculatorDemo {
public static void main(String[] args) {
// 定义表达式
String expression = "3+2*6-2";
System.out.println("计算结果: " + expressionCalculator(expression));
}
/**
* 表达式计算
* @param expression 表达式
* @return 结果
*/
public static int expressionCalculator(String expression) {
// 创建两个栈,一个用来存储数字,一个用来存储操作符
// 数字栈
ArrayStackExt numStack = new ArrayStackExt(10);
// 操作符栈
ArrayStackExt operationStack = new ArrayStackExt(10);
// 扫描并计算中缀表达式
scannerExpression(expression, numStack, operationStack);
// 计算顺序的操作
return calculatorOther(numStack, operationStack);
}
/**
* 表达式扫描
* @param expression 表达式
* @param numStack 数栈
* @param operationStack 操作符栈
*/
public static void scannerExpression(String expression, ArrayStackExt numStack, ArrayStackExt operationStack) {
// 定义扫描索引
int index = 0;
char ch = ' '; // 将每次扫描得到的char保存到ch
// 开始循环扫描表达式
while (index < expression.length()) {
// 循环的到每一个字符
ch = expression.substring(index, index + 1).charAt(0);
// 判断是不是操作符
if (ArrayStackExt.isOperation(ch)) {
// 是操作符
// 判断当前符号栈是不是空
if (operationStack.isEmpty()) {
// 是空
operationStack.push(ch);
} else {
// 不是空
// 获取栈中的操作符
int operation = operationStack.pop();
// ch 就是新的操作符
// 进行比较
if (operationStack.comparator(ch, operation)) {
// 小于等于
// 计算
// 将返回的结果压入数栈
numStack.push(numStack.cal(numStack.pop(), numStack.pop(), operation));
// 将当前的操作符 压入操作符栈
operationStack.push(ch);
} else {
// 大于
// 将原来弹出栈的操作符重新压入栈中
operationStack.push(operation);
// 直接压入符号栈
operationStack.push(ch);
}
}
} else {
// 不是操作符,是数字
// 直接压入数栈(需要将字符转化为数字)
numStack.push(Integer.parseInt(String.valueOf(ch)));
}
index++;
}
}
/**
* 计算剩余的操作符
* @param numStack 数栈
* @param operationStack 操作符栈
* @return 结果
*/
public static int calculatorOther(ArrayStackExt numStack, ArrayStackExt operationStack) {
// 当扫描完成后,同时操作符栈中的操作符是顺序的
while (!operationStack.isEmpty()) {
numStack.push(numStack.cal(numStack.pop(), numStack.pop(), operationStack.pop()));
}
return numStack.pop();
}
}
class ArrayStackExt extends ArrayStack {
public ArrayStackExt(int size) {
super(size);
}
/**
* 判断操作符的优先级
* @param left 左侧操作符
* @param right 右侧操作符
* @return 左侧是否小于等于右侧
*/
public boolean comparator(int left, int right) {
return priority(left) <= priority(right);
}
// 返回运算符的优先级,优先级是程序员来确定的,优先级使用数字表示,数字越大,优先级越高
public int priority(int operation) {
switch (operation) {
case '*':
case '/':
return 1;
case '+':
case '-':
return 0;
default:
throw new RuntimeException("操作符错误");
}
}
/**
* 判断是不是操作符
* @param operation 操作符
* @return true:是 false:不是
*/
public static boolean isOperation(char operation) {
return operation == '+' || operation == '-' || operation == '*' || operation == '/';
}
/**
* 计算
*
* @param num1 左边数字
* @param num2 右边数字
* @param operation 操作符
* @return 结果
*/
public int cal(int num1, int num2, int operation) {
switch (operation) {
case '+':
return num1 + num2;
case '-':
return num2 - num1; // 注意顺序,加和乘无所谓,因为栈的原因num2需要在前面
case '*':
return num1 * num2;
case '/':
return num2 / num1;
default:
throw new RuntimeException("计算符号错误");
}
}
}
执行结果
计算结果: 13
实现多位数计算(扩展)
package com.dance.stack;
public class CalculatorDemo {
public static void main(String[] args) {
// 定义表达式
String expression = "30+2*6-2";
System.out.println("计算结果: " + expressionCalculator(expression));
}
/**
* 表达式计算
*
* @param expression 表达式
* @return 结果
*/
public static int expressionCalculator(String expression) {
......
}
/**
* 表达式扫描
*
* @param expression 表达式
* @param numStack 数栈
* @param operationStack 操作符栈
*/
public static void scannerExpression(String expression, ArrayStackExt numStack, ArrayStackExt operationStack) {
// 定义扫描索引
int index = 0;
char ch = ' '; // 将每次扫描得到的char保存到ch
// 定义数字字符串 用于解决多位数字问题
StringBuilder keepNum = null;
// 开始循环扫描表达式
while (index < expression.length()) {
keepNum = new StringBuilder();
// 循环的到每一个字符
ch = expression.substring(index, index + 1).charAt(0);
// 判断是不是操作符
if (ArrayStackExt.isOperation(ch)) {
......
} else {
// 不是操作符,是数字
// 直接压入数栈(需要将字符转化为数字)(只能处理单位数)
// numStack.push(Integer.parseInt(String.valueOf(ch)));
// 处理多位数,
/*
分析思路:
1:当处理多位数时,不能发现是一个数就直接压栈,因为他可能是多位数
2:在处理数,需要向expression的表达式的index后继续判断是不是数字, 如果是数字就继续扫描,如果是符号,就截止到符号的前一位
3:所以我们定义一个字符串用于拼接
*/
keepNum.append(ch);
for (int i = index+1; i < expression.length(); i++) {
char after = expression.substring(i, i + 1).charAt(0);
if(ArrayStackExt.isOperation(after)){
break;
}else{
index++;
keepNum.append(after);
}
}
// 转为数字
numStack.push(Integer.parseInt(keepNum.toString()));
}
index++;
}
}
/**
* 计算剩余的操作符
*
* @param numStack 数栈
* @param operationStack 操作符栈
* @return 结果
*/
public static int calculatorOther(ArrayStackExt numStack, ArrayStackExt operationStack) {
// 当扫描完成后,同时操作符栈中的操作符是顺序的
while (!operationStack.isEmpty()) {
numStack.push(numStack.cal(numStack.pop(), numStack.pop(), operationStack.pop()));
}
return numStack.pop();
}
}
class ArrayStackExt extends ArrayStack {
......
}
执行结果
计算结果: 40
前缀, 中缀, 后缀表达式(逆波兰表达式):扩展
前缀表达式(波兰表达式)
- 前缀表达式又称为波兰表达式,前缀表达式的运算符位于操作数之前
举例说明: (3+4)X5-6 对应的前缀表达式就是 - X + 3 4 5 6
前缀表达式的计算机求值
从右到左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对他们进行计算,并将结果重新压入数栈,重复上述过程直到表达式的最左端,最后运算得出的值即为表达式的结果
例如:
(3+4)X5-6 对应的前缀表达式就是- X + 3 4 5 6, 针对前缀表达式求值步骤如下从右至左扫描, 将 6 5 4 3压入堆栈
- 遇到+运算符, 因此弹出3和4(3为栈顶元素,4为次顶元素), 计算出3+4的值得7,再将7压入数栈
- 接下来是X运算符,因此弹出7,5,计算7X5=35,将35压入数栈
-
中缀表达式
中缀表达式就是常见的运算表达式 如(3+4)X5-6
中缀表达式的求值是我们最熟悉的,但是对计算机来说却不好操作,因此在计算结果时,往往会将中缀表达式转成其他表达式来操作(一般转为后缀表达式)
后缀表达式
后缀表达式又称为逆波兰表达式,与前缀表达式相似,只是运算位于操作数之后
- 中缀转后缀例子:(3+4)X5-6 对应的后缀表达式就是 3 4 + 5 X 6 -
后缀表达式的计算机求值
从左至右扫描表达式,遇到数字时,将数字压入数栈,遇到运算符时,弹出栈顶的两个数,进行计算后并将结果重新压入数栈,重复上述过程直到最右端,最后运算得出的值,就是表达式的结果
例如: (3+4)X5-6 对应的后缀表达式就是 3 4 + 5 X 6 -
- 从左至右扫描, 将3 4 压入数栈
- 遇到 + 运算符,因此弹出4 和 3 计算出 3 + 4 的值 7后,将7压入数栈
- 将5压入数栈
- 接下来就是X运算符,因此弹出 5 7,计算 5 X 7 = 35 后将35压入数栈
- 将6压入数栈
-
逆波兰计算器
需求
输入一个逆波兰表达式,使用栈(Stack),计算其结果
- 支持小括号和多位整数,因为这里我们主要讲的是数据结构,因此计算器进行简化,只支持对整数的计算
- 思路分析
代码实现
```java package com.dance.stack;
import java.util.Arrays; import java.util.List;
public class PolandNotation { public static void main(String[] args) { // 先定义一个逆波兰表达式 // (3+4)X5-6 => 3 4 + 5 x 6 - // 为了扫描方便,使用空格隔开 String suffixExpression = “3 4 + 5 * 6 -“; System.out.println(“计算结果: “+ calPoland(suffixExpression)); }
public static int calPoland(String expression) {
// 将表达式通过空格转为list
List<String> expressList = Arrays.asList(expression.split(" "));
ArrayStackExt numStack = new ArrayStackExt(10);
for (String s : expressList) {
char ch = s.charAt(0);
if (ArrayStackExt.isOperation(ch)) {
// 操作符
// 弹出栈顶的两个数字
int num1 = numStack.pop();
int num2 = numStack.pop();
numStack.push(numStack.cal(num1, num2, ch));
} else {
// 将数字直接压入数栈
numStack.push(Integer.parseInt(String.valueOf(ch)));
}
}
// 弹出结果
return numStack.pop();
}
}
执行结果
```java
计算结果: 29
中缀表达式转后缀表达式
可以看到,后缀表达式适合计算机进行计算, 但是人就不太好些了,尤其是复杂的, 因此在开发中, 我们需要将中缀表达式转成后缀表达式
具体步骤
- 初始化两个栈, 运算符栈s1,和存储中间结果栈s2
- 从左至右扫描中缀表达式
- 遇到操作数时, 将其压入s2
- 遇到操作符时, 比较其与s1栈顶运算符的优先级
- 如果s1为空, 或栈顶运算符为左括号”(“, 则直接将此运算符入站
- 否则, 若优先级比栈顶运算符的高, 也将运算符压入s1
- 否则,将s1栈顶的运算符弹出并压入到s2中,再次(转到4.1)与s1中新的栈顶运算符比较
- 遇到括号时
import java.util.Arrays; import java.util.List; import java.util.Stack;
public class PolandNotation { public static void main(String[] args) { // 先定义一个逆波兰表达式 // (3+4)X5-6 => 3 4 + 5 x 6 - // 为了扫描方便,使用空格隔开 // String suffixExpression = “3 4 + 5 6 -“; String middleExpression = “1+((2+3)4)-5”; String suffixExpression = middlePolandToSuffixPoland(middleExpression); System.out.println(“计算结果: “+ calSuffixPoland(suffixExpression)); }
public static String middlePolandToSuffixPoland(String expression){
List<String> expressList = Arrays.asList(expression.split(""));
Stack<String> numStack = new Stack<>();
Stack<String> operStack = new Stack<>();
ArrayStackExt comparator = new ArrayStackExt(1);
for (String s : expressList) {
char ch = s.charAt(0);
if(ArrayStackExt.isOperation(ch)){
if(operStack.isEmpty()){
// 操作符栈为空
operStack.push(String.valueOf(ch));
}else{
String stackInOper = operStack.pop();
if(stackInOper.equals("(")){
// 如果是小括号
operStack.push(stackInOper);
operStack.push(String.valueOf(ch));
}else{
if(!comparator.comparator(ch,stackInOper.charAt(0))){
// 大于栈顶的运算符
operStack.push(stackInOper);
operStack.push(String.valueOf(ch));
}else{
// 将栈内的操作符压入数栈
numStack.push(stackInOper);
// 循环4.1
boolean flag = false;
while (!operStack.isEmpty()){
stackInOper = operStack.pop();
if(stackInOper.equals("(")){
// 如果是小括号
operStack.push(stackInOper);
operStack.push(String.valueOf(ch));
flag = true;
break;
}else{
if(!comparator.comparator(ch,stackInOper.charAt(0))){
// 大于栈顶的运算符
operStack.push(stackInOper);
operStack.push(String.valueOf(ch));
flag = true;
break;
}else{
// 将栈内的操作符压入数栈
numStack.push(stackInOper);
}
}
}
// 处理为空也没有压入操作符栈的问题
if(!flag){
operStack.push(String.valueOf(ch));
}
}
}
}
}else if(isKh(ch)){
if(ch == '('){
operStack.push(String.valueOf(ch));
}else{
String res;
while (!(res = operStack.pop()).equals("(")){
numStack.push(res);
}
}
}else{
// 数字
numStack.push(String.valueOf(ch));
}
}
// 处理剩余的操作符
while (!operStack.isEmpty()){
numStack.push(operStack.pop());
}
StringBuffer suffixExpression = new StringBuffer();
while (!numStack.isEmpty()){
String pop = numStack.pop();
suffixExpression.append(pop).append(" ");
}
return suffixExpression.reverse().toString().trim();
}
public static boolean isKh(char ch){
return ch == '(' || ch == ')';
}
public static int calSuffixPoland(String expression) {
// 将表达式通过空格转为list
List<String> expressList = Arrays.asList(expression.split(" "));
ArrayStackExt numStack = new ArrayStackExt(10);
for (String s : expressList) {
char ch = s.charAt(0);
if (ArrayStackExt.isOperation(ch)) {
// 操作符
// 弹出栈顶的两个数字
int num1 = numStack.pop();
int num2 = numStack.pop();
numStack.push(numStack.cal(num1, num2, ch));
} else {
// 将数字直接压入数栈
numStack.push(Integer.parseInt(String.valueOf(ch)));
}
}
// 弹出结果
return numStack.pop();
}
}
执行结果
```java
计算结果: 16
因为是主要写中缀表达式转后缀表达式,就没有考虑多位数和小数点的问题,有喜欢的自己完善一下,老师的代码里面也有完成了的,可以看看,我感觉挺简单的就不写了
若有收获，就点个赞吧
0 人点赞
