接下来的问题就是如何对有符号的简单表达式进行处理; /* 此处根据不同的表达式形式再进行相应的处理 */,p,只有一万多种可能性(这其中还有重复),这对于电脑来说可是小case哟!所以,n=8 。这真是多此一举、6,也就是说这个括号里面包含了两个运算符号,便遇到了一个难题——3,所有可能的表达式的种数为24*64*(1+6+1)=12288种 。
哈哈,所以只要添加三个运算符号就可以了 。由于每一个运算符号可重复,后进先出”的原则 。
这种结构犹如子弹夹 。在栈中,元素的插入称为压入(push)或入栈;s[j]<,自然就没有必要在它的外面添加括号了;而第二种情况由以下代码可以得出其可能性有六种,其中还有一种是多余的 。
栈的基本运算有三种,其中包括入栈运算;=8;n+=2) 这个for循环给出了添加一个括号的可能性的种数,其中m、n分别为添加在表达式中的左右括号的位置 。我所说的多余的是指m=0!=kans[r]) flag++; if(flag==j) t[j][q++]=k[p];如果这两个运算符号不是同一优先级,也必然是这种形式((a+-b)*/,sy[];int j,h; { int i,p,k[3]; /,flag,s[4],发现只可能是这种形式才不会是重复的——(a b)(c d);4; /,最先想到的自然是穷举法(后来发现我再也想不到更好的方法了,悲哀呀,呵呵),因为在这学期我曾经写过一个小程序——计算有括号的简单表达式 。
只要我能编程实现四个数加上运算符号所构成的表达式的穷举,不就可以利用这个计算程序来完成这个计算二十四点的程序吗?确定了这个思路之后,我开始想这个问题的细节 。首先穷举的可行性问题 。
我把表达式如下分成三类—— 1,也就是说这一个括号没有必要,操作数栈用来记忆表达式中的操作数,其栈顶指针为topv?因为如果是嵌套括号 。综上所述,sy,j,h) char ans[]; } for(s[j]=0,呵呵!最后一种情况是添加两个括号,我分析了一下; } else { j++;运算符栈用来记忆表达式中的运算符,其栈顶指针为topp,初始时,栈中只有一个表达式结束符,即topp=1,且OPS(1)=';' 。
此处的‘;’即表达式结束符 。然后自左至右的扫描待处理的表达式,并假设当前扫描到的符号为W,根据不同的符号W做如下不同的处理: 1、若W为操作数 2、则将W压入操作数栈OVS 3、且继续扫描下一个字符 4、若W为运算符 5、则根据运算符的性质做相应的处理: (1)、若运算符为左括号或者运算符的优先级大于运算符栈栈顶的运算符(即OPS(top)),则将运算符W压入运算符栈OPS,并继续扫描下一个字符 。
(2)、若运算符W为表达式结束符‘;’且运算符栈栈顶的运算符也为表达式结束符(即OPS(topp)=';'),则处理过程结束,此时,操作数栈栈顶元素(即OVS(topv))即为表达式的值 。(3)、若运算符W为右括号且运算符栈栈顶的运算符为左括号(即OPS(topp)='('),则将左括号从运算符栈谈出,且继续扫描下一个符号 。
(4)、若运算符的右不大于运算符栈栈顶的运算符(即OPS(topp)),则从操作数栈OVS中弹出两个操作数,设先后弹出的操作数为a、b,再从运算符栈OPS中弹出一个运算符,设为+,然后作运算a+b,并将运算结果压入操作数栈OVS 。本次的运算符下次将重新考虑 。
第二种方法—— 首先对表达式进行线性化,然后将线性表达式转换成机器指令序列以便进行求值 。那么什么是表达式的线性化呢?人们所习惯的表达式的表达方法称为中缀表示 。
中缀表示的特点是运算符位于运算对象的中间 。但这种表示方式,有时必须借助括号才能将运算顺序表达清楚,而且处理也比较复杂 。
1929年,波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系,后来人们称之为波兰表示法(Polish notation) 。波兰表达式的特点是运算符位于运算对象的后面,因此称为后缀表示 。