24点规则

提问：

网友回答：

棋牌类益智游戏，要求四个数字运算结果等于二十四

方法如下:

首先穷举的可行性问题。把表达式如下分成三类--

1、 无括号的简单表达式。

2、 有一个括号的简单表达式。

3、 有两个括号的较复杂表达式。

在栈中，元素的插入称为压入(push)或入栈，元素的删除称为弹出(pop)或退栈。

栈的基本运算有三种，其中包括入栈运算、退栈运算以及读栈顶元素，这些请参考相关数据结构资料。根据这些基本运算就可以用数组模拟出栈来。

那么作为栈的著名应用，表达式的计算可以有两种方法。

第一种方法:

首先建立两个栈，操作数栈OVS和运算符栈OPS。其中，操作数栈用来记忆表达式中的操作数，其栈顶指针为topv，初始时为空，即topv=0;运算符栈用来记忆表达式中的运算符，其栈顶指针为topp，初始时，栈中只有一个表达式结束符，即topp=1，且OPS(1)=';'。此处的';'即表达式结束符。

然后自左至右的扫描待处理的表达式，并假设当前扫描到的符号为W，根据不同的符号W做如下不同的处理:

1、 若W为操作数

2、 则将W压入操作数栈OVS

3、 且继续扫描下一个字符

4、 若W为运算符

5、 则根据运算符的性质做相应的处理:

6、若运算符为左括号或者运算符的优先级大于运算符栈栈顶的运算符(即OPS(top))，则将运算符W压入运算符栈OPS，并继续扫描下一个字符。

7、若运算符W为表达式结束符';'且运算符栈栈顶的运算符也为表达式结束符(即OPS(topp)=';')，则处理过程结束，此时，操作数栈栈顶元素(即OVS(topv))即为表达式的值。

8、若运算符W为右括号且运算符栈栈顶的运算符为左括号(即OPS(topp)='(')，则将左括号从运算符栈谈出，且继续扫描下一个符号。

9、若运算符的右不大于运算符栈栈顶的运算符(即OPS(topp))，则从操作数栈OVS中弹出两个操作数，设先后弹出的操作数为a、b，再从运算符栈OPS中弹出一个运算符，设为+，然后作运算a+b，并将运算结果压入操作数栈OVS。本次的运算符下次将重新考虑。

第二种方法:

首先对表达式进行线性化，然后将线性表达式转换成机器指令序列以便进行求值。

那么什么是表达式的线性化呢?人们所习惯的表达式的表达方法称为中缀表示。中缀表示的特点是运算符位于运算对象的中间。但这种表示方式，有时必须借助括号才能将运算顺序表达清楚，而且处理也比较复杂。

1929年，波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系，后来人们称之为波兰表示法(Polish notation)。波兰表达式的特点是运算符位于运算对象的后面，因此称为后缀表示。在对波兰表达式进行运算，严格按照自左至右的顺序进行。下面给出一些表达式及其相应的波兰表达式。

表达式波兰表达式

A-B AB-

OK，所谓表达式的线性化是指将中缀表达的表达式转化为波兰表达式。对于每一个表达式，利用栈可以把表达式变换成波兰表达式，也可以利用栈来计算波兰表达式的值。

至于转换和计算的过程和第一种方法大同小异，这里就不再赘述了。

下面给出转换和计算的具体实现程序--

这样这个程序基本上就算解决了，回过头来拿这个程序来算一算文章开始的那个问题。很快就算出来了，原来如此简单--(6-3)*10-6=24。

折叠

"巧算24点"能极大限度地调动眼、脑、手、口、耳多种感官的协调活动，对于培养我们快捷的心算能力和反应能力很有帮助