利用后缀表达式（逆波兰式）算24点的JavaScript版算法

思想：

4个数字的排列，加上3个运算符的排列，使用后缀表达式的表现如下：

情形一：

1,2,3,4,+,-,* => 24*24*4

情形二：

1,2,3,+,4,-,* => 24*24*4

情形三：

1,2,3,+,-,4,* => 24*24*4

情形四：

1,2,+,3,-,4,* => 24*24*4

情形五：

1,2,+,3,4,-,* => 24*24*4

每种表现形式后面的24为4个数字的排列，4个运算符的排列，后面的4为运算符可能出现的4种情形，以第一种情况为例：

1,2,3,4,+,-,*

1,2,3,4,+,-,+

1,2,3,4,+,+,-

1,2,3,4,+,+,+

至此，大概的算法思想可以总结如下：

声明数据栈ds，保存要计算数字的排列结果；

声明算符栈os，保存四则算符的排列结果；

遍历数据栈，每次按上面列出的后缀表达式数据格式，通过遍历算符栈进行整理组合，直到结束，即可得到所有的计算表达式。

将这些表达式求值，将符合要求（即等于24，由于计算精度问题，大于23.99的结果也算正确）的结果保留，最后还需要一个将后缀表达式转换为中缀表达式的过程。

参见：

JavaScript版后缀表达式(逆波兰式)24点算法实现

编译原理-中缀表达式转后缀表达式(逆波兰式)

生硬的全排列组合表达式实现24点算法

[本日志由 dh20156 于 2009-12-06 03:06 PM 编辑]
文章来自: DHTML精英,WEB前端专家!
引用通告: 查看所有引用 | 我要引用此文章
Tags: 后缀式后缀式 逆波兰式逆波兰式 24点24点 算法算法