如何利用栈实现表达式求值 曾经终败给现在 2022-02-27 09:03 211阅读 0赞 ## 前言 ## 假如要你实现一个可以识别表达式的简易计算器,你会怎么实现?例如用户输入: 3 + 5 * (2 - 4) 可以直接得出计算结果:-7。对于人类来说,我们很容易计算出来,因为我们从左往右看,看到后面括号时,知道括号内的计算优先级最高,因此可以先计算括号内的,然后反过来计算乘法,最后计算加法,得到最终结果。 ## 后缀表达式 ## 而对于计算机来说,实际也可以采用类似的顺序,先记录存储3为a,然后存储5为b,计算2-4结果存入c,再然后计算b\*c存储d,最终计算a+d得到最终结果。而这种计算过程的操作顺序可描述如下(把操作符号放在操作数后面): 3 5 2 4 - * + 这种记法叫做后缀或逆波兰记法(而我们平常见到的叫中缀记法),它的特点是**不需要用括号就能表示出整个表达式哪部分运算先进行,也就是说不需要考虑优先级,这非常符合计算机的处理方式。**这种记法很容易使用我们前面介绍的栈来求值,但是前提是需要将中缀表达式先转换为后缀表达式。对于这种转换,我们也可以使用前面介绍的《[栈-C语言实现][-C]》或者将要介绍的树来完成,因篇幅有限,本文不准备介绍。 接下来将会介绍如何利用中缀表达式进行求值。 ## 利用栈实现中缀表达式求值 ## 前面也说到,所谓中缀表达式,就是我们能看到的正常表达式,中缀表达式求值,也就是直接对输入的表达式进行求值。为简单起见,我们这里假设**只涉及加减乘除和小括号,并且操作数都是正整数,不涉及更加复杂的数据或运算。** 计算思路: * 使用两个栈,stack0用于存储操作数,stack1用于存储操作符 * 从左往右扫描,遇到操作数入栈stack0 * 遇到操作符时,如果优先级低于或等于栈顶操作符优先级,则从stack1弹出两个元素进行计算,并压入stack0,继续与栈顶操作符的比较优先级 * 如果遇到操作符高于栈顶操作符优先级,则直接入栈stack1 * 遇到左括号,直接入栈stack1,遇到右括号,则直接出栈并计算,直到遇到左括号 上面的思路可能看起来不是很明确,我们举一个简单的例子,假如要对下面的表达式求值: 6 * (2 + 3 )* 8 + 5 我们从左往右开始扫描。首先遇到操作数‘6’,和操作符‘\*’,分别入栈 stack0: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">6</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> stack1: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">*</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> 继续往后扫描,遇到‘(’直接入栈,‘2’入栈,栈顶是左括号,’+‘入栈,‘3’入栈 stack0: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">6</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">2</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">3</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> stack1: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">*</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">(</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> 继续往后扫描,遇到右括号,它与栈顶操作符‘+’相比,优先级要高,因此,将‘+’出栈,弹出两个操作数‘3’,‘2’,计算结果得到‘5’,并入栈: stack0: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">6</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">5</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> stack1: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">*</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">(</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> 继续出栈,直到遇到左括号 stack0: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">6</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">5</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> stack1: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">*</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> 继续往后扫描,遇到操作符‘*’,优先级与栈顶‘*’优先级相同,因此弹出操作数并计算得到30入栈,最后‘\*’入栈 stack0: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">30</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> stack1: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">*</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> 继续扫描,‘8’入栈,操作符‘+’优先级小于‘\*’,弹出操作数计算得到结果‘240’,并将其入栈,最后‘+’也入栈 stack0: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">240</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> stack1: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">+</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> 最后‘5’入栈,发现操作符栈不为空,弹出操作符‘+’和两个操作数,并进行计算,得到‘245’,入栈,得到最终结果。 stack0: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;">栈顶</th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);">245</td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> stack1: <table> <thead style="font-size:inherit;color:inherit;line-height:inherit;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> <th style="color:inherit;line-height:inherit;font-size:1em;border-top-width:1px;border-color:rgb(204,204,204);text-align:left;"><br></th> </tr> </thead> <tbody style="font-size:inherit;color:inherit;line-height:inherit;border-width:0px;"> <tr style="font-size:inherit;color:inherit;line-height:inherit;border-width:1px 0px 0px;border-top-style:solid;border-top-color:rgb(204,204,204);"> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> <td style="color:inherit;line-height:inherit;font-size:1em;border-color:rgb(204,204,204);"><br></td> </tr> </tbody> </table> ## 代码实现 ## 以下为关键部分代码,完整可运行代码可阅读原文进行查看或访问 https://www.yanbinghu.com/2019/03/24/57779.html /*用于记录符号的优先级,这里浪费了一些内存,可以优化*/ static char priority[128] = { 0}; void priorityInit() { /*初始化优先级,值越小,优先级越高*/ priority['+'] = 4; priority['-'] = 4; priority['*'] = 3; priority['/'] = 3; priority['('] = 1; priority[')'] = 1; } /*比较运算符的优先级,op1优先级大于op2时,返回大于0的值*/ int priorityCompare(char op1,char op2) { return priority[op2] - priority[op1]; } /*出栈操作符和操作数进行计算*/ int calcOp(StackInfo_st *nums,StackInfo_st *ops,int nowOp) { int a ,b,op; stack_pop(ops,&op); printf("op %c is <= %c\n",nowOp,op); printf("get op from stack %c\n",op); if(SUCCESS != stack_pop(nums,&b)) { printf("pop failed\n"); return -1; } if(SUCCESS != stack_pop(nums,&a)) { printf("pop failed\n"); return 0; } printf("get b from stack %d\n",b); printf("get a from stack %d\n",a); switch(op) { case '+': { printf("push %d into stack\n",a+b); stack_push(nums,a+b); break; } case '-': { stack_push(nums,a-b); break; } case '*': { printf("push %d into stack\n",a*b); stack_push(nums,a*b); break; } case '/': { printf("push %d into stack\n",a/b); stack_push(nums,a/b); break; } } return 1; } int calc(const char* exp,int *result) { if(NULL == exp || NULL == result) return FAILURE; /*创建栈,用于保存数*/ StackInfo_st nums; nums.topOfStack = TOP_OF_STACK; /*用于保存操作符*/ StackInfo_st ops; ops.topOfStack = TOP_OF_STACK; int index = 0; /*用于标记,判断上一个是否为数字*/ int flag = 0; int temp = 0; int op ; while(0 != *exp) { /*如果是数字*/ if(isdigit(*exp)) { printf("char is %c\n",*exp); /*如果上一个还是数字,则取出栈顶数据*/ if(1 == flag) { stack_pop(&nums,&temp); printf("pop from stack num %d\n",temp); } else temp = 0; flag = 1; temp = 10 * temp + *exp-'0'; printf("push %d to stack\n",temp); stack_push(&nums,temp); } /*如果是操作符*/ else if('/' == *exp || '*' == *exp || '+' == *exp || '-' == *exp) { flag = 0; printf("OP is %c\n",*exp); while((ops.topOfStack > TOP_OF_STACK )&&(SUCCESS == stack_top(&ops,&op))&&'(' != op && ')'!=op&&(priorityCompare(*exp,op) < 0)) { calcOp(&nums, &ops,*exp); } printf("push %c to stack ops\n",*exp); stack_push(&ops,*exp); } /*左括号直接入栈*/ else if('(' == *exp ) { printf("push ( to stack ops\n"); flag = 0; stack_push(&ops,*exp); } /*右括号,计算*/ else if(')' ==*exp ) { printf("deal with ) in ops\n"); flag = 0; /*右括号时,不断计算,直到遇见左括号*/ while(SUCCESS == stack_top(&ops,&op) && '(' != op) { calcOp(&nums, &ops,*exp); } stack_pop(&ops,&op); } else { flag=0; } printf("flag is %d\n\n",flag); exp++; } /*计算剩余两个栈的内容*/ while((!stack_is_empty(&ops)) && (!stack_is_empty(&nums))) { if(!calcOp(&nums, &ops,0)) printf("exp is error\n"); } stack_pop(&nums,&temp); /*如果栈中还有内容,说明表达式错误*/ if((!stack_is_empty(&ops)) || (!stack_is_empty(&nums))) printf("\n\nexp is ok\n\n"); if(SUCCESS == stack_pop(&nums,&temp)) printf("result is %d\n",temp); *result = temp; return 0; } ## 总结 ## 本文介绍了利用栈对中缀表达式进行求值,而代码实现还有很多不足之处,例如对表达式的正确性校验不足,只能处理正整数等等,欢迎在此基础上完善补充。尽管如此,整个过程对使用栈进行中缀表达式的求值做了一个较为完整的介绍,因此具有一定的参考性。 推荐阅读: [leetcode题解-20.有效的括号][leetcode_-20.] [如何自己实现一个栈][-C] 关注公众号【编程珠玑】,获取更多Linux/C/C++/Python/Go/算法/工具等原创技术文章。后台免费获取经典电子书和视频资源。 ![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] [-C]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284540&idx=1&sn=2a79d3785af68f03e6ea89b4fc05b415&chksm=f2f9acdbc58e25cd3957113c7604cb5dfa6a3cbd748b832217742b896791d120986feac0f30d&scene=21#wechat_redirect [leetcode_-20.]: http://mp.weixin.qq.com/s?__biz=MzI2OTA3NTk3Ng==&mid=2649284545&idx=1&sn=d3c2bcac091f8ff84a188f33a19c6dcf&chksm=f2f9aca6c58e25b0793fe899daf9ba7fb1d937b460138b629129dfcfc43783a90c1d8b80c3b0&scene=21#wechat_redirect [640_wx_fmt_jpeg]: /images/20220227/edbb2da1026c4734a474a0aaf66fed0f.png
还没有评论,来说两句吧...