1. 栈的一个实际需求
- 输入一个字符串类型的计算表达式，使用栈结构计算出这个表达式的值
- 栈是遵循先入后出（FILO）原则的一个有序列表
- 栈（stack）是限制线性表中的元素的插入和删除只能在线性表的同一端进行的一种特殊的线性表。允许插入和删除的一端，为变化的一端，成为栈顶（top），另一端固定，称为栈底（Bottom）
- 根据栈的定义可知，最先放入栈的元素在栈底，最后放入栈的元素在栈顶；而删除元素正好相反，最先删除的是栈顶元素，最后删除的是栈底元素。
- 出栈与入栈：
3. 应用场景
- 子程序的调用：在跳往子程序之前，会先将下一个指令地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
- 处理递归调用时：和子程序调用类似，只是除了存储下一个指令地址外，也将参数、区域变量等数据存入堆栈中。
- 表达式的转换【中缀表达式转后缀表达式】与求值（给定计算表达式的字符串进行求解）。
- 二叉树的遍历。
- 图形的深度优先【depth-first】搜索。
4. 使用数组模拟栈
class ArrayStack{/*** 属性:* 1.* 2.* 方法:* 1. 构造器* 2. 栈空* 3. 栈满* 4. 查看栈顶元素* 5. 遍历栈* 6. 入栈* 7. 出栈*/int size;int[] stack;int index = -1;// 1. 构造器public ArrayStack(int size){this.size = size;this.stack = new int[size];}// 2. 栈空public boolean isEmpty(){if (index==-1) return true;return false;}// 3. 栈满public boolean isFull(){if (index==size-1) return true;return false;}// 4. 查看栈顶元素public int peek(){return stack[index];}// 5. 遍历栈public void list(){if (isEmpty()){System.out.println("栈空,无元素!");return;}for (int i=0;i<=index;i++)System.out.printf("%d\t",stack[i]);}// 6. 入栈public void push(int x){if (isFull()){System.out.println("栈满,无法入栈!");return;}stack[++index] = x;}// 7. 出栈public int pop() throws Exception {if (isEmpty()){System.out.println("栈空,无法出栈!");throw new Exception("栈空,无法出栈!");}return stack[index--];}}
5. 栈实现中缀表达式计算
5.1 策略
- 需要两个栈
- 数字栈
- 符号栈
- 需要三个方法
- 判断是否为符号
- 判断符号优先级
- 进行计算
- 如果是数字，直接入数栈
- 如果是符号，那么看优先级
- 如果是*或者/，那么直接进行计算，取出char[]中下一个数，以及numStack中的栈顶元素，计算结果放入数字栈中；
- 如果是+或者-，那么直接入符号栈；
char[]遍历结束后，依次弹出一个符号栈signStack和两个数字栈中的数进行计算，结果放入数字站numStack，执行次数是此时符号栈中元素个数
5.2 实现
```java /**
用于栈实现字符串计算器的工具类 */ public class Calculator {
public static void main(String[] args) {
char ch = '*';int i = ch;char c = (char) i;System.out.println("c = " + c);
}
public int calculator(String str) throws Exception {
// 符号栈 ArrayStack signStack = new ArrayStack(20); // 数字栈 ArrayStack numStack = new ArrayStack(20); // str转换为char数组 char[] chars = str.toCharArray(); // 指向char数组的指针 int index = 0; char ch; int m; int n; StringBuilder sb; for (;index< chars.length;index++){ sb = new StringBuilder(); ch = chars[index]; // 如果是数字, 直接入数栈 if (!isSign(ch)){ // char转化为int是直接转换为ASCII对应的十进制位置 // 0在ASCII表中位置是48
// numStack.push(ch-48);// 那么0~9存进去对应的也是0~9 sb.append(ch-48); while(index+1<chars.length&&!isSign(chars[index+1])){ index++; // numStack.push(chars[index]-48); sb.append(chars[index]-48); } numStack.push(Integer.parseInt(sb.toString())); }else { // if (){ // signStack.push(ch); // }else if (signStack.isEmpty()){ if (ch==’*’||ch==’/‘){
m = numStack.pop();
sb = new StringBuilder();
sb.append(chars[++index]-48);
while(index+1< chars.length && !isSign(chars[index+1])){
sb.append(chars[++index]-48);
}
n = Integer.parseInt(sb.toString());
numStack.push(cal(m,n,ch));
}else {
signStack.push(ch);
}
}else {
if (isPriorityTo(ch, (char) signStack.peek())){
m = numStack.pop();
sb = new StringBuilder();
sb.append(chars[++index]-48);
while(index+1< chars.length && !isSign(chars[index+1])){
sb.append(chars[++index]-48);
}
n = Integer.parseInt(sb.toString());
numStack.push(cal(m,n,ch));
}else {
signStack.push(ch);
}
}
}
}
if (!signStack.isEmpty()){
int size = signStack.size();
int res = 0;
for (int i=0;i<size;i++){
ch = (char) signStack.pop();
n = numStack.pop();
m = numStack.pop();
numStack.push(cal(m,n,ch));
}
}
return numStack.pop();
}
/**
* 方法:
* 1. 判断是符号还是数字
* 2. 比较两个符号的优先级
* 3. 进行计算
*/
/**
* 1. 判断是符号还是数字
* true 表示为符号
* false 表示为数子
*/
public boolean isSign(char ch){
if (ch=='*'||ch=='/'||ch=='+'||ch=='-') return true;
return false;
}
/**
* 2. 比较两个符号的优先级
* 如果m优先级大于等于n,则返回true
*/
public boolean isPriorityTo(char m,char n){
if (m=='*' || m=='/') return true;
else return false;
// if (n==’+’ || n==’-‘) return true; // else return false; }
/**
* 3. 进行计算
* 处理的是 m @ n
*/
public int cal(int m,int n,char ch) throws Exception {
if (!isSign(ch)){
throw new Exception("符号位输入错误,无法进行计算!");
}
int res;
switch (ch){
case '*':
return m*n;
case '/':
return m/n;
case '+':
return m+n;
case '-':
return m-n;
default:
return Integer.MIN_VALUE;
}
}
}
<a name="r5Nrj"></a>
## 6. 逆波兰计算器
<a name="YwCvR"></a>
### 6.1 计算策略
- 这里以字符串输入为前提，当然这里也会转为char[]
- new一个栈，用于存放数字
- 当指针扫描char[]扫描到：
- 数字，直接入栈
- 字符，pop出栈中两个数，进行计算，注意这里先出栈的被操作数（m*n）中的n，后者是操作数m
- 计算完成后压入栈
- 结束char[]的扫描，最后栈中只有一个元素，该元素就是最后结果
```java
// 使用到了直接写好的Stack的实现以及Calculator计算器
public int polandNotation(String str) throws Exception {
// 将字符串计算表达式转化为char[]
char[] chars = str.toCharArray();
int index = 0; // 指针index进行chars的扫描
ArrayStack stack = new ArrayStack(20); // 用于装载数字
Calculator calObj = new Calculator();
StringBuilder sb = new StringBuilder();
int m,n;
int res;
for (;index<chars.length;index++){
char ch = chars[index];
sb.append(ch-48);
if (!calObj.isSign(ch)){
// while(index+1<chars.length && !calObj.isSign(chars[index+1])){
// sb.append(chars[++index]-48);
// }
// stack.push(Integer.parseInt(sb.toString()));
stack.push(ch-48);
}else {
n = stack.pop();
m = stack.pop();
stack.push(calObj.cal(m,n,ch));
}
}
return stack.pop();
}
若有收获，就点个赞吧
0 人点赞
