数据结构学习（四）----------栈的应用案例_符号数栈例题

作者：weixin_40725706 | 2024-07-23 08:24:48

踩

符号数栈例题

运用栈实现计算一个表达式

第一次

思路：
1.需要创建两个栈，一个存放数字的栈numStack，一个存放运算符的栈operStack
2.需要一个下标index帮助遍历获取str中的符号
3.获取到数字，将数字放到数字栈中
4.获取到运算符，判断符号栈中是否为空，为空则直接放到符号栈中
5.符号栈中不为空，判断获取到的符号与符号栈中top指向的符号的优先级，
5.1如果获取的操作符的优先级小于符号栈中的优先级，从数字栈中取出两个数字与符号栈中
的操作符进行运算，将运算结果得到的数放入数字栈，将获取到的操作符放到符号栈（
此处相当于将获取的符号与符号栈中top指向的符号替换了）
5.2如果获取的操作符的优先级大于符号栈中的优先级，直接将获取到的符号存入符号栈
6.扫描完毕后将数字栈中的数字和符号栈中的符号按顺序取出进行运算
7.当数字栈中只有一个数字时，这个数字就是最终的运算结果

代码实现

package com.tmo.stack;
/**
 * 
 * @author tmo
 * 	思路：
 * 	1.需要创建两个栈，一个存放数字的栈numStack，一个存放运算符的栈operStack
 * 	2.需要一个下标index帮助遍历获取str中的符号
 * 	3.获取到数字，将数字放到数字栈中
 * 	4.获取到运算符，判断符号栈中是否为空，为空则直接放到符号栈中
 * 	5.符号栈中不为空，判断获取到的符号与符号栈中top指向的符号的优先级，
 * 		5.1如果获取的操作符的优先级小于符号栈中的优先级，从数字栈中取出两个数字与符号栈中
 * 	的操作符进行运算，将运算结果得到的数放入数字栈，将获取到的操作符放到符号栈（
 * 	此处相当于将获取的符号与符号栈中top指向的符号替换了）
 * 		5.2如果获取的操作符的优先级大于符号栈中的优先级，直接将获取到的符号存入符号栈
 * 	6.扫描完毕后将数字栈中的数字和符号栈中的符号按顺序取出进行运算
 * 	7.当数字栈中只有一个数字时，这个数字就是最终的运算结果
 */
public class Calculator {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str = "5+2*6-4";
		//测试
		ArrayStack2 numStack = new ArrayStack2(10);
		ArrayStack2 operStack = new ArrayStack2(10);
		
		//定义需要的变量
		int index = 0;//辅助扫描的位置
		int num1 = 0; //运算数字1
		int num2 = 0; //运算数字2
		int oper = 0; // 保存操作符
		int res = 0; //保存运算结果
		char ch = ' '; //保存扫描到的结果
		
		while (true) {
			//扫描
			ch = str.substring(index, index+1).charAt(0);
			if (operStack.isOper(ch)) {
				//是运算符
				//判断符号栈是否为空
				if (operStack.isEmpty()) {
					//符号栈为空
					operStack.push(ch);
				}else {
					//符号栈不为空
					//判断优先级
					if (operStack.priority(ch) <= operStack.priority(operStack.getTop())) {
						//符号栈中的优先级大于扫描到的运算符
						//从符号栈中取出运算符，从数字栈中取出两个数字进行计算
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = operStack.cal(num1, num2, oper);
						numStack.push(res);
						operStack.push(ch);
					}else {
						//符号栈中的优先级小于扫描到的运算符
						//直接存入符号栈
						operStack.push(ch);
					}
				}
			}else {
				//是数字
				numStack.push(ch - 48);
			}
			
			index++;
			if (index >= str.length()) {
				//扫描结束
				break;
			}
			
			
			
		}
		
		//当扫描结束，需要将剩余的内容进行运算
		while (true) {
			//判断是否运算结束
			if (operStack.isEmpty()) {
				//符号栈中为空 说明运算结束
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = operStack.cal(num1, num2, oper);
			numStack.push(res);
		}
		
		//计算结束后，数字栈中存放的就是最终的结果
		int res2 = numStack.pop();
		System.out.printf("%s的结果为%d",str,res2);
				
		

	}

}



//数组模拟栈
class ArrayStack2{
	//栈的最大长度
	public int maxSize;
	//栈
	public int[] stack;
	//表示栈顶元素 初始化为-1，表示栈空
	public 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 num) {
		//判断是否栈满
		if (isFull()) {
			System.out.println("栈满");
			return;
		}
		//入栈
		//top后移
		top++;
		stack[top] = num;
	}
	
	//出栈
	public int pop() {
		//判断是否栈空
		if (isEmpty()) {
			throw new RuntimeException("栈空");
		}
		int val = stack[top];
		top-- ;
		return val;
	}
	
	//遍历栈
	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 ch) {
		if (ch == '*' || ch == '/') {
			return 1;
		}else if (ch == '+' || ch =='-') {
			return 0;
		}else {
			return -1;
		}
	}
	
	//判断是否为操作符
	public boolean isOper(int ch) {
		return ch == '*' || ch == '/' || ch == '+' || ch == '-';
	}
	
	//运算
	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;
	}
	
	//获取top的数
	public int getTop() {
		return stack[top];
	}
	
}
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

问题：

当运行 5+2*6-4 时，结果为13 正确；当运行 50 + 2 X 6 - 4 时，结果不正确，只能计算一个字符的结果，当计算多位字符的结果时，结果不正确。

因为我们在扫描到一个字符时，直接存入了数字栈。

解决：

扫描到一个数字时，判断下一个是不是数字，如果是数字，将其取出并进行拼接

然后将拼接的数字入数字栈

package com.tmo.stack;
/**
 * 
 * @author tmo
 * 	思路：
 * 	1.需要创建两个栈，一个存放数字的栈numStack，一个存放运算符的栈operStack
 * 	2.需要一个下标index帮助遍历获取str中的符号
 * 	3.获取到数字，将数字放到数字栈中
 * 	4.获取到运算符，判断符号栈中是否为空，为空则直接放到符号栈中
 * 	5.符号栈中不为空，判断获取到的符号与符号栈中top指向的符号的优先级，
 * 		5.1如果获取的操作符的优先级小于符号栈中的优先级，从数字栈中取出两个数字与符号栈中
 * 	的操作符进行运算，将运算结果得到的数放入数字栈，将获取到的操作符放到符号栈（
 * 	此处相当于将获取的符号与符号栈中top指向的符号替换了）
 * 		5.2如果获取的操作符的优先级大于符号栈中的优先级，直接将获取到的符号存入符号栈
 * 	6.扫描完毕后将数字栈中的数字和符号栈中的符号按顺序取出进行运算
 * 	7.当数字栈中只有一个数字时，这个数字就是最终的运算结果
 */
public class Calculator {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str = "50+2*6-4";
		//测试
		ArrayStack2 numStack = new ArrayStack2(10);
		ArrayStack2 operStack = new ArrayStack2(10);
		
		//定义需要的变量
		int index = 0;//辅助扫描的位置
		int num1 = 0; //运算数字1
		int num2 = 0; //运算数字2
		int oper = 0; // 保存操作符
		int res = 0; //保存运算结果
		char ch = ' '; //保存扫描到的结果
		String keepNum = ""; //保存拼接后的数字
		while (true) {
			//扫描
			ch = str.substring(index, index+1).charAt(0);
			if (operStack.isOper(ch)) {
				//是运算符
				//判断符号栈是否为空
				if (operStack.isEmpty()) {
					//符号栈为空
					operStack.push(ch);
				}else {
					//符号栈不为空
					//判断优先级
					if (operStack.priority(ch) <= operStack.priority(operStack.getTop())) {
						//符号栈中的优先级大于扫描到的运算符
						//从符号栈中取出运算符，从数字栈中取出两个数字进行计算
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = operStack.cal(num1, num2, oper);
						numStack.push(res);
						operStack.push(ch);
					}else {
						//符号栈中的优先级小于扫描到的运算符
						//直接存入符号栈
						operStack.push(ch);
					}
				}
			}else {
				//是数字
				//numStack.push(ch - 48);
				
				//拼接
				keepNum += ch;
				
				//判断是否是最后一个字符
				if (index == str.length() -1) {
					numStack.push(Integer.parseInt(keepNum));
				}else {
					//判断下一位是否是数字
					if (operStack.isOper(str.substring(index+1, index+2).charAt(0))) {
						//不是数字
						numStack.push(Integer.parseInt(keepNum));
						//注意：运算完后要将keepNum设为空
						keepNum = "";
					}
					
				}
				
				
				
				
				
			}
			
			index++;
			if (index >= str.length()) {
				//扫描结束
				break;
			}
			
			
			
		}
		
		//当扫描结束，需要将剩余的内容进行运算
		while (true) {
			//判断是否运算结束
			if (operStack.isEmpty()) {
				//符号栈中为空 说明运算结束
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = operStack.cal(num1, num2, oper);
			numStack.push(res);
		}
		
		//计算结束后，数字栈中存放的就是最终的结果
		int res2 = numStack.pop();
		System.out.printf("%s的结果为%d",str,res2);
				
		

	}

}



//数组模拟栈
class ArrayStack2{
	//栈的最大长度
	public int maxSize;
	//栈
	public int[] stack;
	//表示栈顶元素 初始化为-1，表示栈空
	public 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 num) {
		//判断是否栈满
		if (isFull()) {
			System.out.println("栈满");
			return;
		}
		//入栈
		//top后移
		top++;
		stack[top] = num;
	}
	
	//出栈
	public int pop() {
		//判断是否栈空
		if (isEmpty()) {
			throw new RuntimeException("栈空");
		}
		int val = stack[top];
		top-- ;
		return val;
	}
	
	//遍历栈
	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 ch) {
		if (ch == '*' || ch == '/') {
			return 1;
		}else if (ch == '+' || ch =='-') {
			return 0;
		}else {
			return -1;
		}
	}
	
	//判断是否为操作符
	public boolean isOper(int ch) {
		return ch == '*' || ch == '/' || ch == '+' || ch == '-';
	}
	
	//运算
	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;
	}
	
	//获取top的数
	public int getTop() {
		return stack[top];
	}
	
}
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/869015