数据结构与算法设计实验2

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

2、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型栈顶元素（7）status in(c

3、har 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 *next;node; t

4、ypedef 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->

5、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_int(sqstack *s

6、,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)if(s->base

7、= 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 theta,int

8、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 (z); /计算a和b运算结果status in(char c)if(c='+'|c='-'|c='*'

9、;|c='/'|c='('|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='/'

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

11、39;)return ('>'); /判断两运算符的先后次序主函数int main() /主函数char c,x,theta;int a,b,c1; /定义变量sqstack optr; /定义字符栈sqstack opnr; /定义整型栈initstack_char(&optr); /初始化initstack_int(&opnr); /初始化push_char(&optr,'#'); /将字符型栈底设为#c = getchar(); /从键盘输入得到字符while(c!='='|gettop_char(&o

12、ptr)!='#') /判定是否执行循环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 '<':push_char(&optr,c);c = getchar();break; /当前运算符优先级高，存入char栈case '=':pop_

13、char(&optr,c);c = getchar();break; /运算符次序相等，存入char栈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); /计算完成，取出int栈顶元素，并输出return 0;四、程序调试

14、分析编写程序的过程中遇到了很多的问题，最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可以执行一位数运算的程序出现了error，由于没有及时保存，并且之前的代码无法恢复，只得重新编写一次。第二次编写理清思路之后，在课本和网上资料的辅助下，终于成功的编出了程序并且可以完美执行。经验告诉了我在编程的时候一定要注意经常进行调试，只有学会调试才能处理好大程序的编写，否则极其容易出错。五、用户使用说明 1.运行程序，2.将整个表达式从键盘键入，以“=”结束，回车可得到结果。六、程序运行结果（1）输入：（11+3）*5=输出：70（2）输入：(31-13)/(9-3)=输出：6

15、七、程序清单#include<stdio.h>#include<stdlib.h>#define true 1#define false 0#define ok 1#define error 0typedef int status;typedef struct node /构造char型栈char ch;struct node *next;node; typedef struct struct node *base;struct node *top;sqstack;typedef struct lnode /构造int型栈int num;struct lnode *ne

16、xt;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; /char型栈初始化void initstack_int(sqstack *s)s->base = (lnode *)malloc(sizeof(lnode);s->base->next=null;

17、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(lnode);p->num=num;p->next=s->top;s->top=p;return ok; /int型元

18、素进栈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型栈出栈status po

19、p_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 =

20、(a * b);break;case '/':z = (a / b);break;case '':for(i = 1;i<=b;i+)z = z*a;break;return (z); /计算a和b运算结果status in(char c)if(c='+'|c='-'|c='*'|c='/'|c='('|c=')'|c='='|c='')return ok;elsereturn error; /判断是否为运算符char prece

21、de(char a,char b)if(a='+'|a='-')if(b='+'|b='-'|b=')'|b='=')return '>'elsereturn '<'if(a='*'|a='/')if(b='('|b='')return '<'elsereturn '>'if(a='(')if(b=')')return

22、 '='elsereturn '<'if(a=')')if(b!='(')return '>'if(a='#')if(b='=')return '='elsereturn '<'if(a='')return ('>'); /判断两运算符的先后次序int main() /主函数char c,x,theta;int a,b,c1; /定义变量sqstack optr; /定义字符栈sqstack opnr; /定义整型栈initstack_char(&optr);