/* 在BC31下編譯 或VC6.0*/
/* compile under Borland C++ 3.1 or Visual C++ 6.0*/

/*#include "stdafx.h"*/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "conio.h"

#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100/*存儲空間初始分配量*/
#define STACKINCREMENT 20/*存儲空間分配增量*/

typedef struct
{
	int *pBase;/*在構造之前和銷毀之后,base的值為NULL*/
	int *pTop;/*棧頂指針*/
	int StackSize;/*當前已分配的存儲空間,以元素為單位*/
}Stack;

typedef int BOOLEAN;
 
char Operator[8]="+-*/()#";/*合法的操作符存儲在字符串中*/
char Optr;/*操作符*/
int Opnd=-1;/*操作符*/
int Result;/*操作結果*/

/*算符間的優先關系*/
char PriorityTable[7][7]=
{
	{'>','>','<','<','<','>','>'},
	{'>','>','<','<','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'<','<','<','<','<','=','o'},
	{'>','>','>','>','o','>','>'},
	{'<','<','<','<','<','o','='},
};

//數據對象的操作方法
//構造一個空棧,如果返回值為0,則表示初始化失敗
Stack InitStack()/*這是個效率低的方法*/
{
	Stack S;
	S.pBase=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
	if(!S.pBase)
	{/*內存分配失敗*/
		printf("內存分配失敗,程序中止運行\n");
		exit(-1);
	}
	else
	{
		S.pTop=S.pBase;
		S.StackSize=STACK_INIT_SIZE;
	}
	return S;
}
//銷毀棧S,S不再存在
void DestoryStack(Stack *S)
{
	if(S->pBase)
	{
		free(S->pBase);
		S->pTop=S->pBase=NULL;
        
	}
}
//若棧不空,則用e返回S的棧頂元素
//注:由于應用的特殊,可以不檢查棧是否為空
int GetTop(Stack S)
{
	return *(S.pTop-1);
}
//插入元素e為新的棧頂元素,如果成功則返回1,否則返回0
int Push(Stack *S,int e)
{
	if(S->pTop-S->pBase==S->StackSize)
	{//棧滿,追加存儲空間
		S->pBase=(int*)realloc(S->pBase,S->StackSize+STACKINCREMENT*sizeof(int));
		if(!S->pBase)
			return 0;//存儲分配失敗
		S->pTop=S->pBase+S->StackSize;
		S->StackSize+=STACKINCREMENT;
	}
	*(S->pTop++)=e;
	return 1;
}

int Pop(Stack *S,int *e)
{//若棧不空,則刪除S的棧頂元素,用e 返回其值,并返回1;否則返回0
	if(S->pTop==S->pBase)
		return 0;
	*e=*--(S->pTop);
	return 1;

}
//主函數及其它函數的實現
//比較兩個數學符號operator_1,operator_2的計算優先權,在算符優先關系表中查找相應的關系并返回'<','=',或'>'
char CheckPriority(char operator_1,char operator_2)
{
	int i,j;//用來查詢算符間優先關系表的下標
	//char *ptr;
	i=strchr(Operator,operator_1)-Operator;//找到傳入操作符在字符串Operators中的相對位置
	j=strchr(Operator,operator_2)-Operator;
	//返回算符優先關系表中相應值
	return PriorityTable[i][j];
}

BOOLEAN IsOperator(char ch)
{//判斷一個字符是否為打操作符
	if(strchr(Operator,ch))
		return TRUE;
	else 
		return FALSE;

}
//從鍵盤獲得輸入
void GetInput(void)
{
	char Buffer[20];//鍵盤輸入緩沖區,用來處理輸入多位數的情況
	char ch;//存放鍵盤輸入
	int index;//存放Buffer的下標
	index=0;
	ch=getch();//從鍵盤讀入一個字符
	while(ch!=13&&!IsOperator(ch))
	{//如果輸入的字符是回車符或是操作符,循環結束
		if(ch>='0'&&ch<='9')
		{//將字符回顯到屏幕
			printf("%c",ch);
			Buffer[index]=ch;
			index++;

		}
		ch=getch();
	}
	if(ch==13)
		Optr='#';//輸入的表達式以回車符結束
	else
	{
		Optr=ch;
		printf("%c",ch);

	}
	if(index>0)
	{
		Buffer[index]='\0';
		Opnd=atoi((Buffer));
	}
	else
		Opnd=-1;//程序不支持輸入負數,當Opnd為負數時,表示輸入的字符為操作符
}
//計算形如a+b之類的表達式,theta為操作符,a,b為操作數
int Calc(int a,char theta,int b)
{
	switch(theta)
	{
	case '+':
		return a+b;
	case '-':
		return a-b;
	case '*':
		return a*b;
	default:
		if(b==0)//除數為零的情況
		{
			printf("除數不能為");
			return 0;//返回0用以顯示
		}
		else
			return a/b;
	}
}
/*表達式求值*/
BOOLEAN EvaluateExpression()
{
	int temp;//臨時變量
	char theta;//存放操作符的變量
	int itheta;//存放出棧的操作符的變量add by me
	int a,b;//存放表達式運算時的中間值
	int topOpnd;//棧頂操作數
	char topOptr;//棧頂操作符
	
	Stack OPTR=InitStack();//操作符棧
	Stack OPND=InitStack();//操作數棧

	if(!Push(&OPTR,'#'))//操作符棧中的第一個為#字符
		return FALSE;

	GetInput();//從鍵盤獲得輸入

	while(Optr!='#'||GetTop(OPTR)!='#')
	{//如果Optr>=0,表示有操作數輸入
		if(Opnd>=0)Push(&OPND,Opnd);
		switch(CheckPriority(GetTop(OPTR),Optr))
		{
		case '<'://棧頂元素優先權低
			if(!Push(&OPTR,Optr))return FALSE;
				GetInput();
			break;
		case '='://脫括號并接收鍵盤輸入
			Pop(&OPTR,&temp);GetInput();
			break;
		case '>'://退棧并將運算結果入棧
			//先用itheta得到操作符在賦給theta
			Pop(&OPTR,&itheta);
			Pop(&OPND,&b);
			Pop(&OPND,&a);
			theta = (char)( itheta );
			Push(&OPND,Calc(a,itheta,b));
			Opnd=-1;
			break;

		}
	}
	//本算法中,當輸入只有一個操作數然后就輸入回車符時,
	//OPND.pTop==OPND.pBase
	//如果OPND.pTop==OPND.pBase并且Opnd<0,則說明用戶
	//未輸入任何操作和操作符而直接輸入[回車],程序直接
	//退出運行
	if(OPND.pTop==OPND.pBase&&Opnd<0)
	{
		printf("\n\n感謝使用!\n");
		exit(1);

	}
	else if(OPND.pTop==OPND.pBase)
		Result=Opnd;
	else
	{
		Result=GetTop(OPND);
		DestoryStack(&OPND);
		DestoryStack(&OPTR);
	}
	return TRUE;

}

void Message(void)
{
	printf("\n四則運算表達式求值演示\n");
	printf("-------------------------------\n");
	printf("使用方法:請從鍵盤上直接輸入表達式,以回車鍵結束.如45*(12-2)[回車]\n");
	printf("注0:不輸入任何數而直接按[回車]鍵,將退出程序.\n");
	printf("注1:本程序暫時不接受除數字鍵及四則運算符之外的任何其它鍵盤輸入.\n");
	printf("注2:本程序暫時只能處理正確的表達式,不支持輸入負數.\n");
	printf("-------------------------------\n\n");
}
void main(void)
{
	int i;//用來一些說明性信息
	Message();
	for(i=1;;i++)
	{
		printf("表達式%d:",i);
		if(EvaluateExpression())
			printf("=%d\n",Result);
		else
			printf("計算中遇到錯誤\n");
		
	}
}