「C-assign-2009-03-13」の編集履歴（バックアップ）一覧に戻る

C-assign-2009-03-13 - (2009/02/25 (水) 13:11:29) のソース

*問1
4つの4、4に対して様々な演算子を働かせて数を作る。

以下修正
#codehighlight(c){{
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>

#define LENGTH_OF_ARRAY(x) (sizeof(x)/sizeof((x)[0]))
#define PUT_ERROR(x) fprintf(stderr, (x))
#define ROUND(x) (floor((x) + 0.5))

#define IPOW0(x) 1
#define IPOW1(x) (x)
#define IPOW2(x) ((x)*(x))
#define IPOW3(x) ((x)*(x)*(x))
#define IPOW4(x) ((x)*(x)*(x)*(x))
#define IPOW5(x) ((x)*(x)*(x)*(x)*(x))
#define IPOW6(x) ((x)*(x)*(x)*(x)*(x)*(x))
#define IPOW7(x) ((x)*(x)*(x)*(x)*(x)*(x)*(x))
//#define IPOW7(x) ((x)*(x)*(x)*(x)*(x)*(x)*(x)*(x))

#define STACK_SIZE 64
#define STR_LENGTH 128

double factorial(double x);
int isBinOp(char c);
void d_init(void);
double calc(char *const str);

void s_init(void);
void s_push(char *const str);
char* s_pop();

void toInfix(char *const exp, char *const target);
int makeRPNExp(char *const exp);
void search(char result[][STR_LENGTH]);


const double ERROR_NUM = 1000000.0;
const char* ERROR_OVFLOW = "STACK overflow.\n";
const char* ERROR_NOBODY = "Nakani daremo imasen yo.\n";
const char* STR_NODATA = "Data Empty";
const int SEARCH_RANGE = 114;

const char bin_op[] = "*/+-";
const char uni_op[] = "_sm!.n"; //除く
// m:minus, s:sqrt
// 4.4や4.44 can't be in Z
// .4~==4/9 so n:devide with 9

//const char* const EXP_TYPE[] = {
//	 "4  4  %c  4  %c  4  %c  "
//	,"4  4  %c  4  4  %c  %c  "
//	,"4  4  4  %c  %c  4  %c  "
//	,"4  4  4  %c  4  %c  %c  "
//	,"4  4  4  4  %c  %c  %c  "
//};
const char* const EXP_TYPE[] = {
	 "4 4 %c 4 %c 4 %c "
	,"4 4 %c 4 4 %c %c "
	,"4 4 4 %c %c 4 %c "
	,"4 4 4 %c 4 %c %c "
	,"4 4 4 4 %c %c %c "
};
int ipower(int x, int p)
{
	int a=1;
	for(; p; --p)
		a *= x;
	return a;
}
double factorial(double x)
{
	int i, ix;
	double result = 1.0;
	ix = (int)ROUND(x);
	for(i=1; i<=ix; ++i)
		result *= i;
	return result;
}

int isBinOp(char c)
{
	char const *ptr;
	for(ptr = bin_op; *ptr; ++ptr)
		if(*ptr==c)
			return 1;
	return 0;
}
//this should be template

typedef struct DOUBLE_STACK{
	double stack[STACK_SIZE];
	unsigned int index;
} d_stack;

d_stack ds;
#define D_INIT ds.index = 0
//void d_push(double x)
//{
//	if(ds.index < STACK_SIZE)
//		ds.stack[(ds.index)++] = x;
//	else
//		PUT_ERROR(ERROR_OVFLOW);
//}
#define d_push(x) (ds.stack[(ds.index)++] = (x))
//#define D_POP ((ds.index) ? ds.stack[--(ds.index)] : (PUT_ERROR(ERROR_NOBODY),ERROR_NUM))
#define D_POP (ds.stack[--(ds.index)])

double calc(char *const str)
{
	char *c;
	double op;
	D_INIT;

	for(c = str; *c; ++c)
	{
		if(isdigit(*c))
			d_push((double)(*c-'0'));
		else{
			op = D_POP;
			switch(*c)
			{
			case '+':
				d_push(D_POP + op);
				break;
			case '-':
				d_push(D_POP - op);
				break;
			case '*':
				d_push(D_POP * op);
				break;
			case '/':
				if(op == 0.0)
					return ERROR_NUM;
				d_push(D_POP / op);
				break;
			case 'm':
				d_push(-op);
				break;
			case 's':
				if(op==4.0)
					d_push(2.0);
				else if(op > 0.0)
					d_push(sqrt(op));
				else
					return ERROR_NUM;
				break;
			case '!':
				if(op==4.0)
					d_push(24.0);
				else if(op>0.0 && ROUND(op) == op)
					d_push(factorial(op));
				else
					return ERROR_NUM;
				break;
			case 'n':
				if((int)ROUND(op) == op && op==4)
					d_push(op/9.0);
				else
					return ERROR_NUM;
				break;
			case '.':
				if((int)ROUND(op) == 4)
					d_push(op/10.0);
				else
					return ERROR_NUM;
				break;
			default:
				d_push(op);
				break;
			}
		}
	}
	return D_POP;
}

typedef struct STR_STACK{
	char stack[STACK_SIZE][STR_LENGTH];
	unsigned int index;
} s_stack;

s_stack ss;
void s_init(void)
{
	ss.index = 0;
}
void s_push(char *const str)
{
	if(ss.index < STACK_SIZE)
		sprintf(ss.stack[(ss.index)++], "%s", str);
	else
		PUT_ERROR(ERROR_OVFLOW);
}
char* s_pop()
{
	return (ss.index)
		? ss.stack[--(ss.index)] : (PUT_ERROR(ERROR_NOBODY), (char *)NULL);
}

void toInfix(char *const exp, char *const target)
{
	char temp[STR_LENGTH];
	char *c;	// pointer for char[] exp
	s_init();
	for(c = exp; *c; ++c)
	{
		if(isdigit(*c))
			sprintf(temp, "%c", *c);
		else if(isBinOp(*c))
			sprintf(temp, "(%s %c %s)", s_pop(), *c, s_pop());
		else if(*c == '.')
			sprintf(temp, "%c%s", *c, s_pop());
		else if(*c == 'm')
			sprintf(temp, "-%s", s_pop());
		else if(*c == 's')
			sprintf(temp, "sqrt(%s)", s_pop());
		else if(*c == '!')
			sprintf(temp, "%s%c", s_pop(), *c);
		else if(*c == 'n')
			sprintf(temp, ".%s~", s_pop());
		else
			strcpy(temp, s_pop());
		s_push(temp);
	}
	strcpy(target, temp);
}

int makeRPNExp(char *const exp)
{
#define LNB (LENGTH_OF_ARRAY(bin_op)-1)
	static int idx_bin, idx_uni, idx_exp; // init with zero
	const static int ln_b = LNB;
	const static int ln_max = (LNB)*(LNB)*(LNB) - 1;
#undef LNB
#define LNU (LENGTH_OF_ARRAY(uni_op)-1)
	//there are 3 bin-ops in exp is the reason why LNB is powered with 3
	//int i;
	//const static int ln_exp = strlen(EXP_TYPE[0])/2;

	if(idx_exp==LENGTH_OF_ARRAY(EXP_TYPE))
		++idx_uni, idx_exp = 0;
	if(idx_uni==IPOW7(LNU) - 1)
		++idx_bin, idx_uni = 0;

	//二項演算子の代入
	sprintf(exp, EXP_TYPE[idx_exp] ,
		bin_op[idx_bin%ln_b],
		bin_op[(idx_bin / ln_b) % ln_b],
		bin_op[(idx_bin / ln_b / ln_b) % ln_b]);

	//単項演算子の挿入
#define INPUT_SINGLE(x) (exp[(x)*2+1] = uni_op[(idx_bin / IPOW##x(LNU)) % LNU])
	INPUT_SINGLE(0);
	INPUT_SINGLE(1);
	INPUT_SINGLE(2);
	INPUT_SINGLE(3);
	INPUT_SINGLE(4);
	INPUT_SINGLE(5);
	INPUT_SINGLE(6);
#undef INPUT_SINGLE

	++idx_exp;
	return (idx_bin == ln_max && idx_uni==IPOW7(LNU) - 1 && idx_exp==LENGTH_OF_ARRAY(EXP_TYPE)) ?
		0 : 1;
#undef LNU
}

void search(char result[][STR_LENGTH])
{
	char rpn_exp[STR_LENGTH]; // Reverse Polish Notation Expression
	char inf_exp[STR_LENGTH]; // Infix notation Expression
	double answer;
	int i_answer;
	int fill_counter=SEARCH_RANGE;

	while(makeRPNExp(rpn_exp) && fill_counter)
	{
		answer = calc(rpn_exp);
		i_answer = (int)ROUND(answer);
		if(answer == i_answer
			&& 0 <= i_answer
			&& i_answer < SEARCH_RANGE
			&& result[i_answer][0] == STR_NODATA[0]
		){
			toInfix(rpn_exp, inf_exp);
			strcpy(result[i_answer], inf_exp);
			--fill_counter;
			printf("%d:%s,%s\n", i_answer, rpn_exp, inf_exp);
		}
	}
}

void test(char *a)
{
	char b[256];
	double x;
	x = calc(a);
	toInfix(a, b);
	printf("RPN:%s\n"
		"INF:%s\n"
		"RESULT:%f\n", 
		a, b, x);
}

int main(int argc, char* argv[])
{
#if 0
	test("44*4+");
	test("44+4/");
	test("11-4+");
	test("44/4*");
	test("4!");
	test("4m");
	test("4ms");
	test("4s");
	test("4.");
	test("4n");
	printf("4! = %f", factorial(4.0));
#endif
#if 0
	test("4!4_4s4_-_*_/_");
	test("4s4!4!/_-_4_-_");
	test("4_4!4s*_-_4_/_");
	test("4!4s4_-_4_/_*_");
	test("4!4s-m4_4_/_+_");
	test("4s4_4!4_/_*_-_");
	test("4!4s4s4_-_/_/_");
#endif
#if 1
	char result[SEARCH_RANGE][STR_LENGTH];
	int i;

	for(i=0; i<SEARCH_RANGE; ++i)
		strcpy(result[i], STR_NODATA);

	search(result);

	for(i=0; i<SEARCH_RANGE; ++i)
		printf("%2d : %s\n",i, result[i]);
#endif
	return 0;
}
}}

下は主たる関数全部マクロ展開の狂気版
#codehighlight(c){{
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>

#define LENGTH_OF_ARRAY(x) (sizeof(x)/sizeof((x)[0]))
#define PUT_ERROR(x) fprintf(stderr, (x))
#define ROUND(x) (floor((x) + 0.5))

#define IPOW0(x) 1
#define IPOW1(x) (x)
#define IPOW2(x) ((x)*(x))
#define IPOW3(x) ((x)*(x)*(x))
#define IPOW4(x) ((x)*(x)*(x)*(x))
#define IPOW5(x) ((x)*(x)*(x)*(x)*(x))
#define IPOW6(x) ((x)*(x)*(x)*(x)*(x)*(x))
#define IPOW7(x) ((x)*(x)*(x)*(x)*(x)*(x)*(x))
//#define IPOW7(x) ((x)*(x)*(x)*(x)*(x)*(x)*(x)*(x))

#define STACK_SIZE 64
#define STR_LENGTH 128

double factorial(double x);
int isBinOp(char c);
double calc(char *const str);

void s_init(void);
void s_push(char *const str);
char* s_pop();

void toInfix(char *const exp, char *const target);
int makeRPNExp(char *const exp);
void search(char result[][STR_LENGTH]);


const double ERROR_NUM = 1000000.0;
const char* ERROR_OVFLOW = "STACK overflow.\n";
const char* ERROR_NOBODY = "Nakani daremo imasen yo.\n";
const char* STR_NODATA = "Data Empty";
const int SEARCH_RANGE = 114;

const char bin_op[] = "*/+-";
const char uni_op[] = "_sm!.n"; //除く
// m:minus, s:sqrt
// 4.4や4.44 can't be in Z
// .4~==4/9 so n:devide with 9

const char* const EXP_TYPE[] = {
  "4 4 %c 4 %c 4 %c "
  ,"4 4 %c 4 4 %c %c "
  ,"4 4 4 %c %c 4 %c "
  ,"4 4 4 %c 4 %c %c "
  ,"4 4 4 4 %c %c %c "
};
double factorial(double x)
{
  int i, ix;
  double result = 1.0;
  ix = (int)ROUND(x);
  for(i=1; i<=ix; ++i)
    result *= i;
  return result;
}

int isBinOp(char c)
{
  char const *ptr;
  for(ptr = bin_op; *ptr; ++ptr)
    if(*ptr==c)
      return 1;
  return 0;
}
//this should be template

typedef struct DOUBLE_STACK{
  double stack[STACK_SIZE];
  unsigned int index;
} d_stack;

d_stack ds;
#define d_init (ds.index = 0)
//void d_push(double x)
//{
//	if(ds.index < STACK_SIZE)
//		ds.stack[(ds.index)++] = x;
//	else
//		PUT_ERROR(ERROR_OVFLOW);
//}
#define d_push(x) (ds.stack[(ds.index)++] = (x))
//#define D_POP ((ds.index) ? ds.stack[--(ds.index)] : (PUT_ERROR(ERROR_NOBODY),ERROR_NUM))
#define D_POP (ds.stack[--(ds.index)])

#define ERR answer = ERROR_NUM;goto ERROR
#define CALC					\
  d_init;					\
  for(c = rpn_exp; *c; ++c)			\
    {						\
      if(isdigit(*c))				\
	d_push((double)(*c-'0'));		\
      else{					\
	op = D_POP;				\
	switch(*c)				\
	  {					\
	  case '+':				\
	    d_push(D_POP + op);			\
	    break;				\
	  case '-':				\
	    d_push(D_POP - op);			\
	    break;				\
	  case '*':				\
	    d_push(D_POP * op);			\
	    break;				\
	  case '/':				\
	    if(op == 0.0)			\
	      {ERR;}				\
	    d_push(D_POP / op);			\
	    break;				\
	  case 'm':				\
	    d_push(-op);			\
	    break;				\
	  case 's':				\
	    if(op==4.0)				\
	      d_push(2.0);			\
	    else if(op > 0.0)			\
	      d_push(sqrt(op));			\
	    else				\
	      {ERR;}				\
	    break;				\
	  case '!':				\
	    if(op==4.0)				\
	      d_push(24.0);			\
	    else if(op>0.0 && ROUND(op) == op)	\
	      d_push(factorial(op));		\
	    else				\
	      {ERR;}				\
	    break;				\
	  case 'n':				\
	    if((int)ROUND(op) == op && op==4)	\
	      d_push(op/9.0);			\
	    else				\
	      {ERR;}				\
	    break;				\
	  case '.':				\
	    if((int)ROUND(op) == 4)		\
	      d_push(op/10.0);			\
	    else				\
	      {ERR;}				\
	    break;				\
	  default:				\
	    d_push(op);				\
	    break;				\
	  }					\
      }						\
    }						\
  answer = D_POP;				\
ERROR:

typedef struct STR_STACK{
  char stack[STACK_SIZE][STR_LENGTH];
  unsigned int index;
} s_stack;

s_stack ss;
void s_init(void)
{
  ss.index = 0;
}
void s_push(char *const str)
{
  if(ss.index < STACK_SIZE)
    sprintf(ss.stack[(ss.index)++], "%s", str);
  else
    PUT_ERROR(ERROR_OVFLOW);
}
char* s_pop()
{
  return (ss.index)
    ? ss.stack[--(ss.index)] : (PUT_ERROR(ERROR_NOBODY), (char *)NULL);
}

void toInfix(char *const exp, char *const target)
{
  char temp[STR_LENGTH];
  char *c;	// pointer for char[] exp
  s_init();
  for(c = exp; *c; ++c)
    {
      if(isdigit(*c))
	sprintf(temp, "%c", *c);
      else if(isBinOp(*c))
	sprintf(temp, "(%s %c %s)", s_pop(), *c, s_pop());
      else if(*c == '.')
	sprintf(temp, "%c%s", *c, s_pop());
      else if(*c == 'm')
	sprintf(temp, "-%s", s_pop());
      else if(*c == 's')
	sprintf(temp, "sqrt(%s)", s_pop());
      else if(*c == '!')
	sprintf(temp, "%s%c", s_pop(), *c);
      else if(*c == 'n')
	sprintf(temp, ".%s~", s_pop());
      else
	strcpy(temp, s_pop());
      s_push(temp);
    }
  strcpy(target, temp);
}

#define LNU (LENGTH_OF_ARRAY(uni_op)-1)
#define INPUT_SINGLE(x) (rpn_exp[(x)*2+1] = uni_op[(idx_bin / IPOW##x(LNU)) % LNU])
#define MAKERPNEXP					\
  {							\
    if(idx_exp==LENGTH_OF_ARRAY(EXP_TYPE))		\
      ++idx_uni, idx_exp = 0;				\
    if(idx_uni==IPOW7(LNU) - 1)				\
      ++idx_bin, idx_uni = 0;				\
    sprintf(rpn_exp, EXP_TYPE[idx_exp] ,		\
	    bin_op[idx_bin%ln_b],			\
	    bin_op[(idx_bin / ln_b) % ln_b],		\
	    bin_op[(idx_bin / ln_b / ln_b) % ln_b]);	\
    INPUT_SINGLE(0);					\
    INPUT_SINGLE(1);					\
    INPUT_SINGLE(2);					\
    INPUT_SINGLE(3);					\
    INPUT_SINGLE(4);					\
    INPUT_SINGLE(5);					\
    INPUT_SINGLE(6);					\
    ++idx_exp;						\
  }

void search(char result[][STR_LENGTH])
{
  char rpn_exp[STR_LENGTH]; // Reverse Polish Notation Expression
  char inf_exp[STR_LENGTH]; // Infix notation Expression
  double answer;
  int i_answer;
  int fill_counter=SEARCH_RANGE;
  // calc
  char *c;
  double op;
  // makeRPNexp
#define LNB (LENGTH_OF_ARRAY(bin_op)-1)
  static int idx_bin, idx_uni, idx_exp; // init with zero
  const static int ln_b = LNB;
  const static int ln_max = (LNB)*(LNB)*(LNB) - 1;
#undef LNB

  while(fill_counter)
    {
      MAKERPNEXP;
      CALC;
      i_answer = (int)ROUND(answer);
      if(answer == i_answer
	 && 0 <= i_answer
	 && i_answer < SEARCH_RANGE
	 && result[i_answer][0] == STR_NODATA[0]
	 ){
	toInfix(rpn_exp, inf_exp);
	strcpy(result[i_answer], inf_exp);
	--fill_counter;
	printf("%d:%s,%s\n", i_answer, rpn_exp, inf_exp);
      }
    }
}

int main(int argc, char* argv[])
{
#if 1
  char result[SEARCH_RANGE][STR_LENGTH];
  int i;

  for(i=0; i<SEARCH_RANGE; ++i)
    strcpy(result[i], STR_NODATA);

  search(result);

  for(i=0; i<SEARCH_RANGE; ++i)
    printf("%2d : %s\n",i, result[i]);
#endif
  return 0;
}
}}