#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <ctype.h>
#include <conio.h>
#define CARD_COUNT 52
#define CARD_SUM 4
#define GOAL_SCORE 24
#define HEART 0
#define SPADE 1
#define DIAMOND 2
#define CLUB 3

/*结构体：卡牌*/
typedef struct
{
	unsigned char color:2;
	unsigned char face:4;
}Card;

/*结构体：牌叠*/
typedef struct
{
	int top;
	Card *cards;
}Pile;

/*结构体：表达式计算时使用的栈*/
typedef struct
{
	int depth_op;
	int depth_num;
	char *operators;
	float *numbers;
}Cal_Stack;

/*结构体：回溯时使用的树节点*/
typedef struct
{
	char parent;
	char lchild;
	char rchild;
	char op;
	float val;
}Cal_Tree;

/*过程：调试时使用，将目标字符串输出到trace.txt*/
void trace(char* text)
{
 	FILE *file=fopen("trace.txt","at+");
	fwrite(text,strlen(text)*sizeof(char),1,file);
	fclose(file);
}

/*cls函数：来自MSDN*/
#define PERR(bSuccess, api){if(!(bSuccess)) printf("%s:Error %d from %s on line %d\n", __FILE__, GetLastError(), api, __LINE__);}
void cls( HANDLE hConsole )
	{
	COORD coordScreen = { 0, 0 }; /* here's where we'll home the cursor */
	BOOL bSuccess;
	DWORD cCharsWritten;
	CONSOLE_SCREEN_BUFFER_INFO csbi; /* to get buffer info */
	DWORD dwConSize; /* number of character cells in the current buffer */
	/* get the number of character cells in the current buffer */
	bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi );
	PERR( bSuccess, "GetConsoleScreenBufferInfo" );
	dwConSize = csbi.dwSize.X * csbi.dwSize.Y;
	/* fill the entire screen with blanks */
	bSuccess = FillConsoleOutputCharacter( hConsole, (TCHAR) ' ',
	dwConSize, coordScreen, &cCharsWritten );
	PERR( bSuccess, "FillConsoleOutputCharacter" );
	/* get the current text attribute */
	bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi );
	PERR( bSuccess, "ConsoleScreenBufferInfo" );
	/* now set the buffer's attributes accordingly */
	bSuccess = FillConsoleOutputAttribute( hConsole, csbi.wAttributes,
	dwConSize, coordScreen, &cCharsWritten );
	PERR( bSuccess, "FillConsoleOutputAttribute" );
	/* put the cursor at (0, 0) */
	bSuccess = SetConsoleCursorPosition( hConsole, coordScreen );
	PERR( bSuccess, "SetConsoleCursorPosition" );
	return;
}

/*过程：初始化牌叠*/
void initCards(Pile *pile)
{
	int i,j;
	pile->top=0;
	pile->cards=(Card*)malloc(sizeof(Card)*CARD_COUNT);
	for(i=0,j=HEART-1;i<CARD_COUNT;i++)
	{
		if(i%13==0)j=(j+1)%4;
		pile->cards[i].color=j;
		pile->cards[i].face=(i%13)+1;
	}
}

/*过程：删除牌叠*/
void delCards(Pile *pile)
{
	free(pile->cards);
	free(pile);
}

/*过程：洗牌*/
void shuffleCards(Pile *pile)
{
	int i,j;
	srand((int)time(0));
	for(i=0;i<CARD_COUNT;i++)
	{
		j=rand()%CARD_COUNT;
		if(i==j)continue;
		pile->cards[i].color^=pile->cards[j].color;
		pile->cards[j].color^=pile->cards[i].color;
		pile->cards[i].color^=pile->cards[j].color;
		pile->cards[i].face^=pile->cards[j].face;
		pile->cards[j].face^=pile->cards[i].face;
		pile->cards[i].face^=pile->cards[j].face;
	}
	pile->top=0;
}

/*过程：发牌*/
void dealCards(Pile *pile,Card *cards,int n)
{
	int i;
	if(CARD_COUNT-pile->top<n)
		shuffleCards(pile);
	for(i=0;i<n;i++,pile->top++)
	{
		cards[i].color=pile->cards[pile->top].color;
		cards[i].face=pile->cards[pile->top].face;
	}
}

/*过程：展示牌*/
void showCards(Card *cards,int n)
{
	int i,j;
	COORD c1,c2;/*存储光标位置*/
	CONSOLE_SCREEN_BUFFER_INFO bInfo;/*存储控制台窗口信息（包括光标位置）*/
	/*显示牌的框架*/
	for(i=0;i<n;i++)
		printf("┏━━┓");
	printf("\n");
	for(j=0;j<3;j++)
	{
		for(i=0;i<n;i++)
			printf("┃    ┃");
		printf("\n");
	}
	for(i=0;i<n;i++)
		printf("┗━━┛");
	printf("\n");
	GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &bInfo);/*获取控制台窗口信息*/
	/*获取并修改光标位置*/
	c1.X=bInfo.dwCursorPosition.X;
	c1.Y=bInfo.dwCursorPosition.Y;
	c2.Y=c1.Y-3;
	c2.X=c1.X+3;
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c2);/*定位光标到上面*/
	/*显示牌的花色与点数*/
	for(i=0;i<n;i++)
	{
		switch(cards[i].color)
		{
			case HEART:
				printf("\3");
				break;
			case SPADE:
				printf("\6");
				break;
			case DIAMOND:
				printf("\4");
				break;
			case CLUB:
				printf("\5");
				break;
		}
		switch(cards[i].face)
		{
			case 13:
				printf("K");
				break;
			case 12:
				printf("Q");
				break;
			case 11:
				printf("J");
				break;
			case 1:
				printf("A");
				break;
			default:
				printf("%d",cards[i].face);
				break;
		}
		c2.X=c2.X+8;/*平移光标*/
		SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c2);
	}
	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c1);/*复位光标位置*/
}

/*过程：初始化表达式计算工作空间*/
void initCal(Cal_Stack *cal,int n)
{
	cal->depth_op=0;
	cal->depth_num=0;
	cal->numbers=(float*)malloc(sizeof(float)*n);
	cal->operators=(char*)malloc(sizeof(char)*n);
}

/*过程：删除表达式计算工作空间*/
void delCal(Cal_Stack *cal)
{
	free(cal->numbers);
	free(cal->operators);
	free(cal);
}

/*过程：数据入栈*/
void push_num(Cal_Stack *cal,float number)
{
	cal->numbers[cal->depth_num++]=number;
}

/*过程：操作符入栈*/
void push_op(Cal_Stack *cal,char op)
{
	cal->operators[cal->depth_op++]=op;
}

/*过程：数据出栈*/
void pop_num(Cal_Stack *cal)
{
	if(cal->depth_num>0)
		cal->depth_num--;
}

/*函数：取得栈顶数据*/
float top_num(Cal_Stack *cal)
{
	return cal->numbers[cal->depth_num-1];
}

/*过程：操作符出栈*/
void pop_op(Cal_Stack *cal)
{
	if(cal->depth_op>0)
		cal->depth_op--;
}

/*函数：取得栈顶操作符*/
char top_op(Cal_Stack *cal)
{
	return cal->operators[cal->depth_op-1];
}

/*函数：根据字符返回操作符索引*/
int get_idx(char op)
{
	switch(op)
	{
	case '+':
		return 0;
	case '-':
		return 1;
	case '*':
		return 2;
	case '/':
		return 3;
	case '(':
		return 4;
	case ')':
		return 5;
	default:
		return 6;
	}
}

/*函数：根据操作符索引取得操作符优先级*/
int get_priority(int idx,int in_stack)
{
	int t;
	switch(idx)
	{
	case 0:
	case 1:
		t=2;
		in_stack=in_stack==0?0:1;
		break;
	case 2:
	case 3:
		t=4;
		in_stack=in_stack==0?0:1;
		break;
	case 4:
		t=6;
		in_stack=in_stack==0?0:-5;
		break;
	case 5:
		t=6;
		in_stack=in_stack==0?-5:0;
		break;
	default:
		return 0;
	}
	return t+in_stack;
}

/*函数：根据数据及操作符计算值*/
float figure(float a,float b,char op)
{
	switch(op)
	{
	case 0:
		return a+b;
	case 1:
		return a-b;
	case 2:
		return a*b;
	case 3:
		if(b!=0)
			return a/b;
	default:
		return a;
	}
}

/*函数：取得绝对值*/
float Abs(float n)
{
	if(n<0)
		return -n;
	return n;
}

/*函数：判断浮点数是否足够相近*/
int equal(float a,float b)
{
	if(Abs(a-b)<1e-4)
		return 1;
	return 0;
}

/*函数，格式化字符串，失败返回-1*/
int format(char* buf)
{
	int offset=0;
	unsigned long q=0;//栈，存储未完成匹配的左括号
	while(*buf!=10)
	{
		while(*buf==' ')
		{
			offset++;
			buf++;
		}
		if(!(isdigit(*buf)))
		{
			switch(*buf)
			{
			case '+':
			case '-':
			case '*':
			case '/':
				break;
			case '(':/*对于左括号，入栈*/
				q|=(q<<1)+1;
				break;
			case ')':/*每遇到一个右括号，出栈一个左括号*/
				if((q&0X01)==0X01)
					q>>=1;
				else/*栈空，返回出错*/
					return -1;
				break;
			default:
				return -1;
			}
		}
		*(buf-offset)=*buf;
		buf++;
	}
	if(q!=0)/*栈没有完全清空(左括号过多)，返回出错*/
		return -1;
	*(buf-offset)=10;
	return 0;
}

/*函数：分析表达式与发出的牌，返回表达式正确性，正确返回1，错误返回0，表达式格式错误返回-1*/
int analysis(char* buf,Card *cards,int n)
{
	Cal_Stack* cal;
	float sum=0,a,b,*num;
	int flag=1,p1,p2,count=0,i;/*flag保存正负号信息*/
	char op;
	if(format(buf)==-1)
	{
		return -1;
	}
	cal=(Cal_Stack*)malloc(sizeof(Cal_Stack));
	initCal(cal,1024);
	push_op(cal,get_idx('#'));
	num=(float*)malloc(sizeof(float)*n);
	if(*buf=='-')
	{
		flag=0;
		buf++;
	}
	while(*buf!=10||top_op(cal)!=6)/*字符串未被读完或操作符栈未被清空*/
	{
		if(isdigit(*buf))/*读入数据*/
		{
			sum=0;
			if(flag!=0)
			{
				while(isdigit(*buf))
				{
					sum=sum*10+*buf-'0';
					buf++;
				}
			}
			else
			{
				while(isdigit(*buf))
				{
					sum=sum*10-*buf-'0';
					buf++;
				}
			}
			push_num(cal,sum);
			num[count++]=flag==0?-sum:sum;/*表达式中出现的数字全部记录下来，以便校验表达式合法性*/
			flag=1;
		}
		else/*读入操作符*/
		{
			p1=get_priority(top_op(cal),1);
			p2=get_priority(get_idx(*buf),0);
			if(p1>p2)/*根据优先级决定要执行的操作*/
			{
				b=top_num(cal);
				pop_num(cal);
				a=top_num(cal);
				pop_num(cal);
				op=top_op(cal);
				pop_op(cal);
				push_num(cal,figure(a,b,op));
			}
			else if(p1<p2)
			{
				push_op(cal,get_idx(*buf));
				if(*buf!=10)
					buf++;
			}
			else
			{
				pop_op(cal);
				if(*buf!=10)
					buf++;
			}
		}
	}
	for(i=0,a=1,b=1;i<n;i++)/*计算校验码*/
	{
		a*=cards[i].face;
		b*=num[i];
	}
	if(equal(a,b)==0)/*校验码不一致*/
	{
		printf("错误，必须使用给定的卡牌\n");
	}
	else if(equal(top_num(cal),GOAL_SCORE)==1)
	{
		printf("%d点！正确！\n",GOAL_SCORE);
		free(num);
		delCal(cal);
		return 1;
	}
	else
		printf("%.0f点,错误～\n",top_num(cal));
	free(num);
	delCal(cal);
	return 0;
}

/*过程：初始化树*/
void initTree(Cal_Tree *tree,Card *cards,int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		tree[i].lchild=-1;
		tree[i].rchild=-1;
		tree[i].parent=-1;
		tree[i].op=-1;
		tree[i].val=cards[i].face;
	}
	for(i=2*n-2;i>=n;i--)
	{
		tree[i].lchild=-1;
		tree[i].rchild=-1;
		tree[i].parent=-2;
		tree[i].op=-1;
		tree[i].val=0;
	}
}

/*过程：合并两个子树*/
void catTree(Cal_Tree *tree,int l,int r,int p,char op)
{
	tree[p].lchild=l;
	tree[p].rchild=r;
	tree[p].op=op;
	tree[p].val=figure(tree[l].val,tree[r].val,get_idx(op));
	tree[p].parent=-1;
	tree[l].parent=p;
	tree[r].parent=p;
}

/*过程：分离二叉树*/
void splitTree(Cal_Tree *tree,int n)
{
	tree[tree[n].lchild].parent=-1;
	tree[tree[n].rchild].parent=-1;
	tree[n].parent=-2;
}

/*过程：输出答案到缓冲区*/
void printAnswer(Cal_Tree *tree,char *buf,int *buf_size,int n)
{
	char f=0;/*记录是否需要加上括号*/
	if(*buf_size-strlen(buf)<1024)/*自动扩大缓冲区*/
	{
		realloc(buf,*buf_size*2);
		*buf_size+=*buf_size;
	}
	if(tree[tree[n].lchild].op=='+'||tree[tree[n].lchild].op=='-')
		f=1;
	if(f)
		sprintf(buf,"%s(",buf);
	if(tree[tree[n].lchild].lchild!=-1)
	{
		printAnswer(tree,buf,buf_size,tree[n].lchild);
	}
	else
	{
		sprintf(buf,"%s%.0f",buf,tree[tree[n].lchild].val);
	}
	if(f)
	{
		sprintf(buf,"%s)",buf);
		f=0;
	}
	sprintf(buf,"%s%c",buf,tree[n].op);
	if(tree[tree[n].rchild].op=='+'||tree[tree[n].rchild].op=='-')
		f=1;
	if(f)
		sprintf(buf,"%s(",buf);
	if(tree[tree[n].rchild].lchild!=-1)
	{
		printAnswer(tree,buf,buf_size,tree[n].rchild);
	}
	else
	{
		sprintf(buf,"%s%.0f",buf,tree[tree[n].rchild].val);
	}
	if(f)
		sprintf(buf,"%s)",buf);
}

/*过程：穷举+回溯，找到合理的解，并调用输出函数*/
void tryAnswer(Cal_Tree *tree,char *buf,int *buf_size,int n,int max,int goal)
{
	int i,j;
	if(n==max)
		if(equal(tree[n].val,goal))
		{
			printAnswer(tree,buf,buf_size,max);
			sprintf(buf,"%s\n",buf);
		}
	for(i=0;i<n;i++)
	{
		if(tree[i].parent!=-1)
			continue;
		for(j=i+1;j<=n;j++)
		{
			if(tree[j].parent!=-1)
				continue;
			catTree(tree,i,j,n+1,'+');
			tryAnswer(tree,buf,buf_size,n+1,max,goal);
			splitTree(tree,n+1);
			catTree(tree,i,j,n+1,'*');
			tryAnswer(tree,buf,buf_size,n+1,max,goal);
			splitTree(tree,n+1);
			catTree(tree,i,j,n+1,'-');
			tryAnswer(tree,buf,buf_size,n+1,max,goal);
			splitTree(tree,n+1);
			catTree(tree,j,i,n+1,'-');
			tryAnswer(tree,buf,buf_size,n+1,max,goal);
			splitTree(tree,n+1);
			if(equal(tree[j].val,0))
			{
				catTree(tree,i,j,n+1,'/');
				tryAnswer(tree,buf,buf_size,n+1,max,goal);
				splitTree(tree,n+1);
			}
			if(equal(tree[i].val,0))
			{
				catTree(tree,j,i,n+1,'/');
				tryAnswer(tree,buf,buf_size,n+1,max,goal);
				splitTree(tree,n+1);
			}
		}
	}
}

/*函数：回溯入口，返回存储答案的缓冲区*/
char* giveAnswer(Card *cards,int n)
{
	Cal_Tree *tree=(Cal_Tree*)malloc(sizeof(Cal_Tree)*(n*2-1));
	char *buf=(char*)malloc(sizeof(char)*65536);
	int *buf_size=(int*)malloc(sizeof(int));
	*buf_size=1024;
	initTree(tree,cards,n);
	strcpy(buf,"");
	tryAnswer(tree,buf,buf_size,n-1,n*2-2,GOAL_SCORE);
	free(tree);
	free(buf_size);
	return buf;
}

int main()
{
	Pile *pile=(Pile*)malloc(sizeof(Pile));
	Card cards[CARD_SUM];
	char buf[1024]={'\0'},*tmp;
	int flag;
	initCards(pile);
	shuffleCards(pile);
	printf("############################\n");
	printf("##--------二十四点--------##\n");
	printf("##  V1.02    By.ZaneYork  ##\n");
	printf("############################\n");
	while(1)
	{
		flag=0;
		if(buf[0]!='d')
		{
			printf("按任意键开始发牌\n");
			_getch();
		}
		else
			free(tmp);
		cls(GetStdHandle(STD_OUTPUT_HANDLE));
		while(1)/*对于无解的组合，重新发牌*/
		{
			dealCards(pile,cards,CARD_SUM);
			tmp=giveAnswer(cards,CARD_SUM);
			if(strcmp(tmp,"")>0)
				break;
		}
		showCards(cards,CARD_SUM);
		while(flag!=1)
		{
			printf("请输入算式：（输入：d.换牌 a.答案 c.清屏 q.退出）\n");
			fgets(buf,1024,stdin);
			if(buf[0]=='d'||buf[0]=='q'||buf[0]=='a')
				break;
			else if(buf[0]=='c')
			{
				cls(GetStdHandle(STD_OUTPUT_HANDLE));
				showCards(cards,CARD_SUM);
				continue;
			}
			flag=analysis(buf,cards,CARD_SUM);
			if(flag==-1)
				printf("表达式格式错误\n");
		}
		if(buf[0]=='a')
		{
			printf("%s",tmp);
			free(tmp);
		}
		else if(buf[0]=='q')
			break;
	}
	free(tmp);
	delCards(pile);
	return 0;
}