#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN (7)
#define LEN1 (6*6*6*4*3*2*2)
// const int LEN1 = (6*6*6*4*3*2*2);
typedef struct rational_number
{
int numerator, denominator;
} Rational;
typedef struct binary_expression
{
int val, op_type;
char *Infix, *stdInfix;
struct binary_expression *left, * right;
} B_exp;
char *stdInfixs[LEN1];
int cnt_stdInfixs;
Rational new_Rational(int n, int d)
{
Rational r;
r.numerator = n;
r.denominator = d;
return r;
}
enum oper
{
none = 0, add, rev_subtract, subtract, multiply, rev_division, division
};
char *operators[] =
{
"", " + ", " <- ", " - ", " * ", " </ ", " / "
};
char *oprs[] =
{
"","+","<-","-","*","</","/"
};
enum exp_type
{
number = 0, operator
};
Rational calc(Rational a, Rational b, int t)
{
if (!a.denominator || !b.denominator) return new_Rational(0, 0);
if (t == division && b.numerator == 0) return new_Rational(0, 0);
switch (t)
{
case add:
return new_Rational(a.numerator * b.denominator + b.numerator * a.denominator, a.denominator * b.denominator);
break;
case rev_subtract:
return calc(b, a, subtract);
break;
case subtract:
return new_Rational(a.numerator * b.denominator - b.numerator * a.denominator, a.denominator * b.denominator);
break;
case multiply:
return new_Rational(a.numerator * b.numerator, a.denominator * b.denominator);
break;
case rev_division:
return calc(b, a, division);
break;
case division:
return new_Rational(a.numerator * b.denominator, a.denominator * b.numerator);
break;
}
return new_Rational(0, 0);
}
int opr_level(int opr)
{
if (opr < add) return 0;
else if (opr >= multiply) return 2;
else return 1;
}
int opr_dir_sensitive(int opr)
{
if (opr == none || opr == add || opr == multiply) return 0;
else return 1;
}
char * add_parentheses(char * str)
{
char temp[100] = "";
return strcat(strcpy(str, strcat(strcpy(temp, "("), str)), ")");
}
void writeExp(int exp[], int exp_t[], int len)
{
// code for 中缀表达式 begin
B_exp bin_expS[LEN], *bin_expStk[LEN];
int ps = 0;
// code for 中缀表达式 end
int i;
for (i = 0; i < len; i++)
{
// code for 中缀表达式 begin
// init bin_expS[i];
// 中缀式标准式: 每一个有交换律运算的 左式 和 右式 比较, 小的做左式
bin_expS[i].Infix = (char *) malloc(sizeof (char) * 100);
bin_expS[i].stdInfix = (char *) malloc(sizeof (char) * 100); // 标准式
*(bin_expS[i].Infix) = '\0';
*(bin_expS[i].stdInfix) = '\0';
bin_expS[i].val = 0;
bin_expS[i].op_type = none;
bin_expS[i].left = NULL;
bin_expS[i].right = NULL;
// code for 中缀表达式 end
// if (i > 0 && ((t=='A' && ~i & 1) || (t=='B' && (i==2 || i==5 || i==6 ))))
if (exp_t[i] == operator)
{
printf("%s", oprs[exp[i]]);
// code for 中缀表达式 begin
if (exp[i] == rev_division || exp[i] == rev_subtract)
{
bin_expS[i].op_type = exp[i] + 1;
bin_expS[i].left = bin_expStk[ps - 1];
bin_expS[i].right = bin_expStk[ps - 2];
}
else
{
bin_expS[i].op_type = exp[i];
bin_expS[i].right = bin_expStk[ps - 1];
bin_expS[i].left = bin_expStk[ps - 2];
}
ps -= 2;
bin_expStk[ps++] = &(bin_expS[i]);
/* 加括号原则
1
子运算的运算优先级 低于 当前运算
+ - 低于 * /
2
子运算的运算优先级 同于 当前运算
子运算 是 当前运算 - 或者 / 的右项( <- </ 的左项), 且当前运算是有向运算(无交换律的运算)
即, 当前运算 是 - 或者 / 或者 <- 或者 </
而子运算 是 - 的 减数, 或者是 / 的除数
*/
if (bin_expS[i].left -> op_type != none)
if (opr_level(bin_expS[i].left -> op_type) < opr_level(bin_expS[i].op_type))
{
add_parentheses(bin_expS[i].left ->Infix);
add_parentheses(bin_expS[i].left ->stdInfix);
}
if (bin_expS[i].right -> op_type != none)
if ((opr_level(bin_expS[i].right -> op_type) < opr_level(bin_expS[i].op_type))
||
(
(opr_level(bin_expS[i].right -> op_type) == opr_level(bin_expS[i].op_type))
&&
opr_dir_sensitive(bin_expS[i].op_type)
)
)
{
add_parentheses(bin_expS[i].right ->Infix);
add_parentheses(bin_expS[i].right ->stdInfix);
}
strcat(strcat(strcpy(bin_expS[i].Infix, bin_expS[i].left ->Infix), operators[bin_expS[i].op_type]),
bin_expS[i].right->Infix);
if (opr_dir_sensitive(bin_expS[i].op_type))
{
strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].left ->stdInfix), operators[bin_expS[i].op_type]),
bin_expS[i].right->stdInfix);
}
else
{
if (strcmp(bin_expS[i].right ->stdInfix, bin_expS[i].left ->stdInfix) < 0)
{
strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].right ->stdInfix), operators[bin_expS[i].op_type]),
bin_expS[i].left->stdInfix);
}
else
{
strcat(strcat(strcpy(bin_expS[i].stdInfix, bin_expS[i].left ->stdInfix), operators[bin_expS[i].op_type]),
bin_expS[i].right->stdInfix);
}
}
// code for 中缀表达式 end
}
else
{
printf("%d", exp[i]);
// code for 中缀表达式 begin
bin_expS[i].val = exp[i];
bin_expS[i].op_type = none;
sprintf(bin_expS[i].Infix, "%d", bin_expS[i].val);
sprintf(bin_expS[i].stdInfix, "%d", bin_expS[i].val);
// 数压栈
bin_expStk[ps++] = &(bin_expS[i]);
// code for 中缀表达式 end
}
if (i < len - 1) printf(" ");
}
printf("\t\t%s\t\t%s", bin_expStk[ps - 1]->Infix, bin_expStk[ps - 1]->stdInfix); // 中缀表达式
printf("\n");
int existing;
existing = 0;
for (i=0; i<cnt_stdInfixs; i++)
{
if (strcmp(stdInfixs[i], bin_expStk[ps - 1]->stdInfix) == 0)
{
existing = 1;
break;
}
}
if (!existing)
{
if (stdInfixs[cnt_stdInfixs] == NULL)
{
stdInfixs[cnt_stdInfixs] = (char *) malloc(sizeof (char) * 100);
*(stdInfixs[cnt_stdInfixs]) = '\0';
}
strcpy(stdInfixs[cnt_stdInfixs++], bin_expStk[ps - 1]->stdInfix);
}
}
int main()
{
int datas[] = {1, 5, 5, 9};
int cnt = sizeof (datas) / sizeof (datas[0]);
int len = cnt * 2 - 1;
int pMAX = cnt * 2 - 2;
int used[cnt], exp[len], exp_t[len], pds[len], opr[len], p, i, sumA, sumB, L1;
Rational result[len];
for (i=0, L1 = LEN1; i< L1; i++) stdInfixs[i] = NULL;
while (1)
{
for (i=0, L1 = LEN1; i< L1; i++)
if (stdInfixs[i] != NULL)
{
free(stdInfixs[i]);
stdInfixs[i] = NULL;
}
cnt_stdInfixs =0;
printf("input 4 numbers, separate by space\n");
scanf("%d%d%d%d", &datas[0], &datas[1], &datas[2], &datas[3]);
sumA = sumB = 0;
for (i = 0; i < cnt; i++)
{
// A 形态
/*
// O
// / \
// O O
// / \
// O O
// / \
// O O
*/
for (p = 0; p < cnt; p++) used[p] = 0;
p = 0;
pds[p] = i;
used[pds[p]] = 1;
exp[p] = datas[pds[p]];
exp_t[p] = number;
result[p] = new_Rational(exp[p], 1);
opr[p] = 0;
do
{
if (~p & 1)
{
if (opr[p] > division)
{
p--;
used[pds[p]] = 0; // 释放当前操作数
// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}
}
else
{
if (p > 0)
{
exp[p] = opr[p];
exp_t[p] = operator;
result[p] = calc(result[p - 2], new_Rational(exp[p - 1], 1), exp[p]);
}
if (p >= pMAX)
{
// 检测并输出
if ((result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator))
{
writeExp(exp, exp_t, sizeof (exp) / sizeof (exp[0]));
sumA++;
}
opr[p]++;
}
else
{
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}
}
}
else
{
if (pds[p] >= cnt)
{
p--;
opr[p]++;
}
else
{
used[pds[p]] = 1;
exp[p] = datas[pds[p]];
exp_t[p] = number;
p++;
opr[p] = add;
}
}
}
while (p > 0);
/* B 形态
// O
// / \
// / \
// O O
// / \ / \
// O O O O
//
// a b +-* / c d +-* / +-* /
// c d
// d
//
// 0 1 2 3 4 5 6
*/
for (p = 0; p < cnt; p++) used[p] = 0;
p = 0;
pds[p] = i;
used[pds[p]] = 1;
exp[p] = datas[pds[p]];
exp_t[p] = number;
result[p] = new_Rational(exp[p], 1);
opr[p] = 0;
do
{
if (p == 2 || p == 5 || p == 6)
{
if (opr[p] > division)
{
p--;
if (p == 1 || p == 4)
{
used[pds[p]] = 0; // 释放当前操作数
// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}
}
else
{
opr[p]++;
}
}
else
{
if (p > 0)
{
exp[p] = opr[p];
exp_t[p] = operator;
if (p == 2 || p == 5)
{
result[p] = calc(new_Rational(exp[p - 2], 1), new_Rational(exp[p - 1], 1), exp[p]);
}
else
{
result[p] = calc(result[2], result[5], exp[p]);
}
}
if (p >= pMAX)
{
// 检测并输出
if (/* 1 || */ (result[p].denominator != 0 && result[p].denominator * 24 == result[p].numerator))
{
writeExp(exp, exp_t, sizeof (exp) / sizeof (exp[0]));
sumB++;
}
opr[p]++;
}
else
{
if (p == 2)
{
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}
else
{
p++;
opr[p] = add;
}
}
}
}
else
{
if (pds[p] >= cnt)
{
if (p == 3)
{
p--;
opr[p]++;
}
else if (p == 4)
{
p--;
used[pds[p]] = 0; // 释放当前操作数
// 搜索直到第一个可用数或出界
pds[p]++;
while (pds[p] < cnt)
{
if (used[pds[p]]) pds[p]++;
else break;
}
}
else // p==1
{
p--; // p <== 0 will exit while (p > 0);
}
}
else
{
used[pds[p]] = 1;
exp[p] = datas[pds[p]];
exp_t[p] = number;
if (p == 1 || p == 4)
{
p++;
opr[p] = add;
}
else // p==0 || p==3
{
p++;
pds[p] = 0;
do
{
if (used[pds[p]]) pds[p]++;
else break;
}
while (pds[p] < cnt);
}
}
}
}
while (p > 0);
}
if (sumA + sumB == 0)
{
printf("NOT found any solution\n\n");
}
else
{
printf("A form: %d B form: %d\n\n", sumA, sumB);
printf("merged infix expression : %d\n\n", cnt_stdInfixs);
for (i=0; i<cnt_stdInfixs; i++) puts(stdInfixs[i]);
printf("\n\n");
}
}
return 0;
}