107.堆棧四則運算
/* 在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]='
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");
}
}
面向對象編程
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
