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

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

*問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{
			switch(*c)
			{
			case '+':
				d_push(D_POP + D_POP);
				break;
			case '-':
				d_push(-D_POP + D_POP);
				break;
			case '*':
				d_push(D_POP * D_POP);
				break;
			case '/':
				op = D_POP;
				if(op == 0.0)
					return ERROR_NUM;
				d_push(D_POP / op);
				break;
			case 'm':
				d_push(-D_POP);
				break;
			case 's':
				op=D_POP;
				if(op==4.0)
					d_push(2.0);
				else if(op > 0.0)
					d_push(sqrt(op));
				else
					return ERROR_NUM;
				break;
			case '!':
				op=D_POP;
				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':
				op=D_POP;
				if((int)ROUND(op) == op && op==4)
					d_push(op/9.0);
				else
					return ERROR_NUM;
				break;
			case '.':
				op=D_POP;
				if((int)ROUND(op) == 4)
					d_push(op/10.0);
				else
					return ERROR_NUM;
				break;
			default:
				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{\
			switch(*c)\
			{\
			case '+':\
				d_push(D_POP + D_POP);\
				break;\
			case '-':\
				d_push(-D_POP + D_POP);\
				break;\
			case '*':\
				d_push(D_POP * D_POP);\
				break;\
			case '/':\
				op = D_POP;\
				if(op == 0.0)\
					{ERR;}\
				d_push(D_POP / op);\
				break;\
			case 'm':\
				d_push(-D_POP);\
				break;\
			case 's':\
				op=D_POP;\
				if(op==4.0)\
					d_push(2.0);\
				else if(op > 0.0)\
					d_push(sqrt(op));\
				else\
					{ERR;}\
				break;\
			case '!':\
				op=D_POP;\
				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':\
				op=D_POP;\
				if((int)ROUND(op) == op && op==4)\
					d_push(op/9.0);\
				else\
					{ERR;}\
				break;\
			case '.':\
				op=D_POP;\
				if((int)ROUND(op) == 4)\
					d_push(op/10.0);\
				else\
					{ERR;}\
				break;\
			default:\
				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;
}
}}