Java 数据结构和算法（六）：前缀、中缀、后缀表达式

骑猪看日落 2022-10-30 15:25 156阅读 0赞

# [Java数据结构和算法（六）——前缀、中缀、后缀表达式][Java] #

--------------------

前面我们介绍了三种数据结构，第一种数组主要用作数据存储，但是后面的两种栈和队列我们说主要作为程序功能实现的辅助工具，其中在介绍栈时我们知道栈可以用来做单词逆序，匹配关键字符等等，那它还有别的什么功能吗？以及数据结构与本篇博客的主题前缀、中缀、后缀表达式有什么关系呢？

### 1、人如何解析算术表达式 ###

如何解析算术表达式？或者换种说法，遇到某个算术表达式，我们是如何计算的：

**①、求值 3+4-5**

**　　![140054c37a72bd9d17c8d01cc31b51cb.png][]**

这个表达式，我们在看到3+4后都不能直接计算3+4的值，知道看到4后面的 - 号，因为减号的优先级和前面的加号一样，所以可以计算3+4的值了，如果4后面是 \* 或者 /，那么就要在乘除过后才能做加法操作，比如：

**②、求值 3+4\*5**

**　　![903ed6007493b293970b700900885084.png][]**

这个不能先求3+4的值，因为4后面的\*运算级别比前面的+高。通过这两个表达式的说明，我们可以总结解析表达式的时候遵循的几条规则：

**①、从左到右读取算式。**

**　　②、已经读到了可以计算值的两个操作数和一个操作符时，可以计算，并用计算结果代替那两个操作数和一个操作符。**

**　　③、继续这个过程，从左到右，能算就算，直到表达式的结尾。**

### 2、计算机如何解析算术表达式 ###

对于前面的表达式 3+4-5，我们人是有思维能力的，能根据操作符的位置，以及操作符的优先级别能算出该表达式的结果。但是计算机怎么算？

计算机必须要向前（从左到右）来读取操作数和操作符，等到读取足够的信息来执行一个运算时，找到两个操作数和一个操作符进行运算，有时候如果后面是更高级别的操作符或者括号时，就必须推迟运算，必须要解析到后面级别高的运算，然后回头来执行前面的运算。我们发现这个过程是极其繁琐的，而计算机是一个机器，只认识高低电平，想要完成一个简单表达式的计算，我们可能要设计出很复杂的逻辑电路来控制计算过程，那更不用说很复杂的算术表达式，所以这样来解析算术表达式是不合理的，那么我们应该采取什么办法呢？

请大家先看看什么是前缀表达式，中缀表达式，后缀表达式：这三种表达式其实就是算术表达式的三种写法，以 3+4-5为例

①、前缀表达式：操作符在操作数的前面，比如 +-543

②、中缀表达式：操作符在操作数的中间，这也是人类最容易识别的算术表达式 3+4-5

③、后缀表达式：操作符在操作数的后面，比如 34+5-

上面我们讲的人是如何解析算术表达式的，也就是解析中缀表达式，这是人最容易识别的，但是计算机不容易识别，计算机容易识别的是前缀表达式和后缀表达式，将中缀表达式转换为前缀表达式或者后缀表达式之后，计算机能很快计算出表达式的值，那么中缀表达式是如何转换为前缀表达式和后缀表达式，以及计算机是如何解析前缀表达式和后缀表达式来得到结果的呢？

### 3、后缀表达式 ###

后缀表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。

由于后缀表达式的运算符在两个操作数的后面，那么计算机在解析后缀表达式的时候，只需要从左向右扫描，也就是只需要向前扫描，而不用回头扫描，遇到运算符就将运算符放在前面两个操作符的中间（这里先不考虑乘方类似的单目运算），一直运算到最右边的运算符，那么就得出运算结果了。既然后缀表达式这么好，那么问题来了：

①、如何将中缀表达式转换为后缀表达式？

对于这个问题，转换的规则如下：

![e2672ab1e1514c565b1d41dbcda44d46.png][]

一、先自定义一个栈

二、前缀表达式转换为后缀表达式

<table> 
 <tbody> 
 <tr> 
 <td> 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 </td> 
 <td> <code>package</code>&nbsp;<code>com.ys.poland;</code> &nbsp; <code>public</code>&nbsp;<code>class</code>&nbsp;<code>InfixToSuffix { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>MyCharStack s1;</code><code>//定义运算符栈</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>MyCharStack s2;</code><code>//定义存储结果栈</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>String input;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//默认构造方法，参数为输入的中缀表达式</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>InfixToSuffix(String in){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>input = in;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s1 =&nbsp;</code><code>new</code>&nbsp;<code>MyCharStack(input.length());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s2 =&nbsp;</code><code>new</code>&nbsp;<code>MyCharStack(input.length());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//中缀表达式转换为后缀表达式，将结果存储在栈中返回，逆序显示即后缀表达式</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>MyCharStack doTrans(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code><code>(</code><code>int</code>&nbsp;<code>j =&nbsp;</code><code>0</code>&nbsp;<code>; j &lt; input.length() ; j++){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(</code><code>"s1栈元素为："</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s1.displayStack();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.print(</code><code>"s2栈元素为："</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s2.displayStack();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>char</code>&nbsp;<code>ch = input.charAt(j);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"当前解析的字符:"</code><code>+ch);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>switch</code>&nbsp;<code>(ch) { </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>case</code>&nbsp;<code>'+'</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>case</code>&nbsp;<code>'-'</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>gotOper(ch,</code><code>1</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>case</code>&nbsp;<code>'*'</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>case</code>&nbsp;<code>'/'</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>gotOper(ch,</code><code>2</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>case</code>&nbsp;<code>'('</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s1.push(ch);</code><code>//如果当前字符是'(',则将其入栈</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>case</code>&nbsp;<code>')'</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>gotParen(ch);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>default</code><code>:</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//1、如果当前解析的字符是操作数，则直接压入s2</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//2、</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s2.push(ch);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>//end switch</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>//end for</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(!s1.isEmpty()){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s2.push(s1.pop());</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>s2;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>void</code>&nbsp;<code>gotOper(</code><code>char</code>&nbsp;<code>opThis,</code><code>int</code>&nbsp;<code>prec1){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(!s1.isEmpty()){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>char</code>&nbsp;<code>opTop = s1.pop();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(opTop ==&nbsp;</code><code>'('</code><code>){ </code><code>//如果栈顶是'(',直接将操作符压入s1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s1.push(opTop);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>else</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code>&nbsp;<code>prec2;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(opTop ==&nbsp;</code><code>'+'</code>&nbsp;<code>|| opTop ==&nbsp;</code><code>'-'</code><code>){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>prec2 =&nbsp;</code><code>1</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>else</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>prec2 =&nbsp;</code><code>2</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(prec2 &lt; prec1){ </code><code>//如果当前运算符比s1栈顶运算符优先级高，则将运算符压入s1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s1.push(opTop);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>else</code><code>{ </code><code>//如果当前运算符与栈顶运算符相同或者小于优先级别，那么将S1栈顶的运算符弹出并压入到S2中</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//并且要再次再次转到while循环中与 s1 中新的栈顶运算符相比较；</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s2.push(opTop);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>//end while</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//如果s1为空，则直接将当前解析的运算符压入s1</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s1.push(opThis);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//当前字符是 ')' 时，如果栈顶是'(',则将这一对括号丢弃，否则依次弹出s1栈顶的字符，压入s2，直到遇到'('</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>public</code>&nbsp;<code>void</code>&nbsp;<code>gotParen(</code><code>char</code>&nbsp;<code>ch){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(!s1.isEmpty()){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>char</code>&nbsp;<code>chx = s1.pop();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(chx ==&nbsp;</code><code>'('</code><code>){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code><code>else</code><code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>s2.push(chx);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> &nbsp; <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

三、测试

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 </td> 
 <td> <code>@Test</code> <code>public</code>&nbsp;<code>void</code>&nbsp;<code>testInfixToSuffix(){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>String input;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(</code><code>"Enter infix:"</code><code>);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Scanner scanner =&nbsp;</code><code>new</code>&nbsp;<code>Scanner(System.in);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>input = scanner.nextLine();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>InfixToSuffix in =&nbsp;</code><code>new</code>&nbsp;<code>InfixToSuffix(input);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>MyCharStack my = in.doTrans();</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>my.displayStack();</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

四、结果

![17a5fa5f751525ecab1c79dc252df0d2.png][]

五、分析

![ef749246912f89b16509308cff5cfbaa.png][]

②、计算机如何实现后缀表达式的运算？

![01cb40463412c7448472d3717299024c.png][]

### 4、前缀表达式 ###

前缀表达式，指的是不包含括号，运算符放在两个运算对象的前面，严格从右向左进行（不再考虑运算符的优先规则），所有的计算按运算符出现的顺序。

注意：后缀表达式是从左向右解析，而前缀表达式是从右向左解析。

①、如何将中缀表达式转换为前缀表达式？

![230fc8a4ee68e4b7bdd40cb7cf810978.png][]

②、计算机如何实现前缀表达式的运算？

![d75578036c5e62ea4e862bb43bb85cbe.png][]

[Java]: https://www.cnblogs.com/ysocean/p/7910432.html
[140054c37a72bd9d17c8d01cc31b51cb.png]: /images/20221024/69350729aa2b4fd58e8a2a51ca3cc838.png
[903ed6007493b293970b700900885084.png]: /images/20221024/aa412c6d8d1b4abc94ce301661a8ba2a.png
[e2672ab1e1514c565b1d41dbcda44d46.png]: /images/20221024/934c820a4aec463287b62aab978d3c05.png
[17a5fa5f751525ecab1c79dc252df0d2.png]: /images/20221024/e8bb7eded143412aa33125f6b5f6bdcf.png
[ef749246912f89b16509308cff5cfbaa.png]: /images/20221024/05d5416ec8ce417abefb8b1dce872d32.png
[01cb40463412c7448472d3717299024c.png]: /images/20221024/ce06b0defcf645968c6cacc7986c7314.png
[230fc8a4ee68e4b7bdd40cb7cf810978.png]: /images/20221024/0eb50c43159643df9543328352da2c13.png
[d75578036c5e62ea4e862bb43bb85cbe.png]: /images/20221024/564546c81fb545288830905c666b9bf0.png