代码： 全选
#include <stdio.h>
void Hello( )
{
puts("\n");
puts(" ##################################################");
puts(" ## ##");
puts(" ## ２４点程序 ##");
puts(" ## ##");
puts(" ##################################################");
puts(" ## ##");
puts(" ## 输入４个整数，用它们构造一个算术四则运算， ##");
puts(" ## 使结果等于２４。每个数恰好利用一次。 ##");
puts(" ## ##");
puts(" ## 例如，输入为 ２ ７ １０ ６ ##");
puts(" ## 输出为（２＋６）x（１０－７） ##");
puts(" ## …… ##");
puts(" ## …… ##");
puts(" ## （可输出有重复的全部解） ##");
puts(" ## ##");
puts(" ##################################################");
puts(" ## ##");
puts(" ## 设计者：老汉推车 ##");
puts(" ## 时 间：2012-4-29 ##");
puts(" ## ##");
puts(" ##################################################");
puts("\n");
}
const int N = 4; // 操作数的个数/栈的极限高度
#define eps 1E-6 // 浮点精度
inline float abs(float x) { return x >= 0.0 ? x : -x; }
// 栈模板
template <class T, int N> class STACK {
protected:
T a[N]; // 栈的存储体
int n; // 栈的高度/未来栈顶位置
public:
STACK( ) { reset( ); } // 栈初始化
void reset( ) { n = 0; } // 清空栈
void push(T x) { if(n < N) a[n++] = x; else puts("栈上溢"); } // 压入数据到栈顶
T pop( ) { if(n > 0) return a[--n]; else puts("栈下溢"); } // 弹出栈顶数据
// T top( ) { if(n > 0) return a[n-1]; else puts("栈空"); } // 查询栈顶元素
// bool isempty( ) { return n == 0; } // 查询栈是否为空
// int heigth( ) { return n; } // 查询栈的高度
};
const char opr[ ] = "+-*/";
int a[N]; // 输入的4个数
STACK<float, N> opnstk; // 操作数栈
int b[N], K = 0; // a[]的备份/用于生产排列的工作区
void gen(int n, int m) // 生成n个数中取m个数的全排列。m = n时即为n个数的全排列。---
{ // --- 每产生一个排列，放入b[]中。
void gen24( ); // 函数声明
int i;
if(m == 0) {
// for(i = 0; i < K; ++i) printf("%d ", b[i]); putchar('\n'); // 如果只是为了输出排列
gen24( ); // 函数调用
}
else
for(i = 0; i < n; ++i) if(a[i] != '.') {
b[K++] = a[i];
a[i] = '.';
gen(n, m - 1);
a[i] = b[--K];
}
}
// 用后缀表达式计算，用中缀表达式输出。
// --- n表示将一个操作数压栈，#表示进行一步运算。
// --- abcd指操作数的输出顺序，123指运算符的输出顺序。
const char stkmode[5][22] = {
"nnnn### = a3(b2(c1d))",
"nnn#n## = a3((b1c)2d)",
"nnn##n# = (a2(b1c))3d",
"nn#nn## = (a1b)3(c2d)",
"nn#n#n# = ((a1b)2c)3d",
};
void gen24( ) // 用b[]中的4个数产生等于24的算式
{
bool calc(float, char, float, float&); // 函数声明
int i, jn, jo, p0, p1, p2;
char enumopr[3], op;
float a1, a2, c;
const char *p;
// for(i = 0; i < K; ++i) printf("%d ", b[i]); putchar('\n'); // 如果只是为了输出排列
for(i = 0; i < 5; ++i) // 尝试每种栈模式
for(p0 = 0; p0 < 4; ++p0) { enumopr[0] = opr[p0];
for(p1 = 0; p1 < 4; ++p1) { enumopr[1] = opr[p1];
for(p2 = 0; p2 < 4; ++p2) { enumopr[2] = opr[p2];
opnstk.reset( );
for(jn = jo = 0, p = stkmode[i]; *p != ' '; ++p) switch(*p) {
case 'n':
opnstk.push(b[jn++]); break;
case '#':
a2 = opnstk.pop( ); a1 = opnstk.pop( ); op = enumopr[jo++];
if(calc(a1, op, a2, c)) opnstk.push(c); else goto loc_1;
}
if(abs(c - 24) < eps) {
while(*++p != 0) switch(*p) {
case '(':
case ')':
putchar(*p);
break;
case 'a':
case 'b':
case 'c':
case 'd':
printf("%d", b[*p - 'a']);
break;
case '1':
case '2':
case '3':
printf("%c", enumopr[*p - '1']);
break;
}
putchar('\n');
goto loc_2;
}
loc_1: continue;
}}}
loc_2: return;
}
bool calc(float a, char op, float b, float& c)
{
static bool bRet;
switch(bRet = true, op) {
case '+': c = a + b; break;
case '-': c = a - b; break;
case '*': c = a * b; break;
case '/':
if(abs(b) > eps) c = a / b; else bRet = false;
}
return bRet;
}
int main( )
{
Hello( );
while(true) {
printf("请输入%d个整数（用空白分隔。结束程序请输入0）: ", N);
for(int i = 0; i < N; ++i) { scanf("%d", &a[i]); if(a[i] == 0) goto loc_0; }
K = 0; gen(N, N);
}
loc_0: return 0;
}
