《数据结构与算法设计方案》实验2

1、数据结构与算法设计实验报告实验二学院：自动化学院班级：学号：姓名：一、实验目的按照四则运算加、减、乘、除、幕（人）和括号的优先关系和惯例，编写计算器程序。二、实验内容简单计算器。请按照四则运算加、减、乘、除、幕（竹和括号的优先关系和惯例，编写计算器程序。 要求： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。例如，输入：4+2*5=输出：14输入：（4+2）*（2-10）=输出：-48三、程序设计概要设计1、宏定义#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1#

2、defi ne 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 型栈顶元素（7） S

3、tatus In（ char c） /判断是否为运算符，若是运算符则返回，否则返回（8） char Precede（char a,char b） /判断两运算符的先后次序（9） Status Pop_char（SqStack *S,char &x） /char型栈出栈计算a和b运算结果(11) int Operate。nt a,char theta,int b) /3、流程图实数入粉详细设计数据类型构造char型栈typedef struct node/char ch;struct node *n ext;n ode;typedef structstruct node *base;st

4、ruct node *top;SqStack;typedef struct Inode/构造int型栈int num;struct Inode *n ext;ln ode;typedef structstruct Inode *base;struct Inode *top;sqStack;操作部分void In itStack_char(SqStack *S)S->base = (node *)malloc(sizeof( no de);S->base-> next=NULL;S->top = S->base;型栈初始化/char void In itStack_

5、i nt(sqStack *S)S->base = (Inode *)malloc(sizeof( Ino de);S->base-> next=NULL;S->top = S->base;型栈初始化/int void Push_char(SqStack *S,char ch) node *p;p=(no de*)malloc(sizeof( no de);p_>ch=ch;p_>n ext=S->top;S->top=p;/char型元素进栈Status Pushn t(sqStack *S,i nt num)Inode *p;p=(l

6、no de*)malloc(sizeof( Ino de); p->num=num;p_>n ext=S->top;S->top=p;型元素进栈return OK;intchar GetTop_char(SqStack *S)取char型栈顶元素return (S->top->ch); /int GetTop_i nt(sqStack *S)取int型栈顶元素retur n (S->top->nu m); /Status Pop_char(SqStack *S,char &x)if(S->base = S->top)retur

7、n ERROR;node *p;p=S->top;x=p->ch;S->top=p->n ext;free(p);return OK;型栈出栈/charStatus Pop_i nt(sqStack *S,i nt &x)if(S->base = S->top)return ERROR;Inode *p;p=S->top;x=p->num;S->top=p->n ext;free(p);return OK;型栈出栈int计算功能int Operate(i nt a,char theta,i nt b)int i,z = 1;s

8、witch(theta)case '+':z = (a + b);break;case '-':z = (a - b);break;case '*':z = (a * b);break;case 7':z = (a / b);break;case 'A':for(i = 1;i<=b;i+)z = z*a;break;return (z);/计算a和b运算结果Status ln( char c)if(c='+'|c='-'|c='*'|c=7'|c='(

9、'|c=')'|c='='|c='人') return OK;elsereturn ERROR;/判断是否为运算符char Precede(char a,char b)if(a='+'|a='-')if(b='+'|b='-'|b=')'|b='=')return '>'elsereturn '<'if(a='*'|a='/')if(b='('|b=&#

10、39; a')return '<'elsereturn '>'if(a='(')if(b=')')return '='elsereturn '<'if(a=')')if(b!='(')return '>'if(a='#')if(b='=')return '='elsereturn '<'if(a='A')return ('>

11、;'); /主函数int mai n()/char c,x,theta;int a,b,c1;/SqStack OPTR;/sqStack OPNR;/Ini tStack_char(&OPTR);判断两运算符的先后次序主函数定义变量定义字符栈定义整型栈/初始化初始化将字符型栈底设为#Ini tStack_i nt(&OPNR);/Push_char(&OPTR,' #');/while(c!='='|GetTop_char(&OPTR)!=#) /判定是否执行循环if(!I n(c)cl = 0;while(!I n(

12、c)cl = c1*1O+c-'O：c = getchar();Pushnt(&OPNR,c1);/当扫描字符不是运算符时，转化为整型数存入栈中elseswitch(Precede(GetTop_char(&OPTR),c) /case '<':Push_char(&OPTR,c);c = getchar();break;判定运算符的优先关系/当前运算符优先级高，存入char栈case '=':Pop_char(&OPTR,c);c = getchar();break; /运算符次序相等，存入char 栈case &

13、#39;>':/当前运算符优先级低Pop_char(&OPTR,theta);Pop_i nt(&OPNR,b);Pop_i nt(&OPNR,a);Push _in t(&OPNR, Operate(a,theta,b);/计算运算结果，并存入int栈break;/继续循环printf（"%dn",GetTop_int（&OPNR）;/计算完成，取出 int 栈顶元素，并输出return 0;四、程序调试分析编写程序的过程中遇到了很多的问题，最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可

14、以执行一位数运算的程序出现了error，由于没有及时保存，并且之前的代码无法恢复，只得重新编写一次。第二次编写理清思路之后，在课本和网上资料的辅助下，终于成功的编出了程序并且可以完美执行。经验告诉了我在编程的时候一定要注意经常进行调试，只有学会调试才能处理好大程序的编写，否则极其容易出错。五、用户使用说明1.运行程序，2将整个表达式从键盘键入，以“=”结束，回车可得到结果。六、程序运行结果（1）输入：（11+3）*5=输出：70（2）输入：（31-13）/（9-3）=输出：6七、程序清单#in clude<stdio.h>#in clude<stdlib.h>#defi

15、 ne TRUE 1#defi ne FALSE 0#defi ne OK 1#defi ne ERROR 0构造char型栈typedef int Status;typedef struct node/char ch;struct node *n ext;n ode;typedef structstruct node *base;struct node *top;SqStack;typedef struct In ode/构造 int 型栈int num;struct Inode *n ext;ln ode;typedef structstruct Inode *base;struct In

16、ode *top;sqStack;void In itStack_char(SqStack *S)S->base = (node *)malloc(sizeof( no de);S->base-> next=NULL;S->top = S->base;/char型栈初始化void In itStack_i nt(sqStack *S)S->base = (Inode *)malloc(sizeof( Ino de);S->base-> next=NULL;S->top = S->base;/int型栈初始化void Push_char

17、(SqStack *S,char ch)node *p;p=(no de*)malloc(sizeof( no de);p->ch=ch;p_>n ext=S->top;S->top=p;/char型元素进栈Status Pushn t(sqStack *S,i nt num)Inode *p;p=(l no de*)malloc(sizeof( Ino de);p->num=num;p_>n ext=S_>top;S_>top=p; return OK;intchar GetTop_char(SqStack *S) return (S->

18、top->ch); /int GetTop_i nt(sqStack *S)retur n (S->top->nu m); /型元素进栈取char型栈顶元素取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->n ext; free(p); return OK;/charStatus Pop_i nt(sqStack *S,i nt &am

19、p;x) if(S->base = S->top)return ERROR;Inode *p;p=S->top;x=p->num;S->top=p->n ext;free(p);return OK;/intint Operate(i nt a,char theta,i nt b) int i,z = 1;switch(theta)case '+':z = (a + b);break;case '-':z = (a - b);break;case '*':z = (a * b);break;case 7'

20、:z = (a / b);break;case 'A':for(i = 1;i<=b;i+)z = z*a;break;return (z);/计算a和b运算结果Status ln( char c)if(c='+'|c='-'|c='*'|c=7'|c='('|c=')'|c='='|c=' a') return OK;elsereturn ERROR;/判断是否为运算符char Precede(char a,char b)if(a='+'

21、;|a='-')if(b='+'|b='-'|b=')'|b='=')return '>'elsereturn '<'if(a='*'|a='/')if(b='('|b=' a')return '<'elsereturn '>'if(a='(')if(b=')')return '='elsereturn '&l

22、t;'if(a=')')if(b!='(')return '>'if(a='#')if(b='=') return '='elsereturn '<'if(a='Tretur n ('>');/int mai n()char c,x,theta;int a,b,c1;SqStack OPTR; sqStack OPNR;Ini tStack_char(&OPTR);Ini tStack_i nt(&OPNR);Push_cha