文章目录
- 一、栈的初解
- 栈的基本介绍
- 栈的相关操作
- 栈的应用场景
- 二、栈的快速入门
- 思路分析：
- 代码实现
- 栈的构造方法：
- 判断栈空
- 判断栈满
- 入栈
- 出栈
- 遍历栈
- 测试
- 三、栈的应用
- 使用栈完成表达式的计算
- 前缀、中缀、后缀表达式（逆波兰表达式）
- 前缀表达式
- 前缀表达式简介
- 前缀表达式的计算机求值
- 中缀表达式
- 后缀表达式
- 后缀表达式简介
- 后缀表达式的计算机求值
- 逆波兰计算器
- 四、中缀转后缀表达式
- 具体步骤
- 代码实现
一、栈的初解 栈的基本介绍
栈的英文为stack
栈是一个先入后出的有序列表
栈是一种限制 线性表中元素插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一段，为变化的一段，称为栈顶（Top），另一端为固定的一端，称为栈底（Bottom）。
根据栈的定义可知，最先放入栈的元素在栈底，最后放入的元素在栈顶，而删除元素正好相反，最后放入的元素最先删除，最先放入的元素最后删除；
入栈（push）
出栈（pop）
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
- 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量登上护具存入堆栈中
- 表达式的转换【中缀表达式转后缀表达式】与求值（实际解决）
- 二叉树的遍历
- 图形的深度优先（depth-first）搜索法
二、栈的快速入门 思路分析：
实现栈的思路分析：
- 使用数组来模拟栈
- 定义一个top来表示栈顶，初始化为-1
- 入栈的操作：当有数据加入到栈的时候，top++，stack[top]=data
- 出栈的操作：int value=stack[top];top–,return value
class ArrayStack {
private int maxSize;//栈的大小
private int[] stack;//数组，模拟栈，数据放在该数组中
private int top = -1;//表示栈顶，初始化为-1
//构造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
//后面接其它的方法
判断栈空
//栈空
public boolean isEmpty() {
return top == -1;
}
判断栈满
//栈满
public boolean isFull() {
return top == maxSize - 1;
}
入栈
//入栈
public void push(int value) {
//先判断栈是否已经满了
if (isFull()) {
return;
}
top++;
stack[top] = value;
}
出栈
//出栈 将栈顶的数据返回
public int pop() {
//先判断栈是否为空
if (isEmpty()) {
//抛出异常
throw new RuntimeException("栈空，没有数据");
//抛出异常，则不需要return
}
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]=%dn",i,stack[i]);
}
}
测试
三、栈的应用 使用栈完成表达式的计算
- 通过index值（索引），来遍历我们的表达式
- 如果我们发现的是一个数字，就直接入数栈，
- 如果发现扫描到的是一个符号，就分如下情况
- 如果发现当前符号栈为空，就直接入栈
- 如果符号栈不为空，有操作符，就进行比较，如果当前操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，在符号栈汇总pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈；
- 如果当前操作符的优先级大于栈中操作的优先级就直接如符号栈；
- 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行，
- 最后数栈只有一个数字，就是表达式的结果
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前
例如（3+4）*5-6这个中缀表达式对应的前缀表达式为- * + 3 4 5 6
从右至左扫描表达式，遇到数字的时候，将数字压入到堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们作相应的计算（栈顶元素和次顶元素），并将结果入栈，重复上述过程知道表达式最左端，最后运算得到的值即为表达式的结果；
例如（3+4）*5-6这个中缀表达式对应的前缀表达式为- * + 3 4 5 6，针对前缀表达式求值的步骤如下：
- 从右至左扫描，将6、5、4、3压入栈堆
- 遇到 + 运算符，因此弹出3,4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
- 接下来是* 运算符，计算出35-6的值，即29，由此得到最终结果
中缀表达式就是最常见的运算表达式，如（3+4）*5-6；
中缀表达式的求值是我们最为熟悉的，但是对于计算机来说却不好操作，因此，在计算结果的时候，往往会将中缀表达式转为其它表达式来操作（一般转为后缀表达式）；
后缀表达式又称逆波兰表达式，与前缀表达式非常相似，只是运算符位于操作数之后
例如：（3+4)*5-6对应的后缀表达式就是3 4 + 5 * 6 -
再例如;
从左至右扫描表达式，遇到数字的时候，将数字压入到堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们作相应的计算（栈顶元素和次顶元素），并将结果入栈，重复上述过程知道表达式最右端，最后运算得到的值即为表达式的结果；
例如 （3+4)*5-6对应的后缀表达式就是3 4 + 5 * 6 -，针对后缀表达式求值的步骤如下：
- 从左至右扫描，将3和4压入堆栈
- 遇到+ 运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈
- 将5入栈
- 接下来是运算符，因此弹出5和7，计算出75=35，将35入栈
- 将6入栈
- 最后是 - 运算符，计算出35-6的值，即29，由此得出最终结果
public class PolandNotation {
public static void main(String[] args) {
//先定义一个逆波兰表达式
//3+4)*5-6=> 3 4 + 5 * 6 -
//为了方便，波兰表达式中数字和符号之间使用符号隔开
String suffixExpression = "3 4 + 5 * 6 -";
//思路：
//1.先将suffixExpression放到ArrayList中
//2.将ArrayList传递给一个方法，遍历ArrayList配合栈，完成计算
List list = getListString(suffixExpression);
int res=calulate(list);
System.out.println("计算的结果是="+res);
}
//将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
public static List getListString(String suffixExpression) {
//将suffixExpression进行分隔
String[] split = suffixExpression.split(" ");
ArrayList list = new ArrayList<>();
for (String ele : split) {
list.add(ele);
}
return list;
}
public static int calulate(List ls) {
//创建一个栈
Stack stack = new Stack<>();
//遍历ls
for (String item : ls) {
//这里使用正则表达式来取出数
if (item.matches("\d+")) {//匹配的是多位数
//入栈
stack.push(item);
} else {
//pop出两个数并运算，再入栈
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if (item.equals("+")) {
res = num2 + num1;
} else if (item.equals("-")) {
res = num1 - num2;
} else if (item.equals("*")) {
res = num1 * num2;
}else if (item.equals("/")){
res=num1/num2;
}else{
throw new RuntimeException("运算符有误！");
}
//把res入栈
stack.push(String.valueOf(res));
}
}
//最后留在stack中的数据就是运算结果
return Integer.parseInt(stack.pop());
}
四、中缀转后缀表达式
后缀表达式适合计算机进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发过程中，我们需要将中缀表达式转为后缀表达式
具体步骤- 初始化两个栈，运算符栈s1和存储中间结果的栈2
- 从左至右扫描中缀表达式
- 遇到操作数时，将其压s2
- 遇到运算符时，比较其与s1栈顶预算符的优先级
* 如果s1为空，或栈顶运算符为左括号“（”，则直接将此操作符入栈
* 否则，若优先级比栈顶操作符的高，也将此运算符压入s1
* 否则，将s1栈顶的运算符弹出并压入s2中，再次转到第一步中与新的栈顶运算符进行比较 - 遇到括号时：
* 如果是左括号“（”，则直接压入s1
* 如果是右括号“）”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 - 重复步骤2至5，直到表达式最右边
- 将s1中剩余的运算符依次弹出并压入s2；
- 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
这里需要定义两个方法，一个是将运算字符串转换为列表，并且需要注意多位数数字不能分开，另一个是将列表转换为后缀表达式
//将中缀表达式转换为后缀表表达式
public static List parseSuffixExpressionList(List ls) {
//定义两个栈
Stack s1 = new Stack<>();//符号栈
//说明：因为s2这个栈，在整个转换过程中，没有pop操作，而而且后面我们还要逆序输出
//因此比较麻烦，我们可以考虑使用List来代替s2栈
List s2 = new ArrayList<>();//代替s2来存储中间结果；
//开始遍历
for (String item : ls) {
//如果是一个数，加入到s2；
if (item.matches("\d+")) {
s2.add(item);
} else if (item.equals("(")) { //如果是一个左括号
s1.push(item);
} else if (item.equals(")")) {//如果是一个右括号
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();//将左括号弹出栈，消除小括号
} else {
//当item的优先级小于或等于栈顶运算符的优先级的时候
while (s1.size() != 0 && Operation.getValue(item)<=Operation.getValue(s1.peek())){
s2.add(s1.pop());
}
//还需要将item压入栈中
s1.push(item);
}
}
//将s1中剩余的运算符依次弹出并加入到s2中
while (s1.size()!=0){
s2.add(s1.pop());
}
return s2;
}
//定义一个将字符串计算数转换为列表的方法的方法
public static List revers(String expression) {
ArrayList res = new ArrayList<>();
int i = 0;//这是一个指针，用于遍历中缀表达式中的字符串
String str;//对多位数的拼接
char c;//每遍历到一个字符串，就放入到c
do {
//如果c是一非数字，需要将其加入到res中
if ((c = expression.charAt(i)) < 48 || (c = expression.charAt(i)) > 57) {
res.add("" + c);
i++;
} else {
//如果是一个数，则需要考虑多位数
str = "";//先将str置空
while (i < expression.length() && (c = expression.charAt(i)) >= 48 && (c = expression.charAt(i)) <= 57) {//判断该字符是否为数字,且不为最后一位
str += c;
i++;
}
res.add(str);
}
} while (i < expression.length());
return res;
}
如果感觉内容写的还不错的话，一键三连不迷路！！！！
后面将会更新更多学习内容，一起学习吧！！！！！！
