此处的’24点’并不指午夜,而是一种游戏~
引子
之前看到了一道四则运算相关的程序题,遂而想到了24点游戏,觉得有趣,就想自己随手编写了一个,起初觉得应该比较简单,但实际的路途却并不平坦~
过程
最开始要解决的就是算式的求解问题(输入字符串形式的四则算式,返回算式结果),对于很多脚本语言,都有内建的机制可以使用: 譬如 JS 中 eval, Lua 中的 load 等等,不过还是自己编码开发一下更有趣味些,所以使用传统的双栈(操作数栈和运算符栈)算法实现了一番,这里有了第一点感悟:
- 虽然可以完成基本的四则运算功能,但双栈算法却缺乏错误检测和处理的能力,目前的实现中,对于某些非法输入(譬如”6 (4-13-)9”),仍然可以正常运算并返回结果
- 双栈算法的局限性也很大,功能扩展比较困难(譬如扩展支持数学函数)
- 更好的做法还是需要使用语法分析
可以解析求解四则运算之后,接下来的工作就是24点游戏的”业务逻辑”了,首先要解决的一个问题是: 给定四个数字,判断是否可以计算得到24(每个数字使用一次并仅使用一次)
穷举四个数字间所有的四则运算方式就可以解决这个问题,由于问题规模较小,一般我们手写几个嵌套循环就能完成枚举,但是自己还是尝试一般化了这里的穷举逻辑,于是有了第二点感悟:
- 一般化的生成代码往往需要涉及递归相关逻辑,就目前的实现而言,由于不想存储中间结果,我还不得不在递归中加入了回调
- 就24点而言,四则运算的穷举包括两个部分:运算数字间的排列以及运算符的添加(包括可能的括号),导致目前的实现中产生了递归中的双重回调(回调中包含回调)
- 虽然通用化的代码扩展性更好,但是条件允许的情况下,还是建议采取更简单的特定化实现~
编码过程中还出现了不少之前没有预料到的问题:
- 除零错误
- 算式生成涉及大量字符串操作,繁琐且容易出错
- 游戏逻辑因为需求的原因,很难去除耦合,分离接口
- …
没想小小一个游戏,却能折射出这么多软件工程的问题,这里有了第三点感悟:
- 无论项目大小,始终对编程保持敬畏之心吧~
最后让我们来做做脑部体操,自己来算个24点吧:
11 3 12 5
(什么?算不出24点?那就自己编个程序帮你算吧~)
- gist上自己使用双栈算法实现的四则运算代码
- 这里有一篇关于双栈算法的描述
