栈模拟计算器
栈模拟计算器
背景
-
数据结构——栈
-
博主以b站尚硅谷Java数据结构与算法课进行学习
思路
-
定义两个栈，一个为数栈numStack，用于存放数，一个为符号栈operStack，用于存放运算符
-
设置索引index遍历表达式
-
index指数，则直接入数栈
-
index扫描为运算符，则分不同情况
- 符号栈为空，直接入栈
- 符号栈不为空，就进行比较
- 当前运算符的优先级小于或等于栈中的运算符，就从数栈中取出两个数和从符号栈中取出一个符号进行运算，将结果入数栈，再将当前的运算符入符号栈
- 当前运算符的优先级大于栈中的运算符，直接入符号栈
-
当整个表达式扫描完毕，就可以按顺序pop出数字和符号进行运算了
-
数栈的最后一个数就是结果
实现步骤
-
代码实现
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
182public class Calculator {
public static void main(String[] args) {
String expression = "8-2*3+1";
//创建两个栈，一个数栈，一个符号栈
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
//定义相关变量
int index = 0;//用于扫描
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' ';//将每次扫描得到char保存到ch
String keepNum = " ";//变量，用于拼接多位数
//开始while扫描expression
while(true){
//依次得到expression的每一个字符
ch = expression.substring(index,index+1).charAt(0);//substring用法
//判断ch是什么做相应处理
if (operStack.isOper(ch)){//如果是运算符
//判断当前符号栈是否为空
if(!operStack.isEmpty()){
//如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或等于栈中的操作符，就需要重数栈中取出两数
//从符号栈中取出一个符号进行运算，将运算结果入数栈，将当前操作符入符号栈
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{
//如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
operStack.push(ch);
}
}else{
//如果为空直接入栈
operStack.push(ch);
}
}else{
//如果是数直接入数栈
// numStack.push(ch-48);//在表中‘1’是49
//思路分析
//1.当处理多位数时，不能发现一个数就入栈
//2.在处理数时，需要向expression的表达式的index后看一位，如果是数就进行扫描，是符号就入栈
//3.需要 定义一个变量字符串用于拼接
//处理多位数
keepNum += ch;
//如果ch已经是最后一位就直接入栈
if (index == expression.length()-1){
numStack.push(Integer.parseInt(keepNum.trim()));
}else{
//判断下个字符是是不是数字，如果是数字就继续扫描，是符号就入栈
//注意是看后一位，不是index++
if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))){
//是的话，后面一位是符号，入栈
numStack.push(Integer.parseInt(keepNum.trim()));
//重要：keepNum清空
keepNum = " ";
}
}
}
//让index+1，判断是否扫描到expression最后
index++;
if (index>= expression.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(expression+"="+numStack.pop());
}
}
//先创建一个栈，需要扩展功能
class ArrayStack2{
private int maxSize;//栈的大小
private int[] stack;//数组模拟栈，数据放在该数组
private int top = -1;//top表示栈顶，初始化为-1
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
//增加一个方法，可以返回当前栈顶的值,但不是取出
public int peek(){
return stack[top];
}
//栈满
public boolean isFull(){
return top == maxSize -1;
}
//栈空
public boolean isEmpty(){
return top == -1;
}
//入栈push
public void push(int value){
//判断栈是否满
if(isFull()){
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}
//出栈pop，将栈顶数据返回
public int pop(){
//先判断栈是否空
if(isEmpty()){
//抛出异常
throw new RuntimeException("栈空");
}
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]==%d\n",i,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; //res用于存放结果
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;
}
}