计算24点

问题描述:

有四个整数(0到10),运算符只有加减乘除,还有括号,每个数能且只能用一次,要求判断这些表达的结果中是否有24,如果有,输出过程,格式如下:

4*6*1*1 .(允许有括号).

注意:

1,中间结果允许出现分数,如: (5 – 1/5)*5;

2,不能有多余的括号.

3,不能出现两个负数相乘,如(1-4)*(1-9),看作(4-1)*(9-1)的重复,也不能出现8-8*(2-4).

4,避免交换律引起的重复.

5,避免结合律引起的重复.

6,由于数字相同的重复也不允许,如有两个2.

 

分析:

#1,#2,#3代表运算符,a,b,c,d代表运算数,对于表达式a #1 b #2 c #3 d根据运算顺序有如下六种可能.

1,运算顺序:#1,#2,#3            (( a  #1 b)  #2  c)  #3  d

2,运算顺序:#1,#3,#2            ( a #1 b )  #2  ( c #3 d)

3,运算顺序:#2,#3,#1            a #1 (( b #2 c  )　#3 d )

4,运算顺序:#2,#1,#3            (a #1 (  b #2 c　) )  #3 d

5运算顺序:#3,#1,#2            ( a #1 b )  #2  ( c #3 d )

6运算顺序:#3,#2,#1            a #1 ( b  #2  ( c #3 d))

其中运算符对应关系有６４种

运算数对应关系２４种．

考虑６／（５／４　－１）＝　２４自定义数据类型ＣData,包含整形的分子，分母．

 

最后排除重复(输出成字符串再比较)

１，由于运算数相同的问题，直接比较就行了．

２，交换律的问题：

(( a  #1 b)  #2  c)  #3  d成立

如果＃都是＋或＊

那么，

(( b  #1 a)  #2  c)  #3  d

(c  #2  ( a  #1 b))  #3  d

d  #3  (c  #2  ( a  #1 b))

调整使不会出现小数加(乘)大数,再比较就行了,注意如果结果相同,还要比较过程,运算符在运算数之前,如:(2+4)*6而不是6*(2+4).都是运算符也保证顺序的唯一性.

３，分配律不认为重复．

4,结合律,如: a + b –c = a – c + b;由于只有三个运算符,故只会出现两个运算符的结合律和三个运算符的结合律.我们先将-/变成加乘,全部是加(乘)的结合律好处理.a-(b*c),a-(b/c),a/(b+c),a/(b-c)不好处理,加个标记就行了.总共三个运算符,而结合律至少要两个运算符,故b,c不会再包含运算符.

 

 

 

CData的结构:

 

当为运算数时,符号为字符#,指针为空.

当为符号时,分子和分母表示结果,左右指针分别指向运算数,注意最后调整使大的在左边(对加乘而言).

如:(5-1) * (2+4),整个过程为:                

每个结点的指针用箭头代替,为了避免交换律引起的重复,将它调整成(2*4)*(5-1).不好意思,箭头丢了.

 

CData的函数有:

构造函数:  默认构造函数,复制构造函数,构造运算符的构造函数,构造运算数(分母默认为1)的构造函数.

析构函数.

重载运算符:   1, +-*/          2, <,>,==只比较分子和分母,不比较指针

3, =  右边的参数可以是整形

YueFen化简使得分子和分母不含有公约数,也不同时为负.

OutPut 将数据转化成字符串表达式,注意不能有多余的括号.

Adjust1调整使得对于+*,左边的运算数大于右边的,避免因交换律引起的重复.

Adjust2调整使避免两个负数相乘.

Adjust3 避免结合律产生的重复.

先把减转化成等效的加.

再分成情况讨论:

1,三个运算符相同.

2,运算符和左支相同.

2,运算符与右支相同.

4,左支的两个运算符相同(递归处理)

5,右支的两个运算符相同(递归处理).

对相同运算符部分,从大到小的顺序按列.不能从小到大.否则有出现-1 + 0 + 5 * 5;

再直接相加就行了.

void ChangeSubToAdd(); 将减法转变成相应的加法

void UndoSubToAdd(); 将减法还原

int GetOperand(CData  **data);//返回操作数的个数,并使data的元素指向各操作数

bool IsOperSame(char ch);//运算符和左右支的运算符是否都是ch

 

int GetAddSubCount();//返回加减的总数,好判断是不需要考虑结合律

int GetMulDivCount();//返回乘除的总数,好判断是不需要考虑结合律

void ChangeDivToMul();//除化成乘

void UndoDivToMul();//除还原成乘

 

主模块函数简介及调用关系

CData cal(CData data1,int op,CData data2)

第一个和最后一个参数是运算数,op表示运算符0到3分别表示+-*/,它调用CData类的加减乘除.

 

void Add(CData data)

它调整data(避免重复),再调用CData类的OutPut将内容转化成字符串,再将这个字符串加进全局变量result中(不重复加).

 

void Do(int nData[4],int op[3])

运算数与操作符固定时,穷举5种情况,再调用Add 将结果加进去.

 

void Cal24Point(int input[4])

穷举所有可能:操作数和操作符的对应关系,再调用Do. 三个运算符之间没有任何联系,运算数能且只能用一次.

 

测试数据:

(1),1,5,5,5    (2)3,8,8,8     (3),1,2,3, 4    (4),2,4,5,6

(4),4,2,2,5    (5)1,2,2,6     (6),4,2,8,8     (4),0,3,8,8

再随机选几组数据.