本文先给出思路与方法，最后将给出完整代码：
算法综述：
一、中缀表达式转后缀表达式：
1.中缀表达式要转后缀表达式，首先需要两个stack（栈），其中一个应用于存放字符，另一个用于存放数字。
2.读到数字直接存入数字栈中，读到字符时，要咸鱼栈内前一元素（字符）进行比较，当当前（要存入的字符）优先级大于迁移字符时才存入，否则（>=）要仿佛将栈内元素弹出，并依次存入数字栈中。
提示：‘（' 的优先级默认比所有字符都小。所有字符都可以存在它后面；同时夜笔所有字符都大，可以存在所有字符后面
3.遇到 ‘）'时将栈内所有字符依次弹出，并存入数字栈中，知道遇到 ‘（' 为止
4.当所有字符、数字访问完毕时，栈内很可能还会有剩余的字符，这是将他们一次弹出，并纯如数字栈中
小技巧：
1.存放‘+'，‘-'时，如果只有当前一个数位空或者‘（' 时才进行存入操作，否则均弹出。
2.存放 ‘*'，‘/' 时，只有当前一个数位 ‘*'，‘/' 时才弹出其他情况下，均存入。
附上代码：
|
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
|
/** 中缀转后缀*/public void topostfix() {// todo auto-generated method stubint sum = 0 ;//用于记入”（）“总个数int j = 0 ;//用于读到”）“时循环出栈string outstack = null;charnum.push(null);for( int i = 0 ; i < calculatelength ; i ++){if ( calculate[i].equals("(")) {charnum.push(calculate[i]);sum ++ ;}else if ( calculate[i].equals(")") ) {outstack = charnum.pop();//进入前先出一个while ( !outstack.equals("(") ){num.push(outstack);outstack = charnum.pop();}//最后一次outstack正好接到”（“不入栈sum ++ ;}else if (calculate[i].equals("*")) {outstack = charnum.pop();charnum.push(outstack);while( ( outstack == "*" || outstack == "/" ) && !(outstack == null) ){num.push(outstack);charnum.pop();//由于前第三行又将outstack存入栈中，座椅此处再次弹出outstack = charnum.pop();charnum.push(outstack);}charnum.push("*");}else if (calculate[i].equals("/")) {outstack = charnum.pop();charnum.push(outstack);while( ( outstack == "*" || outstack == "/" ) && !(outstack == null) ){num.push(outstack);charnum.pop();//由于前第三行又将outstack存入栈中，座椅此处再次弹出outstack = charnum.pop();charnum.push(outstack);}charnum.push("/");}else if (calculate[i].equals("+")) {outstack = charnum.pop();charnum.push(outstack);while( !(outstack=="(") && !(outstack == null) ){num.push(outstack);charnum.pop();outstack = charnum.pop();charnum.push(outstack);}charnum.push("+");}else if (calculate[i].equals("-")) {outstack = charnum.pop();charnum.push(outstack);while( !(outstack=="(") && !(outstack == null) ){num.push(outstack);charnum.pop();outstack = charnum.pop();charnum.push(outstack);}charnum.push("-");}else {num.push(calculate[i]);}}outstack = charnum.pop();while ( outstack != null ) {num.push(outstack);outstack = charnum.pop();}calculatelength = calculatelength - sum ;stack<string> zanshi = new stack<>();for(int i = 0 ; i < calculatelength ; i ++ ){zanshi.push(num.pop());}calculatetozero();for(int i = 0 ; i < calculatelength ;i ++ ){calculate[i] = zanshi.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
|
/* * 后缀表达式求值 */ public string postfix() { int a = 0 , b = 0;//栈中弹出的两数 int sum ;//求两数运算 for (int i = 0; i < calculatelength ; i++ ) { if (i == 0) { num.push(calculate[i]); }else if (calculate[i].equals("+") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a + b ; num.push(string.valueof(sum)); }else if (calculate[i].equals("-") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a - b ; num.push(string.valueof(sum)); }else if (calculate[i].equals("*") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a * b ; num.push(string.valueof(sum)); }else if (calculate[i].equals("/") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a / b ; num.push(string.valueof(sum)); }else if (calculate[i].equals("%") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a / b ; num.push(string.valueof(sum)); }else { num.push(calculate[i]); } } return num.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
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
234
235
236
237
238
239
240
241
242
|
public class text { stack<string> num = new stack<>(); //后缀用栈 中转后数字栈 stack<string> charnum = new stack<>();//中转后字符栈 string []calculate = new string[1000];//存字符串数组 int calculatelength = 0 ;//字符串数组长度 public text() { // todo auto-generated constructor stub } //转字符串数组 public void tostringarray(string input) { char chararray[] = input.tochararray(); int number = 0;//用于导入多位数 int j = 0 ;//用于计入当前字符串数组的位数 system.out.println(chararray.length); for(int i = 0 ; i < chararray.length ; i++){ if(chararray[i] == '('){ calculate[j++] = "("; }else if(chararray[i] == ')'){ calculate[j++] = ")"; }else if (chararray[i] == '+') { calculate[j++] = "+"; }else if (chararray[i] == '-') { calculate[j++] = "-"; }else if (chararray[i] == '*') { calculate[j++] = "*"; }else if (chararray[i] == '/') { calculate[j++] = "/"; }else if (chararray[i] == '%') { calculate[j++] = "%"; }else if (chararray[i] == '#') { calculate[j++] = "#"; }else { string str=string.valueof(chararray[i]); number = number * 10 + integer.parseint(str);system.out.println("123"); if( (i + 1) == chararray.length || chararray[i+1] < '0' || chararray[i+1] > '9'){ if ( (i + 1) != chararray.length && chararray[i+1] == ' ') { system.out.println("456");i++; } calculate[j++] = string.valueof(number); system.out.println(number); number = 0 ; } } system.out.println("---z->" + calculate[i]); } calculatelength = j-- ;//不--会将‘#'存入 } public void outputcalculate() { for(int i = 0 ; i < calculatelength ; i ++ ){ system.out.println(calculate[i]); } } public void calculatetozero() { for(int i = 0 ; i < calculatelength ; i ++ ){ calculate[i]= calculate[999] ; } } //中缀转后缀 public void topostfix() { // todo auto-generated method stub system.out.println("789"); int sum = 0 ;//用于记入”（）“总个数 int j = 0 ;//用于读到”）“时循环出栈 string outstack = null; charnum.push(null); system.out.println(calculatelength); for( int i = 0 ; i < calculatelength ; i ++){ system.out.println(calculate[i]);//----------------------------- if ( calculate[i].equals("(")) { charnum.push(calculate[i]); system.out.println("1-1 charpush " + calculate[i]);//----------------------------- sum ++ ; }else if ( calculate[i].equals(")") ) { system.out.println("2-1 charpush " + calculate[i]);//----------------------------- outstack = charnum.pop();//进入前先出一个 system.out.println("2-1 charpush " + outstack);//----------------------------- while ( !outstack.equals("(") ){ system.out.println("2-2 charpush " + outstack);//----------------------------- num.push(outstack); outstack = charnum.pop(); }//最后一次outstack正好接到”（“不入栈 system.out.println("qiangxing 1 = " + outstack );// outstack = charnum.pop(); system.out.println("qiangxing 2 = " + outstack ); sum ++ ; }else if (calculate[i].equals("*")) { outstack = charnum.pop(); charnum.push(outstack); system.out.println("3-2 charpush " + outstack);//----------------------------- while( ( outstack == "*" || outstack == "/" ) && !(outstack == null) ){ system.out.println("3-1 charpush " + outstack);//----------------------------- num.push(outstack); charnum.pop();//由于前第三行又将outstack存入栈中，座椅此处再次弹出 outstack = charnum.pop(); charnum.push(outstack); } system.out.println("3-3 charpush " + outstack);//----------------------------- charnum.push("*"); }else if (calculate[i].equals("/")) { system.out.println("5-1-0 charpush " + "1-1-1-1-1-1-1-1");//----------------------------- outstack = charnum.pop(); system.out.println("5-1-1 charpush " + "2-2-2-2-2-2-22-2");//----------------------------- charnum.push(outstack); system.out.println("4-1 charpush " + outstack);//----------------------------- while( ( outstack == "*" || outstack == "/" ) && !(outstack == null) ){ system.out.println("4-2 charpush " + outstack);//----------------------------- num.push(outstack); charnum.pop();//由于前第三行又将outstack存入栈中，座椅此处再次弹出 outstack = charnum.pop(); charnum.push(outstack); } system.out.println("4-3 charpush " + outstack);//----------------------------- system.out.println("5-1-2 charpush " + outstack);//----------------------------- charnum.push("/"); }else if (calculate[i].equals("+")) { outstack = charnum.pop(); charnum.push(outstack); system.out.println("5-1 charpush " + outstack);//----------------------------- while( !(outstack=="(") && !(outstack == null) ){ system.out.println("5-2 charpush " + outstack);//----------------------------- num.push(outstack); charnum.pop(); outstack = charnum.pop(); charnum.push(outstack); } system.out.println("5-3 charpush " + outstack);//----------------------------- charnum.push("+"); }else if (calculate[i].equals("-")) { outstack = charnum.pop(); charnum.push(outstack); system.out.println("6-1 charpush " + outstack);//----------------------------- while( !(outstack=="(") && !(outstack == null) ){ system.out.println("6-2 charpush " + outstack);//----------------------------- num.push(outstack); charnum.pop(); outstack = charnum.pop(); charnum.push(outstack); } system.out.println("6-3 charpush " + outstack);//----------------------------- charnum.push("-"); }else { system.out.println("7-7 " + calculate[i]); num.push(calculate[i]); } } system.out.println("匹配结束" + outstack); outstack = charnum.pop(); system.out.println("finish 1 == " + outstack); while ( outstack != null ) { num.push(outstack); outstack = charnum.pop(); system.out.println("finish 2 == " + outstack); } calculatelength = calculatelength - sum ; system.out.println( "0.0.0.0 charpush " );//----------------------------- system.out.println("sum = " + sum + " calculate = " + calculatelength + "calculatelength-sum = " + (calculatelength-sum)); system.out.println("over ~~~~~0 "); stack<string> zanshi = new stack<>();// num.pop(); for(int i = 0 ; i < calculatelength ; i ++ ){ zanshi.push(num.pop());// system.out.println(num.pop()); } calculatetozero(); system.out.println("over ~~~~~1 "); for(int i = 0 ; i < calculatelength ;i ++ ){ calculate[i] = zanshi.pop(); } system.out.println("over ~~~~~2 "); for(int i = 0 ; i < calculatelength ;i ++ ){ system.out.println(calculate[i]); } system.out.println("over ~~~~~3 ");// num.push("#"); } //后缀计算 public string postfix() { int a = 0 , b = 0;//栈中弹出的两数 int sum ;//求两数运算 for (int i = 0; i < calculatelength ; i++ ) {// system.out.println("目前符号：" + calculate[i]); if (i == 0) { num.push(calculate[i]); }else if (calculate[i].equals("+") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a + b ; num.push(string.valueof(sum)); }else if (calculate[i].equals("-") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a - b ; num.push(string.valueof(sum)); }else if (calculate[i].equals("*") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a * b ; num.push(string.valueof(sum)); }else if (calculate[i].equals("/") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a / b ; num.push(string.valueof(sum)); }else if (calculate[i].equals("%") ) { b = integer.parseint(num.pop()); a = integer.parseint(num.pop()); sum = a / b ; num.push(string.valueof(sum)); }else { num.push(calculate[i]); } } return num.pop(); }} |
结果如下：
一、前缀转后缀并输出
其中over前为转化后的后缀表达式
over后为计算结果
|
1
2
3
4
5
6
7
8
9
|
public class main { public static void main(string[] args) { text text = new text(); text.tostringarray("1+2*(3-1+2)-3"); text.outputcalculate(); text.topostfix(); system.out.println(text.postfix()); }} |
二、后缀直接输出
注意后缀表达式时
为了实现多位数运算，连续输入一串数时 ，输入完一个数加空格
如：要计算："1+2*(3-1+2)-3" 则输入："1 2 3 1-2+*+3-"
例：
|
1
2
3
4
5
6
7
8
|
public class main { public static void main(string[] args) { text text = new text(); text.tostringarray("1 2 3 1-2+*+3-"); text.outputcalculate(); system.out.println(text.postfix()); }} |
输出结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/qq_43377749/article/details/84483862
