算法基础07:栈及实现简单计算器

栈的实际需求

栈的介绍

应用场景

代码实现

快速入门

思路分析

代码

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
package com.algorithm.stack;

import java.util.Scanner;

/**
* TODO
*
* @author:XMD
* @date: 23.8.22
*/
public class ArrayStackDemo {

public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(5);
String key = "";
boolean loop = true;
Scanner scanner = new Scanner(System.in);

while (loop) {
key = scanner.next();
switch (key) {
case "show":
arrayStack.show();
break;
case "push":
System.out.println("输入");
int value = scanner.nextInt();
arrayStack.push(value);
break;
case "pop":
try {
int res = arrayStack.pop();
System.out.println("pop:" + res);
} catch (Exception e) {
e.printStackTrace();
}
break;
case "exit":
scanner.close();
loop = false;
break;
}

System.out.println("结束");
}
}

}

class ArrayStack {
//栈的大小
private int maxSize;
//数组,模拟栈,存放数据
private int[] stack;
//栈顶,默认-1
private int top = -1;

public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}

public boolean isFull() {
return top == maxSize - 1;
}

public boolean isEmpty() {
return top == -1;
}

public void push(int value) {
if (isFull()){
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}

public int pop() {
if (isEmpty()) throw new RuntimeException("栈空");

int value = stack[top];
top--;
return value;
}

public void show() {
if (isEmpty()) {
System.out.println("栈空");
}
for (int i = top; i >= 0; i--) {
System.out.println(stack[i]);
}
}
}

实现综合计算器

思路

代码实现

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
package com.algorithm.stack;

/**
* 栈实现综合计算器 (单位数的加减乘除)
*
* @author:XMD
* @date: 23.8.22
*/
public class Calculator {
public static void main(String[] args) {
String exp = "70+2*60-4";
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
//定义需要的变量

//用于扫描
int index = 0;
int num1;
int num2;
int oper;
int res;
//将每次扫描得到的char保存到ch
char ch = ' ';
String keepNum = "";
while (true) {
ch = exp.substring(index, index + 1).charAt(0);
//如果是运算法
if (operStack.isOper(ch)) {
//判断符号栈是否为空
if (operStack.isEmpty()) {
//直接入符合栈
operStack.push(ch);
} else {
//进行比较,如果当前操作符优先级小于等于女栈中的优先级,就需要从栈中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 {
//如果当前操作符的优先级大于栈中的操作符,就直接入符号栈
//为什么要减48,需要看ASCII表,十进制
operStack.push(ch);
}
}
} else {
//如果是数,直接入数栈
// numStack.push(ch - 48);
//思路分析
//1.当处理多为数是,不能发现是一个数就立即入栈,因为可能是多位数
//2.在处理数时。需要向exp的表达式的index后再看一位,如果是数就进行扫描,如果是符号就入栈
//3.因此需要定义一个变量字符串keepNum,用于拼接
keepNum += ch;

//如果ch是最后一位,就直接入栈
if (index == exp.length() -1){
numStack.push(Integer.parseInt(keepNum));
}else {
//判断下一个字符是不是数字,如果是数字就继续扫描,如果是运算符,就入栈
//注意只是看后一位,不是出栈
if (operStack.isOper(exp.substring(index+1,index+2).charAt(0))){
//如果后一位是运算符,就入栈
numStack.push(Integer.parseInt(keepNum));
//keepNum清空
keepNum = "";
}
}
}

//让index + 1 ,并判断是否扫描到exp最后
index++;
if (index >= exp.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);
}
System.out.println("结果是:" + numStack.pop());

}
}

class ArrayStack2 {
//栈的大小
private int maxSize;
//数组,模拟栈,存放数据
private int[] stack;
//栈顶,默认-1
private int top = -1;

public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}

public boolean isFull() {
return top == maxSize - 1;
}

public boolean isEmpty() {
return top == -1;
}

public void push(int value) {
if (isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}

public int pop() {
if (isEmpty()) throw new RuntimeException("栈空");

int value = stack[top];
top--;
return value;
}

//返回栈顶数据,不出栈
public int peek() {
if (isEmpty()) throw new RuntimeException("栈空");
return stack[top];
}

public void show() {
if (isEmpty()) {
System.out.println("栈空");
}
for (int i = top; i >= 0; i--) {
System.out.println(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;
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;
}
}


-------------本文结束感谢您的阅读-------------