#include <stdio.h>
#include <alloc.h>
#include <stdlib.h> 
#include <string.h> 
/*字符操作函數*/
#include <ctype.h> 

#define BUFFSIZE 32
#define COL 128
#define ROW 64

/*定義棧1*/
typedef struct node
{
   int data;
   struct node  *next;
}STACK1; 
 /*定義棧2*/
typedef struct node2
{
   char data;
   struct node2 *next;
}STACK2;
/*下面定義兩個棧基本操作*/
/*入棧函數*/
STACK1 *PushStack(STACK1 *top,int x)
{
   STACK1 *p;  
   p=(STACK1 *)malloc(sizeof(STACK1));
   if(p==NULL)  
   {
      printf("ERROR\n!");
      exit(0);  
   }
   p->data=x; 	
   p->next=top;	
   top=p;  			
   return top; 	
}
/*出棧函數*/
STACK1 *PopStack(STACK1 *top) 
{
   STACK1 *q; 
   q=top;  
   top=top->next; 
   free(q);  
   return top; 
}
 /*讀棧頂元素*/
int GetTop(STACK1 *top) 
{
   if(top==NULL)
   {
      printf("Stack is null\n"); 
      return 0;
   }
   /*返回棧頂元素*/
   return top->data; 
}
/*取棧頂元素，并刪除棧頂元素*/
STACK1 *GetDelTop(STACK1 *top,int *x) 
{
   *x=GetTop(top);  	
   top=PopStack(top); 
   return top; 
}
int EmptyStack(STACK1 *top) /*判棧是否為空*/
{
   if(top==NULL) 
   		return 1; 
   return 0; 
}
/*入棧函數*/
STACK2 *PushStack2(STACK2 *top,char x) 
{
   STACK2 *p;
   p=(STACK2 *)malloc(sizeof(STACK2)); 
   if(p==NULL) 
   {
      printf("error\n!"); 
      exit(0); 
   }
   p->data=x; 
   p->next=top; 
   top=p; 
   return top; 
}
STACK2 *PopStack2(STACK2 *top) /*出棧*/
{
   STACK2 *q; 
   q=top; 
   top=top->next; 
   free(q); 
   return top; 
}
/*讀棧頂元素*/
char GetTop2(STACK2 *top) 
{
   if(top==NULL) 
   {
      printf("Stack is null\n"); 
      return 0; 
   }
   return top->data; 
}
/*取棧頂元素，并刪除棧頂元素*/
STACK2 *GetDelTop2(STACK2 *top,char *x) 
{
   *x=GetTop2(top); 
   top=PopStack2(top);
   return top; 
}
/*判棧是否為空*/
int EmptyStack2(STACK2 *top) 
{
   if(top==NULL)
      return 1; 
   else
      return 0; 
}
/*隨機發牌函數*/
void GenCard()
{
   int num,i;
   randomize();
   for(i=0;i<4;i++)
   {
      num=random(13); /*大小隨機數*/
      printf("%d ",num);
   } 
}
/*中綴字符串e轉后綴字符串a函數*/
void ExpressTransform(char *expMiddle,char *expBack) 
{
   STACK2 *top=NULL; /* 定義棧頂指針*/
   int i=0,j=0;
   char ch;
   while(expMiddle[i]!='\0') 
   {
   		/*判斷字符是數字*/
      if(isdigit(expMiddle[i])) 
      {
	 			do{
	    		expBack[j]=expMiddle[i];
	    		i++;j++; 
	  		}while(expMiddle[i]!='.');
	 			expBack[j]='.';
	 			j++;
      }
      /*處理“(”*/
      if(expMiddle[i]=='(')  
	 			top=PushStack2(top,expMiddle[i]);
	 		/*處理“)”*/
      if(expMiddle[i]==')')  
      {
	 			top=GetDelTop2(top,&ch); 
	 			while(ch!='(')  
	 			{
	    		expBack[j]=ch;  
	    		j++; 
	    		top=GetDelTop2(top,&ch);
	 			}
      }
      /*處理加或減號*/
      if(expMiddle[i]=='+'||expMiddle[i]=='-') 
      {
	 			if(!EmptyStack2(top))
	 			{
	    		ch=GetTop2(top);
	    		while(ch!='(') 
	    		{
	       		expBack[j]=ch;
	       		j++; 
	       		top=PopStack2(top);
	       		if(EmptyStack2(top))
		  				break; 
	       		else
		  				ch=GetTop2(top); 
	    		}
	 			}
       top=PushStack2(top,expMiddle[i]);
     }
     /*處理乘或除號*/
     if(expMiddle[i]=='*'||expMiddle[i]=='/') 
     {
	 	 	if(!EmptyStack2(top)) 
	 		{
	    		ch=GetTop2(top);
	    		while(ch=='*'||ch=='/')
	    		{
	       		expBack[j]=ch;
	      	  j++; 
	       		top=PopStack2(top);
	       		if(EmptyStack2(top)) 
		  				break; 
	       		else
		  				ch=GetTop2(top); 
	    		}
	 		}
	 		top=PushStack2(top,expMiddle[i]); 
    }
      i++; 
   }
   while(!EmptyStack2(top)) 
      top=GetDelTop2(top,&expBack[j++]);
   expBack[j]='\0';  
}
/*后綴表達式求值函數*/
int ExpressComputer(char *s)
{
   STACK1 *top=NULL;
   int i,k,num1,num2,result;
   i=0;
   while(s[i]!='\0')  /*當字符串沒有結束時作以下處理*/
   {
      if(isdigit(s[i])) /*判字符是否為數字*/
      {
	 			k=0;  /*k初值為0*/
	 			do{
	    		k=10*k+s[i]-'0';  /*將字符連接為十進制數字*/
	    		i++;   /*i加1*/
	 			}while(s[i]!='.'); /*當字符不為‘.’時重復循環*/
	 			top=PushStack(top,k); /*將生成的數字壓入堆棧*/
      }
      if(s[i]=='+')  /*如果為'+'號*/
      {
	 			top=GetDelTop(top,&num2); /*將棧頂元素取出存入num2中*/
	 			top=GetDelTop(top,&num1);  /*將棧頂元素取出存入num1中*/
	 			result=num2+num1;  /*將num1和num2相加存入result中*/
	 			top=PushStack(top,result);  /*將result壓入堆棧*/
      }
      if(s[i]=='-')  /*如果為'-'號*/
      {
	 			top=GetDelTop(top,&num2); /*將棧頂元素取出存入num2中*/
	 			top=GetDelTop(top,&num1); /*將棧頂元素取出存入num1中*/
	 			result=num1-num2; /*將num1減去num2結果存入result中*/
	 			top=PushStack(top,result); /*將result壓入堆棧*/
      }
      if(s[i]=='*')  /*如果為'*'號*/
      {
	 			top=GetDelTop(top,&num2); /*將棧頂元素取出存入num2中*/
	 			top=GetDelTop(top,&num1); /*將棧頂元素取出存入num1中*/
	 			result=num1*num2; /*將num1與num2相乘結果存入result中*/
	 			top=PushStack(top,result); /*將result壓入堆棧*/
      }
      if(s[i]=='/') /*如果為'/'號*/
      {
	 			top=GetDelTop(top,&num2); /*將棧頂元素取出存入num2中*/
	 			top=GetDelTop(top,&num1); /*將棧頂元素取出存入num1中*/
	 			result=num1/num2; 				/*將num1除num2結果存入result中*/
	 			top=PushStack(top,result); /*將result壓入堆棧*/
      }
      i++;  /*i加1*/
   }
   top=GetDelTop(top,&result); /*最后棧頂元素的值為計算的結果*/
   return result;  /*返回結果*/
}
/*檢查輸入的表達式是否正確*/
int CheckExpression(char *e)
{
	char ch;
	int i=0;
	while(e[i]!='\0')
	{
		if(isdigit(e[i])) 
		{
			if(isdigit(e[i+1]))
			{
				i++;
			 	continue;
			}
			if(e[i+1]!='.')
			{
				printf("\n The wrong express format!!\n");
				return 0;
			}
			i++;
		}
		i++;
	}
	return 1;
}
/*主函數*/
int main()
{
   char expMiddle[BUFFSIZE],expBack[BUFFSIZE],ch;
   int i,result;
   clrscr(); 
   /*提示輸入字符串格式*/
   printf("*******************************************\n");
   printf("|  Welcome to play our game : 24 points!  |\n");
   printf("|      The input format as follows:       |\n");
   printf("|              10.*(4.-3.)                |\n");
   printf("*******************************************\n");
   while(1)
   {
   		printf("\n The four digits are: ");
     	GenCard();
     	printf("\n");
     	do{
     	printf(" Please input the express:\n");
     	/*輸入字符串壓回車鍵*/
   		scanf("%s%c",expMiddle,&ch); 
      //printf("%s\n",expMiddle);
      /*檢查輸入的表達式是否正確*/
    	}while(!CheckExpression(expMiddle));
     
      printf("%s\n",expMiddle);
      /*調用ExpressTransform函數將中綴表達式expMiddle轉換為后綴表達式expBack*/
      ExpressTransform(expMiddle,expBack); 
      /*計算后綴表達式的值*/
      result=ExpressComputer(expBack); 
      printf("The value of %s is:%d.\n",expMiddle,result);
      if(result==24) 
	 			printf("You are right!");
      else printf("You are wrong!");
      printf(" Do you want to play again(y/n)?\n");
      scanf("%c",&ch); 
      if(ch=='n'||ch=='N') 
	 			break;   
   } 
   return 0;
}