《《数据结构与算法设计》实验》由会员分享,可在线阅读,更多相关《《数据结构与算法设计》实验(17页珍藏版)》请在金锄头文库上搜索。
1、数据结构与算法设计实验 作者: 日期:数据结构与算法设计实验报告实验二学院:自动化学院班级:学号:姓名: 一、实验目的 按照四则运算加、减、乘、除、幂()和括号的优先关系和惯例,编写计算器程序。二、实验内容 简单计算器。请按照四则运算加、减、乘、除、幂()和括号的优先关系和惯例,编写计算器程序。要求: 从键盘输入一个完整的表达式,以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。例如,输入:4+2*5=输出:14 输入:(4+2)*(2-10)=输出:-48三、程序设计 概要设计1、宏定义#define TRUE 1#define F
2、ALSE 0#define OK 1#define ERROR 02、基本函数:(1)void InitStack_char(SqStack *S) /char型栈初始化(2)void InitStack_int(sqStack *S) /int型栈初始化(3)void Push_char(SqStack *S,char ch) /char型元素进栈(4)void Push_int(sqStack *S,int num) /int型元素进栈(5)char GetTop_char(SqStack *S) /取char型栈顶元素(6)int GetTop_int(sqStack *S) /取int
3、型栈顶元素(7)Status In(char c) /判断是否为运算符,若是运算符则返回,否则返回(8)char Precede(char a,char b) /判断两运算符的先后次序(9)Status Pop_char(SqStack *S,char &x) /char型栈出栈(10)Status Pop_int(sqStack *S,int &x) /int型栈出栈(11)int Operate(int a,char theta,int b) /计算a和b运算结果3、流程图详细设计数据类型typedef struct node /构造char型栈char ch;struct node *n
4、ext;node; typedef struct struct node *base;struct node *top;SqStack;typedef struct lnode /构造int型栈int num;struct lnode *next;lnode; typedef struct struct lnode *base;struct lnode *top;sqStack; 操作部分void InitStack_char(SqStack *S)S-base = (node *)malloc(sizeof(node);S-base-next=NULL;S-top = S-base; /ch
5、ar型栈初始化void InitStack_int(sqStack *S)S-base = (lnode *)malloc(sizeof(lnode);S-base-next=NULL;S-top = S-base; /int型栈初始化void Push_char(SqStack *S,char ch)node *p;p=(node*)malloc(sizeof(node);p-ch=ch;p-next=S-top;S-top=p; /char型元素进栈Status Push_int(sqStack *S,int num) lnode *p;p=(lnode*)malloc(sizeof(ln
6、ode);p-num=num;p-next=S-top;S-top=p;return OK; /int型元素进栈char GetTop_char(SqStack *S)return (S-top-ch); /取char型栈顶元素int GetTop_int(sqStack *S)return (S-top-num); /取int型栈顶元素Status Pop_char(SqStack *S,char &x)if(S-base = S-top)return ERROR;node *p;p=S-top;x=p-ch;S-top=p-next;free(p);return OK; /char型栈出栈
7、Status Pop_int(sqStack *S,int &x)if(S-base = S-top)return ERROR; lnode *p;p=S-top;x=p-num;S-top=p-next;free(p);return OK; /int型栈出栈计算功能int Operate(int a,char theta,int b)int i,z = 1;switch(theta)case +:z = (a + b);break;case -:z = (a - b);break;case *:z = (a * b);break;case /:z = (a / b);break;case :
8、for(i = 1;i;elsereturn ;if(a=*|a=/)if(b=(|b=)return ;if(a=()if(b=)return =;elsereturn ;if(a=#)if(b=)return =;elsereturn ); /判断两运算符的先后次序主函数int main() /主函数char c,x,theta;int a,b,c1; /定义变量SqStack OPTR; /定义字符栈sqStack OPNR; /定义整型栈InitStack_char(&OPTR); /初始化InitStack_int(&OPNR); /初始化Push_char(&OPTR,#); /将
9、字符型栈底设为#c = getchar(); /从键盘输入得到字符while(c!=|GetTop_char(&OPTR)!=#) /判定是否执行循环if(!In(c)c1 = 0;while(!In(c)c1 = c1*10+c-0;c = getchar();Push_int(&OPNR,c1); /当扫描字符不是运算符时,转化为整型数存入栈中elseswitch(Precede(GetTop_char(&OPTR),c) /判定运算符的优先关系case : /当前运算符优先级低Pop_char(&OPTR,theta);Pop_int(&OPNR,b);Pop_int(&OPNR,a);Push_int(&OPNR, Operate(a,theta,b);/计算运算结果,并存入int栈break; /继续循环printf(%dn,GetTop_int(&OPNR