北理工自动化数据结构实验报告2

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

2、：(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) Status In(char c)判断是否为运算符，若是运算符则返回，否

3、则返回(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、主要流程由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序，调用OutPut(L)函数显示排序结果。再由主程序首先调用InPut(L)函数创建顺序表，调用 Quic

4、kSort(L)函数进行交换排序, 调用OutPut(L)函数显示排序结果。再由主程序首先调用InPut(L)函数创建顺序表，调用SelectSort(L)函数进行选择排序,调用OutPut(L)函数显示排序结果。4、模块调用关系由主函数模块调用创建顺序表模块，排序模块与显示输出模块。20 / 163、流程图开始数据类型typedef struct node/构造char型栈char ch;struct node *next;node;typedef structstruct node *base;struct node *top;SqStack;typedef struct lnode/构造

5、int型栈int num;struct Inode *next;lnode;typedef structstruct Inode *base;struct Inode *top;sqStack;操作部分void InitStack_char(SqStack *S)S->base = (node *)malloc(sizeof(node);S->base->next=NULL;S->top = S->base;/char型栈初始化void InitStack_int(sqStack *S)S->base = (lnode *)malloc(sizeof(lno

6、de);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) Inode *p;p=(lnode*)malloc(sizeof(lnode);p->num=num;p->next=S->top;S-

7、>top=p;return OK;/intchar GetTop_char(SqStack *S)return (S->top->ch);/int GetTop_int(sqStack *S)return (S->top->num);/Status Pop_char(SqStack *S,char &x) if(S->base = S->top)return ERROR;node *p;p=S->top;型元素进栈取char型栈顶元素取int型栈顶元素x=p->ch;S->top=p->next;free(p)；retu

8、rn OK;/char型栈出栈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);b

9、reak;case '*':z = (a * b);break;case '/':z = (a / b);break;case '"for(i = 1;i<=b;i+)z = z*a;break;return 亿)；/计算a和b运算结果Status In(char c)(if(C='+'|c='-'|C='*'|C='/'|C='('|C=')'|C='='|C='A')return OK;elsereturn

10、ERROR;/判断是否为运算符char Precede(char a,char b)(if(a='+'|a='-')(if(b='+'|b='-'|b=')'|b='=')return '>'elsereturn '<'if(a='*'11a='/')(if(b='('|b='A，)return '<'elsereturn '>'if(a='(

11、9;)if(b=')')return '='elsereturn '<'if(a=')')if(b!='(')return '>'if(a='#')if(b='=')return '='elsereturn '<'if(a='A')return ('>');主函数int main()/char c,x,theta;int a,b,c1;/SqStack OPTR;/sqStack

12、OPNR;/判断两运算符的先后次序主函数定义变量定义字符栈定义整型栈InitStack_char(&OPTR);/InitStack_int(&OPNR); /Push_char(&OPTR,'#');/初始化初始化将字符型栈底设为#c = getchar();/从键盘输入得到字符while(c!='='|GetTop_char(&OPTR)!='#') /判定是否执行循环if(!In(c)cl = 0;while(!In(c) cl = c1*10+c-'0'c = getchar();Push_

13、int(&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 '>':/Pop_char(&OPTR,theta

14、);Pop_int(&OPNR,b);Pop_int(&OPNR,a);Push_int(&OPNR, Operate(a,theta,b);/当前运算符优先级低计算运算结果，并存入int栈break;/继续循环printf("%dn",GetTop_int(&OPNR);/计算完成，取出 int 栈顶元素，并输出return 0;四、程序调试分析编写程序的过程中遇到了很多的问题，比如开始时，使用getchar函数输入，但其有较大的弊端，只能输入0-9之间的整数，不能实现多位数及小数的计算。于是换为gets函数,将表达式作为整体存入数组中待处

15、理，在后续程序中加以转换。还有，在设计主要处理函数时，出现了多次编译错误。最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可以执行一位数运算的程序出现了error。还有许多问题后发现是由于指针指向混乱造成。这主要是自己的思路不清并且混淆了部分函数，导致程序结构混乱。 后来仔细绘制了流程图，详尽的分析了过程后，在课本和网上资料的辅助下，终于成功的解决了该问题。这也说明编程需要细心和耐心，只有一步一步的编写，不断的调试和修改，才能最终得到想要的结果。五、用户使用说明1 .本程序的运行环境为 Windows操作系统下的 Microsoft Visual C+ 6.0。2

16、.在VC环境下打开程序后，点击运行。3 .从键盘输入一个完整的表达式，以“=”作为表达式输入结束的标志，按回车键即可得到结果。六、程序运行结果(1)输入：4+2*5=输出：14(2)输入：(4+2)*(2-10)=输出：-48(3)输入：3* (4+1)=输出：15七、程序清单#include<stdio.h>#include<stdlib.h># define TRUE 1# define FALSE 0# define OK 1# define ERROR 0 typedef int Status;typedef struct node/构造char型栈char c

17、h;struct node *next;node;typedef structstruct node *base;struct node *top;SqStack;typedef struct Inode/构造int型栈int num;struct Inode *next;lnode;typedef structstruct lnode *base;struct lnode *top;sqStack;void InitStack_char(SqStack *S)S->base = (node *)malloc(sizeof(node);S->base->next=NULL;S

18、->top = S->base;/char型栈初始化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

19、_int(sqStack *S,int num) lnode *p;p=(lnode*)malloc(sizeof(lnode);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)

20、if(S->base = S->top) return ERROR;node *p;p=S->top;x=p->ch;S->top=p->next;free(p);return OK;/char型栈出栈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

21、 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 '"for(i = 1;i<=b;i+) z = z*a;break;return 亿)；/计算a和b运算结果Status In(char c) (if(c='+'|c='-

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

23、9;*11a='/')if(b='('|b=w)return '<'elsereturn '>'if(a='(')if(b=')')return '='elsereturn '<'if(a=')')if(b!='(') return '>'if(a='#')if(b='=')return '='elsereturn '<'if(a='A')return ('>');/判断两运算符的先后次序 int main()/主函数 定义变量定义字符栈定义整型栈/初始化char c,x,theta;int a,b,c1;/SqStack