/* 在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;/*在構造之前和銷(xiāo)毀之后,base的值為NULL*/
int *pTop;/*棧頂指針*/
int StackSize;/*當前已分配的存儲空間,以元素為單位*/
}Stack;
typedef int BOOLEAN;
char Operator[8]="+-*/()#";/*合法的操作符存儲在字符串中*/
char Optr;/*操作符*/
int Opnd=-1;/*操作符*/
int Result;/*操作結果*/
/*算符間的優(yōu)先關(guān)系*/
char PriorityTable[7][7]=
{
{'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','o'},
{'>','>','>','>','o','>','>'},
{'<','<','<','<','<','o','='},
};
//數據對象的操作方法
//構造一個(gè)空棧,如果返回值為0,則表示初始化失敗
Stack InitStack()/*這是個(gè)效率低的方法*/
{
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;
}
//銷(xiāo)毀棧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)
{//棧滿(mǎn),追加存儲空間
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;
}
//主函數及其它函數的實(shí)現
//比較兩個(gè)數學(xué)符號operator_1,operator_2的計算優(yōu)先權,在算符優(yōu)先關(guān)系表中查找相應的關(guān)系并返回'<','=',或'>'
char CheckPriority(char operator_1,char operator_2)
{
int i,j;//用來(lái)查詢(xún)算符間優(yōu)先關(guān)系表的下標
//char *ptr;
i=strchr(Operator,operator_1)-Operator;//找到傳入操作符在字符串Operators中的相對位置
j=strchr(Operator,operator_2)-Operator;
//返回算符優(yōu)先關(guān)系表中相應值
return PriorityTable[i][j];
}
BOOLEAN IsOperator(char ch)
{//判斷一個(gè)字符是否為打操作符
if(strchr(Operator,ch))
return TRUE;
else
return FALSE;
}
//從鍵盤(pán)獲得輸入
void GetInput(void)
{
char Buffer[20];//鍵盤(pán)輸入緩沖區,用來(lái)處理輸入多位數的情況
char ch;//存放鍵盤(pán)輸入
int index;//存放Buffer的下標
index=0;
ch=getch();//從鍵盤(pán)讀入一個(gè)字符
while(ch!=13&&!IsOperator(ch))
{//如果輸入的字符是回車(chē)符或是操作符,循環(huán)結束
if(ch>='0'&&ch<='9')
{//將字符回顯到屏幕
printf("%c",ch);
Buffer[index]=ch;
index++;
}
ch=getch();
}
if(ch==13)
Optr='#';//輸入的表達式以回車(chē)符結束
else
{
Optr=ch;
printf("%c",ch);
}
if(index>0)
{
Buffer[index]='\0';
Opnd=atoi((Buffer));
}
else
Opnd=-1;//程序不支持輸入負數,當Opnd為負數時(shí),表示輸入的字符為操作符
}
//計算形如a+b之類(lèi)的表達式,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;//臨時(shí)變量
char theta;//存放操作符的變量
int itheta;//存放出棧的操作符的變量add by me
int a,b;//存放表達式運算時(shí)的中間值
int topOpnd;//棧頂操作數
char topOptr;//棧頂操作符
Stack OPTR=InitStack();//操作符棧
Stack OPND=InitStack();//操作數棧
if(!Push(&OPTR,'#'))//操作符棧中的第一個(gè)為#字符
return FALSE;
GetInput();//從鍵盤(pán)獲得輸入
while(Optr!='#'||GetTop(OPTR)!='#')
{//如果Optr>=0,表示有操作數輸入
if(Opnd>=0)Push(&OPND,Opnd);
switch(CheckPriority(GetTop(OPTR),Optr))
{
case '<'://棧頂元素優(yōu)先權低
if(!Push(&OPTR,Optr))return FALSE;
GetInput();
break;
case '='://脫括號并接收鍵盤(pán)輸入
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;
}
}
//本算法中,當輸入只有一個(gè)操作數然后就輸入回車(chē)符時(shí),
//OPND.pTop==OPND.pBase
//如果OPND.pTop==OPND.pBase并且Opnd<0,則說(shuō)明用戶(hù)
//未輸入任何操作和操作符而直接輸入[回車(chē)],程序直接
//退出運行
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("使用方法:請從鍵盤(pán)上直接輸入表達式,以回車(chē)鍵結束.如45*(12-2)[回車(chē)]\n");
printf("注0:不輸入任何數而直接按[回車(chē)]鍵,將退出程序.\n");
printf("注1:本程序暫時(shí)不接受除數字鍵及四則運算符之外的任何其它鍵盤(pán)輸入.\n");
printf("注2:本程序暫時(shí)只能處理正確的表達式,不支持輸入負數.\n");
printf("-------------------------------\n\n");
}
void main(void)
{
int i;//用來(lái)一些說(shuō)明性信息
Message();
for(i=1;;i++)
{
printf("表達式%d:",i);
if(EvaluateExpression())
printf("=%d\n",Result);
else
printf("計算中遇到錯誤\n");
}
}聯(lián)系客服
