24点.cpp

给定四个数（1--13）

#include <stdio.h>
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( )
{
   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;
}