中缀表达式转后缀表达式--C# 代码实现

使用计算机进行表达式的转换
平常我们用的标准四则运算表达式，如“1+（2-3）*4/5”叫做中缀表达式，，，
中缀转后缀表达式的规则是：

• 从左到右变量中缀表达式的每个数字和符号，若是数字就输出，即成为后面表达式的一部分，若是符号，则判断其与栈顶符号的优先级，是右括号或者有限级低于栈顶符号（先乘除后加减），则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最后输出后后缀表达式为止，，，

以“9+（3-1）× 3+10÷2”为例
初始化一个空战，用来对符号进栈，

第一个字符是9，输出9，后面是符号“+”，进栈，，，
第三个字符是“（”，依然是符号，因其只是符号“+”，还为配对，故进栈，，
第四个字符是数字3，输出，总表达式为9 3 接着是“-”，进栈，，，

接下来是数字1，输出，总表达式为9，3，1后面是符号“）”，，此时我们需要去匹配此前的“（”，，所以栈顶依次出栈，并输出，直到“（”出栈为止，，此时左括号上方只有“ - ”，因此输出“ - ”，总的输出表达式为9 3 1 - ，，，
接着是数字3，，输出，总的表达式为9 3 1 - 3 ，，紧接着是符号“ × ”，，因为此时的栈顶符号为“ + ”，优先级低于“ * ”，，因此不输出，“ * ”进栈，，

之后是符号“+”，此时当前栈顶元素是“ × ”比“ + ”的优先级高，，因此栈中元素出栈并输出（没有比“+”号根低的优先级，所以全部出栈），，总输出表达式为9 3 1 - 3 × +，，然后将当前这个符号“+” 进栈，，
接着是数字10，，输出总的表达式就是：9 3 1 - 3 * + 10 后面的是“÷”，所以“/”进栈
最后一个数字2，，输出，然后件栈中的符号全部输出，，即最终的表达式是：9 3 1 - 3 * + 10 2 / +

实现方法：主要利用的栈的特性，然后是使用状态机的思路实现，，，把“+-”，“*/”，“（”,“）”分别看做一种状态，，然后挨个实现每个状态之间的跳转，，，值得注意的是：每个状态的下一步都有可能是四个状态，，一定要讨论所有的输入，然后在考虑下一状态，，，点击查看状态机的简易实例

下面是使用以上思路实现的代码，，，，
之前问题一修改，若有错误请留言。

namespace 玩嗨的练习 { class Program { static void Main(string[] args) { //运行时用建议输入空格 Console.WriteLine("请输入您要转换的表达式："); string inputstr = Console.ReadLine(); //测试用 //string inputstr = "9 * (3 - 1) + (10 - 1) / 2"; //string inputstr = "1 - 2 - 3 * 4 + 10 / 5"; Console.WriteLine("您转换后的结果为："); Change(inputstr); Console.ReadKey(); } private static void Change(string inputstr) { Stack<char> arrStark = new Stack<char>(); char[] arrChar = inputstr.ToCharArray(); int a = 4;  //默认状态是什么都没有,这里是4状态，， for (int i = 0; i < arrChar.Length; i++) { //数字空格就直接输出 if (arrChar[i] <= '9' && arrChar[i] >= '0') { Console.Write(arrChar[i]); } if (arrChar[i] == ' ') { Console.Write(" "); } //运算符走状态机 switch (a) { //=============================状态1 * / ==================================== case 1:  //表示当前是+- 状态 if (arrChar[i] == '+' || arrChar[i] == '-') { a = 1; Console.Write(arrStark.Pop()); arrStark.Push(arrChar[i]); } else if (arrChar[i] == '*' || arrChar[i] == '/') { a = 2; arrStark.Push(arrChar[i]); } else if (arrChar[i] == '(') { a = 3; arrStark.Push(arrChar[i]); } else if (arrChar[i] == ')') { a = 4; for (int j = 0; j < arrStark.Count; j++) { //输出括号中间的符号，，， if (arrStark.Peek() == '(') { //把左括号，，弹出栈外 arrStark.Pop(); break; } else { Console.Write(arrStark.Pop()); } } } break; //=============================状态2 * / ==================================== case 2:  //表示当前是* / 状态 if (arrChar[i] == '+' || arrChar[i] == '-') { a = 1; for (int j = 0; j <= arrStark.Count; j++) { //Console.Write(arrStark.Count); Console.Write(arrStark.Pop()); } arrStark.Push(arrChar[i]); } else if (arrChar[i] == '*' || arrChar[i] == '/') { a = 2; Console.Write(arrStark.Pop()); arrStark.Push(arrChar[i]); } else if (arrChar[i] == '(') { a = 3; arrStark.Push(arrChar[i]); } else if (arrChar[i] == ')') { a = 4; for (int j = 0; j < arrStark.Count; j++) { if (arrStark.Peek() == '(') { //把左括号，，弹出栈外 arrStark.Pop(); break; } else { //输出括号中间的符号，，， Console.Write(arrStark.Pop()); } } } break; //=============================状态3 ） ==================================== case 3:  //表示当前是( 状态 if (arrChar[i] == '+' || arrChar[i] == '-') { arrStark.Push(arrChar[i]); } else if (arrChar[i] == '*' || arrChar[i] == '/') { arrStark.Push(arrChar[i]); } else if (arrChar[i] == '(') { a = 3; arrStark.Push(arrChar[i]); } else if (arrChar[i] == ')') { a = 4; for (int j = 0; j < arrStark.Count; j++) { if (arrStark.Peek() == '(') { //把左括号，，弹出栈外 arrStark.Pop(); break; } else { //输出括号中间的符号，，， Console.Write(arrStark.Pop()); } } } break; //=============================状态4 （ ==================================== case 4:  //表示当前是 )  状态 if (arrChar[i] == '+' || arrChar[i] == '-') { if (arrStark.Count == 0) { a = 1; arrStark.Push(arrChar[i]); } else { if (arrStark.Peek() == '+' || arrStark.Peek() == '-') { a = 1; arrStark.Push(arrChar[i]); } else if (arrStark.Peek() == '*' || arrStark.Peek() == '/') { a = 1; for (int j = 0; j < arrStark.Count; j++) { Console.Write(arrStark.Pop()); } arrStark.Push(arrChar[i]); } } } else if (arrChar[i] == '*' || arrChar[i] == '/') { if (arrStark.Count == 0) { a = 2; arrStark.Push(arrChar[i]); } else { if (arrStark.Peek() == '+' || arrStark.Peek() == '-') { a = 2; arrStark.Push(arrChar[i]); } else if (arrStark.Peek() == '*' || arrStark.Peek() == '/') { a = 2; arrStark.Push(arrChar[i]); } } } else if (arrChar[i] == '(') { a = 3; arrStark.Push(arrChar[i]); } if (arrChar[i] == ')') { a = 4; for (int j = 0; j < arrStark.Count; j++) { if (arrStark.Peek() == '(') { //把左括号，，弹出栈外 arrStark.Pop(); break; } else { //输出括号中间的符号，，， Console.Write(arrStark.Pop()); } } } break; default: Console.WriteLine("Wrong"); break; } } //遍历栈中剩余的符号输出，并清空栈， foreach (char item in arrStark) { Console.Write(" " + item); } arrStark.Clear(); } }
}

  

 

  
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
  
243
  
244
  
245
  
246
  
247
  
248
  
249
  
250
  
251
  
252
  
253
  
254
  
255
  
256
  
257
  
258
  
259
  
260
 

测试效果图：

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/78067542