本文先給出思路與方法，最后將給出完整代碼：
算法綜述：
一、中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式：
1.中綴表達(dá)式要轉(zhuǎn)后綴表達(dá)式，首先需要兩個(gè)stack（棧），其中一個(gè)應(yīng)用于存放字符，另一個(gè)用于存放數(shù)字。
2.讀到數(shù)字直接存入數(shù)字棧中，讀到字符時(shí)，要咸魚棧內(nèi)前一元素（字符）進(jìn)行比較，當(dāng)當(dāng)前（要存入的字符）優(yōu)先級(jí)大于遷移字符時(shí)才存入，否則（>=）要仿佛將棧內(nèi)元素彈出，并依次存入數(shù)字棧中。
提示：‘（' 的優(yōu)先級(jí)默認(rèn)比所有字符都小。所有字符都可以存在它后面；同時(shí)夜筆所有字符都大，可以存在所有字符后面
3.遇到 ‘）'時(shí)將棧內(nèi)所有字符依次彈出，并存入數(shù)字棧中，知道遇到 ‘（' 為止
4.當(dāng)所有字符、數(shù)字訪問(wèn)完畢時(shí)，棧內(nèi)很可能還會(huì)有剩余的字符，這是將他們一次彈出，并純?nèi)鐢?shù)字棧中
小技巧：
1.存放‘+'，‘-'時(shí)，如果只有當(dāng)前一個(gè)數(shù)位空或者‘（' 時(shí)才進(jìn)行存入操作，否則均彈出。
2.存放 ‘*'，‘/' 時(shí)，只有當(dāng)前一個(gè)數(shù)位 ‘*'，‘/' 時(shí)才彈出其他情況下，均存入。
附上代碼：
|
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
|
/** 中綴轉(zhuǎn)后綴*/public void topostfix() {// todo auto-generated method stubint sum = 0 ;//用于記入”（）“總個(gè)數(shù)int j = 0 ;//用于讀到”）“時(shí)循環(huán)出棧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();//進(jìn)入前先出一個(gè)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();}} |
二、后綴表達(dá)式計(jì)算
后綴表達(dá)式計(jì)算只遵循一個(gè)原則：
首先將表達(dá)式存在棧中
遇到符號(hào)時(shí)彈出兩個(gè)相應(yīng)的數(shù)字，進(jìn)行計(jì)算后再次 存入棧內(nèi)
最后棧內(nèi)身下的唯一一個(gè)數(shù)，就是所要求的結(jié)果
|
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
|
/* * 后綴表達(dá)式求值 */ public string postfix() { int a = 0 , b = 0;//棧中彈出的兩數(shù) int sum ;//求兩數(shù)運(yùn)算 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(); }} |
最后附上完整代碼
//注：代碼中有很多輸出 方便讀者實(shí)時(shí)查看運(yùn)算過(guò)程中 各內(nèi)容
// 這些輸出導(dǎo)致篇幅較長(zhǎng) 大家看明白后 刪去即可
|
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<>(); //后綴用棧 中轉(zhuǎn)后數(shù)字棧 stack<string> charnum = new stack<>();//中轉(zhuǎn)后字符棧 string []calculate = new string[1000];//存字符串?dāng)?shù)組 int calculatelength = 0 ;//字符串?dāng)?shù)組長(zhǎng)度 public text() { // todo auto-generated constructor stub } //轉(zhuǎn)字符串?dāng)?shù)組 public void tostringarray(string input) { char chararray[] = input.tochararray(); int number = 0;//用于導(dǎo)入多位數(shù) int j = 0 ;//用于計(jì)入當(dāng)前字符串?dāng)?shù)組的位數(shù) 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-- ;//不--會(huì)將‘#'存入 } 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] ; } } //中綴轉(zhuǎn)后綴 public void topostfix() { // todo auto-generated method stub system.out.println("789"); int sum = 0 ;//用于記入”（）“總個(gè)數(shù) int j = 0 ;//用于讀到”）“時(shí)循環(huán)出棧 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();//進(jìn)入前先出一個(gè) 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("匹配結(jié)束" + 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("#"); } //后綴計(jì)算 public string postfix() { int a = 0 , b = 0;//棧中彈出的兩數(shù) int sum ;//求兩數(shù)運(yùn)算 for (int i = 0; i < calculatelength ; i++ ) {// system.out.println("目前符號(hào)：" + 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(); }} |
結(jié)果如下：
一、前綴轉(zhuǎn)后綴并輸出
其中over前為轉(zhuǎn)化后的后綴表達(dá)式
over后為計(jì)算結(jié)果
|
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()); }} |
二、后綴直接輸出
注意后綴表達(dá)式時(shí)
為了實(shí)現(xiàn)多位數(shù)運(yùn)算，連續(xù)輸入一串?dāng)?shù)時(shí) ，輸入完一個(gè)數(shù)加空格
如：要計(jì)算："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()); }} |
輸出結(jié)果：
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/qq_43377749/article/details/84483862
