栈
数组模拟栈实现
思路分析
-
栈(stack)是一个后进先出的有序列表。
-
栈是限制线性表中元素的插入和删除操作只能在线性表的同一端进行的特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶；另一端为固定的一端，称为栈底。
-
常用方法：
pop出栈，先判断isEmpty，return arr[top--]先返回数据，后将top指针向下移动。push入栈，先判断isFull是否已满，若无，再arr[++top]，先指向下一个位置，再入栈。isFull判断是否为空，top == -1isEmpty判断是否已满，top == maxSize-1
-
应用场景：
- 子程序的调用：在跳往子程序前，先将下个指令的地址存到堆栈中，等子程序执行完了，再将地址取出，继续执行源程序。
- 递归调用：和子程序的调用类似，不过除了存储下一个指令的地址外，还将参数、区域变量等数据存入堆栈。
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
- 二叉树的遍历。
- 图的深度优先搜索法。
代码实现
ArrayStack
后续的栈实现简易计算器也基于下方代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| package com.yukinoshita.dataStructure.stack;
public class ArrayStack {
private int maxSize;
private int[] arr;
private int top = -1;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
arr = new int[this.maxSize];
}
public boolean isFull(){
return top == maxSize - 1;
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
public int pop(){
if(isEmpty()){
throw new RuntimeException("Stack is empty，无法出栈");
}
return arr[top--];
}
public void push(int data){
if(isFull()){
throw new RuntimeException("Stack is full，无法入栈");
}
arr[++top] = data;
}
public int top(){
if(isEmpty()){
throw new RuntimeException("Stack is empty，无法获取栈顶元素");
}
return arr[top];
}
public void traverse(){
if(isEmpty()){
System.out.println("栈为空");
}else{
for(int i=top;i>=0;i--){
System.out.printf("栈arr[%d]=%d \n", i, arr[i]);
}
}
}
}
|
ArrayStackDemo
就不写一个简易的用户界面了（与前类似）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| package com.yukinoshita.dataStructure.stack;
public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(5);
try {
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
stack.push(9);
stack.traverse();
System.out.println("出栈："+stack.pop());
stack.pop();
stack.pop();
System.out.println("栈顶元素为："+stack.top());
stack.traverse();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
|
栈实现简易计算器
思路分析
例如要使用栈完成$2 * 50 - 2 + 8 \div 2 = ?$ $2+3*4 - 1$
使用中缀表达式[^1]
数字可能不仅仅是个位，运算符号包括加+减-乘*除/，其他符号包括小括号、等号。（这一版代码先不考虑实现小括号）
- 使用一个索引
index来遍历表达式
- 使用一个数栈
numStack和一个符号栈opStack分别存放数字和运算符
- 使用一个
isNum记录上一个输入的元素
- 可用作判断输入数字是否为多位数，也可用作判断表达式输入是否有误(比如$1 + - 2$)
- 当index遍历时，遇到：
- 数字。
- 判断上一个入栈的元素，若也为数字，则说明是个多位数；
- 若上个入栈的不是数字，则直接入栈。
- 运算符。
- 如果符号栈为空，直接入栈
- 只要符号栈不为空，判断当前读取的符号和栈内符号的优先级。若当前符号的优先级小于等于栈内符号，则从数栈中不断出栈两个数字、符号栈中出栈一个符号进行运算，将结果入数栈；若当前符号优先级大于栈内符号，则继续入栈。
- 小括号。
- 若为左括号，则直接入符号栈；
- 若为右括号，判断栈顶符号——栈顶若为左括号，则说明当前表达式输入有误，若不是，则继续出栈，继续进行出栈时的符号判断，直至将左括号出栈，最后将运算结果入数栈。（小括号就相当于一个弱化版的等号，只是将括号范围内做运算）
- 等号。每次从数栈取两个、符号栈取一个出栈，得到最终计算结果。
基于数组模拟栈实现所使用的ArraryStack类（由于这个栈内存储元素仅为int类型，为了建立int与char类型符号的关联，还增加了一个枚举类）
CV前请注意文件目录结构
代码实现
Calculator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| package com.yukino.caculator;
public class Calculator {
ArrayStack numStack = new ArrayStack(100);
ArrayStack opStack = new ArrayStack(100);
boolean isNum;
boolean endCalculate = false;
boolean hasNoneUseChar = false;
public int caculate(String input) {
for (int i = 0; i < input.length(); i++) {
char ch = input.charAt(i);
if(String.valueOf(ch).matches("\\d")){
pushNum(ch);
}else{
pushOp(ch);
}
}
if(endCalculate){
if(hasNoneUseChar){
System.out.println("输入了无关符号,仅支持0-9以及+-*/=,运算时已忽略无关符号");
}
return numStack.pop();
}else{
throw new RuntimeException("计算出错,是否是遗漏了'='?");
}
}
public void pushNum(char number) {
int num = Integer.parseInt(String.valueOf(number));
if(!isNum) {
numStack.push(num);
}else{
int temp_num = numStack.pop();
numStack.push(temp_num*10+num);
}
isNum = true;
}
public void pushOp(char operator){
boolean isOtherChar = false;
switch(operator) {
case '+'->{
while(opStack.size()>0) {
operate();
}
opStack.push(OperateEnum.PLUS.getCode());
}
case '-'->{
while(opStack.size()>0) {
operate();
}
opStack.push(OperateEnum.MINUS.getCode());
}
case '*'->{
if(opStack.isEmpty()) {
opStack.push(OperateEnum.TIMES.getCode());
}else{
while(!opStack.isEmpty() && (opStack.top()==3 || opStack.top()==4)) {
operate();
}
opStack.push(OperateEnum.TIMES.getCode());
}
}
case '/'->{
if(opStack.isEmpty()) {
opStack.push(OperateEnum.DIVIDE.getCode());
}else{
while(!opStack.isEmpty() && (opStack.top()==3 || opStack.top()==4)){
operate();
}
opStack.push(OperateEnum.DIVIDE.getCode());
}
}
case '='->{
while(opStack.size()>0){
operate();
}
endCalculate = true;
}
default -> {
this.hasNoneUseChar = true;
isOtherChar = true;
}
}
if(!isOtherChar){
isNum = false;
}
}
public void operate(){
int num2 = numStack.pop();
int num1 = numStack.pop();
int op = opStack.pop();
switch(op) {
case 1->{
numStack.push(num1+num2);
}
case 2->{
numStack.push(num1-num2);
}
case 3->{
numStack.push(num1*num2);
}
case 4->{
if(num2==0){
throw new ArithmeticException("被除数不能为0");
}
numStack.push(num1/num2);
}
}
}
}
|
OperateEnum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| package com.yukino.caculator;
public enum OperateEnum {
PLUS(1),
MINUS(2),
TIMES(3),
DIVIDE(4);
private final int code;
OperateEnum(int code) {
this.code = code;
}
public int getCode() {
return code;
}
}
|
TestCalculator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| package com.yukino.caculator;
public class TestCalculator {
public static void main(String[] args) {
Calculator calculator = new Calculator();
String input = "1+1 0 )({}= ";
try{
int res = calculator.caculate(input);
System.out.printf("计算结果为：%d", res);
}catch(Exception e){
System.out.println(e.getMessage());
}
}
}
|
后期留言：一点都不是“简易”计算器，实现过程会有很多小错误……Debug了很久
逆波兰计算器(经典)
思路分析
中缀表达式转后缀表达式
思路步骤分析：
- 初始化两个栈运算符栈
s1和存储中间结果栈s2
- 从左到右扫描中缀表达式[^1]
- 遇到操作数时，将其压入
s2
- 遇到运算符时，比较其与
s1栈顶运算符的优先级：
- 如果
s1为空，或栈顶元素为(，则直接将该运算符入栈
- 否则，若优先级比栈顶元素高，也将该符号压入
s1
- 否则，将
s1栈顶的运算符弹出压入s2中，再次转到4.1.与s1中新的栈顶元素比较
- 遇到括号时：
- 如果是左括号
(，则直接压入s1
- 如果是右括号
)，则依次弹出s1中运算符并压入s2，直到遇到左括号)为止，此时就将这一对括号丢弃
- 重复2.—5.步骤，直到表达式最右边
- 将
s1中剩余的符号弹出压入s2
- 依次弹出
s2中元素并输出，结果的逆序即为中缀表达式所对应的后缀表达式
s2可用队列优化（省去了取逆序）
代码实现均在PolandNotation中
利用后缀表达式计算
要求：
- 输入一个后缀表达式[^1]（逆波兰表达式），利用栈（Stack）计算结果
- 支持小括号和多位整数
代码实现
PolandNotation
输入后缀表达式，计算结果
计算很简单：遍历表达式(存到ArrayList中) 遇到数就入栈 遇到符号就取出两个数、计算、结果入栈 最后栈中剩余的就是结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| package com.yukinoshita.dataStructure.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
String suffixExpression = "3 4 + 5 * 6 - ";
List<String> rpnList = getListString(suffixExpression);
System.out.printf("计算结果为：%d", calculate(rpnList));
}
public static List<String> getListString(String suffixExpression){
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<>();
for(String ele: split){
list.add(ele);
}
return list;
}
public static int calculate(List<String> rpnList){
Stack<String> stack = new Stack<String>();
for(String item:rpnList){
if(item.matches("\\d+")){
stack.push(item);
}else{
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if(item.equals("+")){
res = num1 + num2;
}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("运算法有问题");
}
stack.push(Integer.toString(res));
}
}
return Integer.parseInt(stack.pop());
}
}
|
