'24点'编码小感

灰太狼 2022-05-20 10:44 141阅读 0赞

> 此处的’24点’并不指午夜,而是一种游戏~

#### 引子 ####

之前看到了一道四则运算相关的程序题,遂而想到了[24点游戏][24],觉得有趣,就想自己随手编写了一个,起初觉得应该比较简单,但实际的路途却并不平坦~

#### 过程 ####

最开始要解决的就是算式的求解问题(输入字符串形式的四则算式,返回算式结果),对于很多脚本语言,都有内建的机制可以使用:  
譬如 JS 中 [eval][], Lua 中的 [load][] 等等,不过还是自己编码开发一下更有趣味些,所以使用传统的双栈(操作数栈和运算符栈)算法实现了一番,这里有了第一点感悟:

*  虽然可以完成基本的四则运算功能,但双栈算法却**缺乏错误检测和处理的能力**,目前的实现中,对于某些非法输入(譬如”6+(4-13-)9”),仍然可以正常运算并返回结果
 *  双栈算法的局限性也很大,功能扩展比较困难(譬如扩展支持数学函数)
 *  更好的做法还是需要使用语法分析

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

可以解析求解四则运算之后,接下来的工作就是24点游戏的”业务逻辑”了,首先要解决的一个问题是:  
**给定四个数字,判断是否可以计算得到24**(*每个数字使用一次并仅使用一次*)

穷举四个数字间所有的四则运算方式就可以解决这个问题,由于问题规模较小,一般我们手写几个嵌套循环就能完成枚举,但是自己还是尝试一般化了这里的穷举逻辑,于是有了第二点感悟:

*  一般化的生成代码往往需要涉及递归相关逻辑,就目前的实现而言,由于不想存储中间结果,我还不得不在递归中加入了回调
 *  就24点而言,四则运算的穷举包括两个部分:**运算数字间的排列**以及**运算符的添加(包括可能的括号)**,导致目前的实现中产生了递归中的双重回调(回调中包含回调)
 *  虽然通用化的代码扩展性更好,但是条件允许的情况下,**还是建议采取更简单的特定化实现**~

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

编码过程中还出现了不少之前没有预料到的问题:

*  除零错误
 *  算式生成涉及大量字符串操作,繁琐且容易出错
 *  游戏逻辑因为需求的原因,很难去除耦合,分离接口
 *  …

没想小小一个游戏,却能折射出这么多软件工程的问题,这里有了第三点感悟:

*  无论项目大小,始终对编程保持**敬畏之心**吧~

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

最后让我们来做做脑部体操,自己来算个24点吧:

11 3 12 5

(*什么?算不出24点?那就自己编个程序帮你算吧~*)

*  [gist][]上自己使用双栈算法实现的四则运算代码
 *  [这里][Link 1]有一篇关于双栈算法的描述

[24]: https://zh.wikipedia.org/wiki/24%E7%82%B9
[eval]: http://www.w3school.com.cn/js/jsref_eval.asp
[load]: https://www.lua.org/manual/5.3/manual.html#pdf-load
[gist]: https://gist.github.com/tkokof/6f2a5d2451dda2d0138e6d3075bad887
[Link 1]: http://www2.lawrence.edu/fast/GREGGJ/CMSC150/071Calculator/Calculator.html