北理工数据结构实验二

数据结构与算法设计实验报告实验二学院：自动化学院班级：_学号：_姓名：_一、实验目的 1、熟悉 VC 环境，学习使用 C 语言实现栈的存储结构。2、通过编程、上机调试，进一步理解栈的基本概念。3、锻炼动手编程，独立思考的能力。二、实验内容 实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（）和括号的优先关系和惯例，编写计算器程序。要求支持运算符：+、-、*、/、%、 （）和=： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志； 输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。例如，输入：4+2*5= 输出：14输入：(4+2)*(2-10)= 输出：-48三、程序设计 1、概要设计为实现上述程序功能，应使用两个栈，分别寄存操作数与运算符。为此，需要栈的抽象数据结构。(1)、栈的抽象数据类型定义为：ADT Stack数据对象：D= | ,12,0iaElemStin数据关系：R1= 11,|iiiiaD约定 端为栈顶， 端为栈底。na1a基本操作：InitStack(char *top;int stacksize;开始输入表达式char c=表达式首字符c!=|GetTop1(OPTR)!=!In(c,OP)c 存入数组;c=*(+ex);In(c,OP)数组中的数压入栈内;指针指向数组首元素case :操作数栈前 2 个数运算return GetTop2(OPND)输出 result结束SqStack1; /定义运算符栈数据类型typedef structint *base;int *top;int stacksize;SqStack2; /定义操作数栈数据类型SqStack1 OPTR; /声明运算符栈SqStack2 OPND; /声明操作数栈(2)、操作算法设计Status InitStack1(SqStack1 /申请空间if(!S.base)exit(OVERFLOW); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack1Status InitStack2(SqStack2 /申请空间if(!S.base)exit(OVERFLOW); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack2char GetTop1(SqStack1 S)/取得运算符栈的栈顶元素char e;if(S.top=S.base) return ERROR; /栈空e=*(S.top-1);return e;/GetTop1int GetTop2(SqStack2 S)/取得操作数栈的栈顶元素int e;if(S.top=S.base) return ERROR; /栈空e=*(S.top-1);return e;/GetTop2Status Push1(SqStack1 if(!S.base) exit(OVERFLOW);/存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push1Status Push2(SqStack2 if(!S.base) exit(OVERFLOW); /存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push2Status Pop1(SqStack1 /栈空e=*-S.top;return OK;/Pop1Status Pop2(SqStack2 /栈空e=*-S.top;return OK;/Pop2Status In(int m,char a)/判断 m 若是运算符，返回 TRUE，否则返回 FALSEfor(int n=0;an!=0;n+)if(m=an) return TRUE;return FALSE;/Inchar Precede(char m,char n)/判断 m 与 n 的优先级switch(m)case+:case-:if(n=+|n=-|n=)|n=)return ;