alabama_country @Wiki

C-assign-2009-03-13

最終更新：2009年02月28日 20:19

alabama_country

- view

管理者のみ編集可

問1

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

計算を手抜きした版を上に、実直な版を下に添える。

#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 numbers[] = "4SM?.N";
const char bin_op[] = "*/+-";
const char uni_op[] = "_s"; // m!除く
// m:minus, s:sqrt
// 4.4や4.44 can't be in Z
// .4~==4/9 so n:devide with 9
 
struct EXP_BASE
{
	int bin_position[3];
	int num_position[4];
	int uni_position[2];
};
 
const char * EXP_BASE_STRING[] ={
	"44$@4$@4$",
	"444$@$@4$",
	"444$@4$@$",
	"4444$@$@$",
	"44$@44$@$",
};
 
struct EXP_BASE exp_base[LENGTH_OF_ARRAY(EXP_BASE_STRING)];
 
void exp_base_init(const char *pstr[], int length, struct EXP_BASE *target)
{
	int i, j;
	int c_n, c_u, c_b;
	const char *c;
	for(i = 0; i < length; ++i)
	{
		for(c = pstr[i], j = c_n = c_u = c_b = 0; c[j]; ++j)
		{
			switch(c[j])
			{
			case '4':
				target[i].num_position[c_n++] = j;
				break;
			case '@':
				target[i].uni_position[c_u++] = j;
				break;
			case '$':
				target[i].bin_position[c_b++] = j;
				break;
			default:
				break;
			}
		}
	}
}
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))
double d_pop(void)
{
	return (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(4.0);
		else{
			switch(*c)
			{
			case 'M':
				d_push(-4.0); /*dump*/
				break;
			case 'S':
				d_push(2.0); /*dump*/
				break;
			case '?':
				d_push(24.0); /*dump*/
				break;
			case 'N':
				d_push(4.0/9.0);
				break;
			case '.':
				d_push(0.4);
				break;
			case 'm':
				d_push(-d_pop());
				break;
			case 's':
				op = d_pop();
				if( op < 0.0)
					return ERROR_NUM;
				else
					d_push(sqrt(op));
				break;
			case '!':
				op = d_pop();
				if(op != ROUND(op) || op < 0.0)
					return ERROR_NUM;
				else
					d_push(factorial(op));
				break;
			case '+':
				d_push(d_pop() + d_pop());
				break;
			case '-':
				op = d_pop();
				d_push(d_pop() - op);
				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;
			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
		{
			switch(*c)
			{
			case '.':
				sprintf(temp, ".4");
				break;
			case 'N':
				sprintf(temp, ".4~");
				break;
			case 'M':
				sprintf(temp, "-4");
				break;
			case 'S':
				sprintf(temp, "sqrt(4)");
				break;
			case '?':
				sprintf(temp, "4!");
				break;
			case 'm':
				sprintf(temp, "-(%s)", s_pop());
				break;
			case 's':
				sprintf(temp, "sqrt(%s)", s_pop());
				break;
			case '!':
				sprintf(temp, "(%s)%c", s_pop(), *c);
				break;
			default:
				if(isBinOp(*c))
					sprintf(temp, "(%s %c %s)", s_pop(), *c, s_pop());
				else
					strcpy(temp, s_pop());
				break;
			}
		}
		s_push(temp);
	}
	strcpy(target, temp);
}
 
int makeRPNExp(char *const exp)
{
#define LNB (LENGTH_OF_ARRAY(bin_op)-1)
	static int idx_bin, idx_num, idx_exp; // init with zero
	static int idx_uni;
	const static int ln_b = LNB;
	const static int ln_max = IPOW3(LNB) - 1;
	//there are 3 bin-ops in exp is the reason why LNB is powered with 3
#undef LNB
 
#define LNU (LENGTH_OF_ARRAY(uni_op) - 1)
#define LNN (LENGTH_OF_ARRAY(numbers) - 1)
 
	if(idx_exp==LENGTH_OF_ARRAY(exp_base))
		++idx_num, idx_exp = 0;
	if(idx_num==IPOW4(LNN) - 1)
		++idx_uni, idx_num = 0;
	if(idx_uni==IPOW2(LNU) - 1)
		++idx_bin, idx_uni = 0;
 
	//二項演算子の代入
	strcpy(exp, EXP_BASE_STRING[0]);
	//どうせ全ての項目を後で代入してしまうので、領域が確保されている以上strcpyが無駄。
	//と思いきや\0の問題が…仕方ないのできまりきった文字列をコピペすることに
	//つまり、EXP_BASE::stringはお飾り
#define INPUT_BINARY(x) exp[exp_base[idx_exp].bin_position[x]] = bin_op[(idx_bin / IPOW##x(ln_b)) % ln_b]
	INPUT_BINARY(0);
	INPUT_BINARY(1);
	INPUT_BINARY(2);
#undef INPUT_BINARY
 
	//数字オブジェクトの挿入
#define INPUT_NUM(x) exp[exp_base[idx_exp].num_position[x]] = numbers[(idx_num / IPOW##x(LNN)) % LNN]
	INPUT_NUM(0);
	INPUT_NUM(1);
	INPUT_NUM(2);
	INPUT_NUM(3);
#undef INPUT_NUM
 
	//単項演算子の代入
#define INPUT_SINGLE(x) exp[exp_base[idx_exp].uni_position[x]] = uni_op[(idx_uni / IPOW##x(LNU)) % LNU]
	//#define INPUT_SINGLE(x) exp[exp_base[idx_exp].uni_position[x]] = '_'
	INPUT_SINGLE(0);
	INPUT_SINGLE(1);
#undef INPUT_SINGLE
 
	++idx_exp;
	return (idx_bin == ln_max
		&& idx_num == IPOW4(LNN) - 1
		&& idx_uni == IPOW2(LNU) - 1
		&& idx_exp==LENGTH_OF_ARRAY(exp_base)) ?
		0 : 1;
#undef LNU
#undef LNN
}
 
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[])
{
	exp_base_init(EXP_BASE_STRING, LENGTH_OF_ARRAY(EXP_BASE_STRING), exp_base);
#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;
}

#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 = 31; //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))
double d_pop(void)
{
	return (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;
}

タグ：

C言語

「C-assign-2009-03-13」をウィキ内検索

alabama_country @Wiki

記事メニュー

最近更新されたページ

人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう！

全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう！