Fdream's Blog

算法的用途：

我的目的很简单，做一个24点牌的Flash小游戏，接受用户输入的表达式，然后计算结果。貌似在AS中没有可以直接计算字符串表达式的函数，所以只好自己写了。要计算这个表达式（带括号）首先得把括号去掉，括号真的是挺麻烦的一个东东，所以还得选后缀表达式-_-

算法基本思想：

使用三个数组，一个数组保存用户输入的表达式（中缀表达式），一个数组保存后缀表达式，一个数组作为运算符的栈。

从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理；
1、如果是数字则直接放入后缀表达式数组；
2、如果是左括号则直接入栈；
3、如果是右括号，则把从栈顶直到对应左括号之间的运算符依次退栈，并清除对应的左括号；
4、对于运算符，如果该运算符的优先级大于栈顶优先级，则直接入栈，若该运算符的优先级小于等于栈顶优先级，则先把栈顶运算符出栈，写入后缀表达式数组，然后再入栈；
5、扫描完成后，取出栈中所有运算符，写入后缀表达式数组。…

先公布一下第一篇文章中提出的问题的答案：
1,5,5,5：(5-1/5)*5=24
3,3,8,8：8/(3-8/3)=24

此文所贴代码均为面向过程的C(++)代码，在VC6下编译通过。

第二种思路：

还是尽量避免处理括号，实在是很麻烦。有一种没有括号的表达式——逆波兰表达式（后缀表达式），逆波兰表达式严格地按照从左至右的顺序执行。因此，只需把所有的数字的排列组合与所有的符号的排列组合再进行排列组合即可遍历所有可能的表达式。在输出结果时，只需把逆波兰表达式按照规则还原成正常的表达式即可。

说明：’-‘和’/’有两种情况，’a-b’用’a-b’表示,’b-a’用’a|b’表示，’a/b’用’a/b’表示，’b/a’用’a\b’表示，’\’是转义字符，要用’\\’表示。…

此文所贴代码均为面向过程的C(++)代码，在VC6下编译通过。

第一种思路：
把多元运算转化为两元运算，先从四个数中取出两个数进行运算，然后把运算结果和第三个数进行运算，再把结果与第四个数进行运算。在求表达式的过程中，最难处理的就是对括号的处理，而这种思路很好的避免了对括号的处理。基于这种思路有两种算法：

第二种算法（此算法思想参考了CSDN(penguinMII)–企鹅的算法思想）：
可以寻找所有表达式的规律，得出如下结论：把表达式看成一个函数F(A,B,C,D)=24，可分两种情况F=(((A,B),C),D)和F=((A,B),(C,D))，对其分别计算即可得到答案，算法过程如下：
1)先对第一个数和第二个数进行计算，并保存结果和表达式；
2)对上述结果与第三个数进行计算，并保存结果和表达式；
3)对上述结果与第四个个数进行计算，并保存结果和表达式；
4)判断结果，并输出结果；
5)对第三个数和第四个数进行计算，并保存结果和表达式；…

昨天晚上在寝室里觉得无聊，于是就玩这个24点游戏，上网搜了半天，就一个代码是正确的，而且只能给出一个解，于是只好自己写咯，参考了网上现有的一些算法^_^

先简单介绍一下24点游戏：
给出4个1-9之间的自然数，其中每个数字只能使用一次；任意使用 + – * / ( ) ，构造出一个表达式，使得最终结果为24，这就是常见的算24点的游戏。比如两道比较经典的题目：1，5，5，5和3，3，8，8，先自己试试，答案贴在文章最后^_^

此文所贴代码均为面向过程的C(++)代码，在VC6下编译通过。

解决这个问题一般使用穷举法，即穷举4个整数所有可能的表达式，然后对表达式求值。下面的两种思路（三种算法）均是基于穷举法，各有优劣。

第一种思路：
把多元运算转化为两元运算，先从四个数中取出两个数进行运算，然后把运算结果和第三个数进行运算，再把结果与第四个数进行运算。在求表达式的过程中，最难处理的就是对括号的处理，而这种思路很好的避免了对括号的处理。基于这种思路有两种算法：…