小学生都能看懂的表达式计算（图解）

待我称王封你为后i 2022-01-11 09:39 308阅读 0赞

**基础知识**

会加减乘除（*纳尼，这个还有不会的吗*）

会双向链表和树（*纳尼，还个还要会吗*）

**温故知新**

表达式 2 + 3 - 4 + 5，人类计算的过程是这样的，如下图：

![76066-20190104091735081-941668585.png][]

*因为加减操作符优先级相同，所以从左到右依次运算。*

可计算机不会这样啊，必须先转化为一棵树（AST，抽象语法树，这是编译原理中的概念）才行，如下图：

![76066-20190104091759404-1750463642.png][]

*操作符上提变为根节点，左右操作数下降变为叶子节点，它们整体又成了一个操作数。依次对每个操作符使用这个规则，表达式即可变成一棵树。*

**再接再厉**

表达式 2 + 3 × 4 - 5 ÷ 6，人类的计算过程是这样的，如下图：

![76066-20190104091813843-1264296285.png][]

*按照优先级从高到低，先乘除，再加减。*

要想让计算机来算啊，还得先转换为一棵AST才行，如下图：

![76066-20190104091829263-1389547111.png][]

**发现问题**

综上，不难发现，先要把一个表达式转化为一棵AST。人类根据操作符的优先级很自然地把一个表达式转化为一棵树，但是计算机该怎么做呢？

**模仿人类**

人类的视线可以在表达式上随意扫描，对于不复杂的，一眼就发现优先级高的操作符，瞬间拿到它两边的操作数，就可以进行转化了。

计算机在方式上无法和人类相比，但是在结果上必须要相同，即也要找到优先级高的操作符，也要知道它两边的操作数，然后再进行转化。

**回归程序**

定义一下操作符的优先级，优先级的数值没有要求，如下图：

![76066-20190104091849116-381191979.png][]

*当我们拿到一个操作符时，也要能拿到它左右两边的操作数，因操作符和操作数是间隔互联的，实际它们就是一个双向链表。*

*因我们要找出优先级高的操作符，所以必须先找出所有的操作符，然后再判断优先级的高低。*

把整个表达式里的操作数和操作符用双向链表串起来，并把所有的操作符放入一个列表里。如下图：

![76066-20190104092942743-171296078.png][]

按优先级从高到低对操作符列表排序，优先级高的前移，优先级低的后移，优先级相同的相对位置不变。如下图：

![76066-20190104092957764-151081689.png][]

取出排在第一位的×，去双向链表里找出它的左右操作数3和4，把这三个节点转化为一棵树，再把该树作为操作数替换掉原来的三个节点，同时修复好与前面 + 号和后面 - 号的双向链接。如下图：

![76066-20190104093011972-1169039613.png][]

取出第二位的÷，采用和上面相同的方式进行转化。如下图：

![76066-20190104093027226-958457104.png][]

取出第三位的+，采用相同的方式转化。如下图：

![76066-20190104093045018-133139908.png][]

取出最后一位的-，采用相同的方式转化后，整个表达式转化完毕，变为一棵AST。如下图：

![76066-20190104092153459-1843540418.png][]

**推而广之**

*操作符有了优先级之后，就限制了表达式的计算顺序，人们有时希望打破这种限制，就引入了更神奇的操作符，就是小括号啦（哈哈）。*

表达式 ( 2 + 3 ) × ( ( 4 - 5 ) ÷ 6 )，如果还想采用上面的套路，那么核心问题就落到了操作符的优先级上了。即如何真实地反映每个操作符的优先级值。

*此时我们意识到，操作符的优先级不再是固定的，而是会随着有没有括号以及括号的嵌套深度而变化。*其实小括号本来就是改变了操作符的优先级嘛，我们人类明白这一点，关键也要让计算机明白。

既然括号是操作符，那也为它定义一个优先级值，这个值最好稍微大一些。如下图：

![76066-20190104092258483-148351418.png][]

*定义一个上下文的基础优先级值，默认当然是0了。*

*当遇到左括号时，基础优先级值加上括号优先级值，相当于基础优先级值得到了提升，这样括号里的操作符因为有基础优先级值的存在，所以自然抬高了自己的优先级值（相等于站到了巨人的肩膀上）。*

*当遇到右括号时，基础优先级值减去括号优先级值，相当于此时新的基础优先级值降到了进入括号前的水准。*如下图：

![76066-20190104092312078-2000159285.png][]

解析表达式，同时计算出每个操作符的优先级值（*牢记，遇到一个左括号加100，遇到一个右括号减100*）。如下图：

![76066-20190104093104416-1959242047.png][]

按照实际优先级值从高到低排序操作符列表。如下图：

![76066-20190104093117355-1836344730.png][]

最后按照相同的方式，转换为一棵AST。如下图：

![76066-20190104092355891-2129512691.png][]

**后记**：人类社会存在的历史要比计算机的历史长的多，从人类社会寻找问题的解决思路有时也是一个不错的方向。甚至可以从大自然中寻找。

（完）

**编程新说**

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

**用独特的视角说技术**

![76066-20190104091645201-885626176.jpg][]

转载于:https://blog.51cto.com/12151772/2338584

[76066-20190104091735081-941668585.png]: /images/20220110/f0cfe8b3a78141789b6fb7dc02eaada1.png
[76066-20190104091759404-1750463642.png]: /images/20220110/4575b960202c403d9d9ec994d0a3b839.png
[76066-20190104091813843-1264296285.png]: /images/20220110/42890443eef1498c805aaf593812cb28.png
[76066-20190104091829263-1389547111.png]: /images/20220110/e44a9ccc1c27471ebaf82a852df600cb.png
[76066-20190104091849116-381191979.png]: /images/20220110/b412600cb4d54fb993c489ff9c037d58.png
[76066-20190104092942743-171296078.png]: /images/20220110/6bbbc7839dde48db8a73259fdfc88262.png
[76066-20190104092957764-151081689.png]: /images/20220110/4e67c02b88b14fd1907ede380a43bbfc.png
[76066-20190104093011972-1169039613.png]: /images/20220110/a92d89fa864342abbe0ba6c3dcd4a04d.png
[76066-20190104093027226-958457104.png]: /images/20220110/ff182d77292046478f88c3a9fcd2954c.png
[76066-20190104093045018-133139908.png]: /images/20220110/66252cb31dcb4b6685c24ed3f866a913.png
[76066-20190104092153459-1843540418.png]: /images/20220110/0ca5b91ef5954cfeba5116a1b6b3b863.png
[76066-20190104092258483-148351418.png]: /images/20220110/7089b6913f5343819acfbef4d08555dd.png
[76066-20190104092312078-2000159285.png]: /images/20220110/3af810e88f7b491598046c51840200c1.png
[76066-20190104093104416-1959242047.png]: /images/20220110/8e63abc3ef8f46ee9e42d4620d663ea6.png
[76066-20190104093117355-1836344730.png]: /images/20220110/22baec2af3fe418abba402bea0f6228e.png
[76066-20190104092355891-2129512691.png]: /images/20220110/e23566069a3a442e9061228d9705cb65.png
[76066-20190104091645201-885626176.jpg]: /images/20220110/06fbd56c26cf4f329b8894afcc46e92b.png