【概述】

(相关资料图)

逆波兰表达式转换和计算可以说是Felys中最核心的部分，因为他可以将字符串形式的表达式解析出其中的逻辑并加以计算，并且我进行了一些魔改使其用起来和其他编程语言的表达式几乎没差异，如果你看不懂逆波兰表达式转换的话，强烈推荐去网上了解一下，会有很多非常细致的讲解，这里篇幅原因只会不会大量展开。

【流程】

读取，如果需要赋值，拆分变量名和表达式

将表达式中空格去除，并在将负数转化为零减这个数

处理好的表达式转化为逆波兰表达式（字符串形式存储）

解析数字和变量，同时利用栈的特性对逆波兰式进行计算

得到计算结果，如需赋值则赋值，返回表达式最终的结果

【第一步】

赋值符号可以随意定制，我这里用的是小于号和连接符的组合，毕竟我觉得赋值和等价是两回事，之前有个教授一直在强调是a variable is assigned the value而不是variable equals a value，影响深刻。这一段代码相当基础，直接看图。

【第二步】

在开始第二步之前，有必要介绍一下token函数，这个函数要求你输入一个字符，返还给你一个整型，这个返回值就是优先级：0代表数字和字母，1～3是三种不同的操作符，-1是括号，？则是未知。在标准化的过程中遇到问好会报错，空格自动跳过。

由于逆波兰表达式转换的时候是不存在负数的，所以我们要把-x转化为0-x的形式，这里我们会遇到两种特别的情况。

a/-b或者a+-b，我们需要能正确的修正为a/(0-b)和a+(0-b)，不然这在逆波兰转换时是灾难性的bug

如何正确解析-(a+b)+c为(0-(a+b))+c，这个后括号的位置显然不能简单的放在负号后面第一个数字的后面

判定逻辑都在代码注释里自己看，这里主要讲一下这里栈的作用。括号本质也是层层相扣先进后出，完美吻合栈的特性。不过这次栈中储存的是计数器，即一个前括号被读取之后，后面又遇到了多少前括号，如果计数器归零（即要被弹出）了，就说明这个前括号所对应的后括号可以加上去了，不然就得等够的后括号之后才能被弹出。里面用到了一个特殊的函数stkone就是对全栈进行自增或自减，毕竟不论是先进还是后进的括号计数器，只要遇到前括号，那就是所有都多遇到了一个前括号。运行完成之后得到的字符数组，就是我们逆波兰转换算法能稳定运作的标准输入。前提是你的栈清干净了，没清干净就代表用户输入错误。

【第三步】

真正的转换从这里开始。前文我提了无数次逆波兰表达式，所以这究竟是什么？它的另一个名字叫后缀式，顾名思义就是把运算符写在数字的后面，比如我们常用的中缀式a+b在后缀式中就是ab+，通过一定的组合之后，后缀式可以做到完全不用括号，也能完全表达出一个式子的含义，比如a*(b+c)在后缀式中即可写为abc+*，计算时我们必须要先结算bc+，因为ab后面没有运算符，计算后我们得到了ad*（假设d是bc+的值），最后就可以得到我们想要的结果了，你可能觉得没啥用，但是这对于计算机而言却极容易运算，毕竟计算机并没聪明到可以随心所欲的找括号再一步一步计算。如果你有兴趣的话可以去网上查阅相关资料，然后自己练习练习就能理解这种运算方式的优势了。

背景知识补充完，接下来就可以开始转换了。首先要明确一点，后缀式是把运算符写在后面，对于其中每一个数字的排列顺序是完全不用动的，我们需要考虑的只有调整运算符的位置。想到这里，第一步已经呼之欲出了，即遍历表达式时遇到数字直接存进container之中。为了让读者循序渐进地理解，我们姑且先不考虑括号问题，只考虑基础的四则运算优先级即乘除大于加减。简单的排列组合，我们可以得到以下四种情况：

a+b*c转化为abc*+；中缀式中的优先级为+小于*

a*b+c转化为ab*c+；中缀式中的优先级为*大于+

a+b+c转化为ab+c+；中缀式中的优先级为+等于+

a*b*c转化为ab*c*；中缀式中的优先级为*等于*

注意：3和4可以转化为abc++和abc**，但这样相当于先算bc+和bc*，与中缀式的从左到右逻辑不符合，我们不把这种混淆视听的写法考虑在内。

仔细观法就会发现，当前面一个的运算符的优先级大于等于后一个时，他们的输出其实是一样的，都必须在c写入之前提前把运算符丢进去；只有当前面一个的运算符的优先级小于等于后一个时，可以直接无脑输出数字在无脑出运算符。现在逻辑理通顺了，就可以尝试用计算机来转换了。

如你所料，我们再一次会需要使用栈来临时存放运算符，再次提醒，当遇到数字的时候，直接存入container即可，只需要关注好运算符就行。这里我们会遇到三种情况：

空栈，直接把运算符压栈

栈顶优先级小于当前运算符，直接压栈

栈顶优先级大于当前运算符，弹出全部内容到container直到触底（或者遇到括号，稍后展开讲括号），然后再把自己压栈

对照我们前面的逻辑，完全吻合，至于第三种情况为什么是直接输出到触底，你可以自己去尝试一下a+b*c+d的情况就可以理解了。最后在完成的时候，我们还需要把栈中剩下的内容全部弹出到container即可。如果你是第一次学这个东西，觉得有些步骤看不懂，要多尝试一下把逻辑彻底弄通就好，逻辑这种东西很多时候只能意会。如果你完全理解这个逻辑，你可以非常简单的支持比较符，它的优先级应当比加减还要低。

现在我们只差最后一步了，解析括号。然而括号的解析其实异常简单。因为你可以把括号理解为栈中栈，当你压入一个括号的时候，括号外的东西都与你无关，在里面继续进行对于四则运算的解析，而后括号就是结束这个栈中栈的时候，也就是把剩余的全部弹出进container直到这对括号的结束，即栈弹到左括号的时候。

这一步结束之际，我还是想说一下，我写这一段的价值不是带你细致地过一遍逆波兰表达式转换算法，而是当你在查阅相关资料时看不懂的地方，你可以来看看我这边额外的思路。

【第四步】

终于来到实际计算的地方了，你没猜错，我们还是需要借助栈的帮助来完成。在这里你只需要知道后缀式子的一个特点即可：不论运算到哪一步，遇到的第一个运算符前面必然有两及以上的数字。根据这条定理，我们只需要遍历container，把数字进行字符串转数字后直接压栈（遇到字母则认为是变量名，直接去变量库里面取值），如果遇到了运算符，我们则取出栈顶两次，运算，再压回去，直到遍历完成。如果输入正确的话，栈中应该只有一个数字，便是结果，返回即可。

注意：在计算的时候，比如bc-，在栈中表现为栈顶是c，第二层是b，如果按照顺序取弹出的话，第一个值为c，第二值为b，你要用第二个值去减第一个值才行，或者你可以像我一样运用好数学改写成负的第一个值加第二个值，乘除和比较符同理。

【第五步】

我们终于得到值，根据第一步的情况，如果要赋值就去赋值，最后在返还这个表达式的值给主程序就好了方便后面的判定。

【总结】

这一部分涉及了三套算法做三件事情，是Felys语言中最复杂抽象的一章，如果你对栈不熟悉的话，相信通过这次你一定能玩转栈操作的，毕竟这也是我第一次实际应用栈，真的花了我很多时间研究。记得多去外面查查资料。

标签：