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小时内删除侵权内容。