北京理工大学数据结构实验2

1、1、简单计算器。请按照四则运算加、减、乘、除、幂（）和括号的优先关系和惯例，编写计算器程序。要求： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。例如，输入：4+2*5=输出：14 输入：(4+2)*(2-10)=输出：-48程序如下：#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存

2、储空间分配增量typedef struct/定义运算符栈数据类型 char *base; char *top; int stacksize;SqStack1;typedef struct/定义操作数栈数据类型 int *base; int *top; int stacksize;SqStack2;int InitStack1(SqStack1 &S)/构造一个空的运算符栈 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_

3、INIT_SIZE; return OK;/InitStack1int InitStack2(SqStack2 &S)/构造一个空的操作数栈 S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack2char GetTop1(SqStack1 S)/若栈不空，则用char型元素e返回S的栈顶元素，并返回OK；否则返回ERROR char e; if(S.top=S.bas

4、e) return ERROR; e=*(S.top-1); return e;/GetTop1int GetTop2(SqStack2 S)/若栈不空，则用int型元素e返回S的栈顶元素，并返回OK；否则返回ERROR int e; if(S.top=S.base) return ERROR; e=*(S.top-1); return e;/GetTop2int Push1(SqStack1 &S,char e)/插入char型元素e为新的栈顶元素 if(S.top-S.base=S.stacksize) S.base=(char *)realloc(S.base,(S.stacksize+

5、STACKINCREMENT)*sizeof(char); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push1int Push2(SqStack2 &S,int e)/插入int型元素e为新的栈顶元素 if(S.top-S.base=S.stacksize) S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base) ex

6、it(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push2int Pop1(SqStack1 &S,char &e)/若栈不空，则删除S的栈顶元素，用char型元素e返回其值，并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/Pop1int Pop2(SqStack2 &S,int &e)/若栈不空，则删除S的栈顶元素，用int型元素e返回其值，并返回OK；否则返回ERROR

7、 if(S.top=S.base) return ERROR; e=*-S.top; return OK;/Pop2char Precede(char a,char b)/比较两个相继出现的运算符a和b间的优先级关系switch(a)case +:switch(b)case+:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return;break;case:return;break;case-:return;break;case*:return;bre

8、ak;case/:return;break;case(:return;break;case=:return;break;case:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return;break;case:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return;break;case:return;br

9、eak;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return;break;case:return;break;case(:switch(b)case+:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case):return=;break;case:return;break;case-:return;break;case*:return;bre

10、ak;case/:return;break;case):return;break;case=:return;break;case:return;break;case#:switch(b)case+:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return=;break;case:return0;b-) x=x*a; return x;/powint Operate(int a,char theta,int b)/操作数a和b进行运算 switch(t

11、heta)case+:return(a+b);case-:return(a-b);case*:return(a*b);case/:return(a/b);case:return(pow(a,b);/Operateint In(char c)/判断字符c是否为运算符if(c!=+&c!=-&c!=*&c!=/&c!=&c!=&c!=(&c!=) return ERROR;else return OK;/Inint EvaluateExpression()int x,a,b;char c,theta; SqStack1 OPTR;SqStack2 OPND;InitStack1(OPTR);InitStack2(OPND);Push1(OPTR,#);c=getchar();while(c!=n) x=0;if(!In(c)/c是操作数while(!In(c)x=x*10+c-48;c=getchar();Push2(OPND,x);else/c是算符 switch(Precede(GetTop1(OPTR),c)case:/退栈并将运算结果入栈Pop1