数据结构模拟计算器课程设计Word版

传播优秀Word版文档 ，希望对您有帮助，可双击去除！数据结构课程设计实验报告模拟计算器班 级：学 号：姓 名：模拟计算器1、 问题描述对于模拟计算器的设计，实际便是利用栈对一个表达式求值的问题。要求：对包含加，减，乘，除，括号的任意整型表达式进行求解2、 设计思路表达式：任何表达式都是由操作数、运算符和界限符组成的有意义的式子。表达式求值时一般有后缀表示、中缀表示、前缀表示。操作数：可以是常数、变量、常量。运算符：从运算对象上分有单目运算符、双目运算符、三目运算符。界限符：左右括号和表达式结束符。思 路：我们平时用到的表达式即为我们所输入的表达式（以 # 结束），此表达式为中缀表达式，只要将此表达式利用栈来进出运算的符号转换为后缀表达式，之后利用栈来进出运算的数字将后缀表达式的值求出即可。3、 数据结构定义一般表达式的长度不会过长所以将顺序栈的容量设为100已经算是比较大了具体数据结构如下：# define maxsize 100typedef double datatype1;typedef char datatype2;typedef struct stack1 datatype1 data1maxsize; int top1;/*栈顶元素*/seqstack1,*pseqstack1; /*顺序栈*/typedef struct stack2 datatype2 data2maxsize; int top2;/*栈顶元素*/seqstack2,*pseqstack2; /*顺序栈*/4、 系统功能模块介绍（1） 判断字符是否为操作数函数 int isnum(char)当输入表达式时要利用栈对表达式中的数字和符号进行进栈出栈，因此要判断表达式中的内容是操作数、运算符还是界限符，给出相关信息。（2） 求运算符优先级函数 int priority(char ) 对输入的表达式中的内容，若为运算符和界限符则要判断其优先级已完成其计算的先后顺序。（3） 中缀表达式转换为后缀表达式函数 int infix_exp_value(char *,char *) 我们平时使用的为中缀表达式，但若利用栈则利用后缀表达式比较容易计算，因此要将中缀表达式转换为后缀表达式，具体算法步骤如下：count=0，初始化运算符栈s，将结束符# 加入运算符栈s中。读表达式字符=w。当栈顶为# 并且w也是# 时结束；否则循环做下列步骤： 如果w是操作数判断若count=0直接输出,读下一个字符=w;转。若 count!=0 追加字符, 读下一个字符=w, 转。 w若是运算符，则：count=1; 如果栈顶为（并且w为）则（出栈不输出，读下一个字 符=w，转。 如果栈顶为（或者栈顶优先级小于w优先级，则w入栈，读下 一个字符=w，转。否则：从运算符栈中出栈并输出，转（4） 后缀表达式的求值函数 double postfix_exp(char *)使用一个操作数栈，当从左到右扫描表达式时，每遇到一个操作数就送入栈中保存，如果操作数不止一位，则保存在operand中，遇到下一个操作数时，执行operand=operand*10+(ch-0)，便可将操作数转化为数字。每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果在入栈，直到整个表达式结束，这时送入栈顶的值就是结果。5、 程序清单# include # include # include # define maxsize 100typedef double datatype1;typedef char datatype2;typedef struct stack1 datatype1 data1maxsize; int top1;/*栈顶元素*/seqstack1,*pseqstack1; /*顺序栈*/typedef struct stack2 datatype2 data2maxsize; int top2;/*栈顶元素*/seqstack2,*pseqstack2; /*顺序栈*/*栈的初始化*/pseqstack1 init_seqstack1(void) pseqstack1 S; S=(pseqstack1)malloc(sizeof(pseqstack1); if(S) S-top1=-1; return S;pseqstack2 init_seqstack2(void) pseqstack2 S; S=(pseqstack2)malloc(sizeof(pseqstack2); if(S) S-top2=-1; return S;/*判断栈空*/int empty_seqstack1(pseqstack1 S) if(S-top1=-1) return 1; else return 0;int empty_seqstack2(pseqstack2 S) if(S-top2=-1) return 1; else return 0;/*X入栈*/int push_seqstack1(pseqstack1 S,datatype1 X) if(S-top1=maxsize-1) printf(栈满，无法入栈！n); return 0; else S-top1+; S-data1S-top1=X; return 1; int push_seqstack2(pseqstack2 S,datatype2 X) if(S-top2=maxsize-1) printf(栈满，无法入栈！n); return 0; else S-top2+; S-data2S-top2=X; return 1; /*X出栈*/int pop_seqstack1(pseqstack1 S,datatype1 *X) if(empty_seqstack1(S) return 0; else *X=S-data1S-top1; S-top1-; return 1; int pop_seqstack2(pseqstack2 S,datatype2 *X) if(empty_seqstack2(S) return 0; else *X=S-data2S-top2; S-top2-; return 1; /*求栈顶元素*/int gettop_seqstack1(pseqstack1 S,datatype1 *X) if(empty_seqstack1(S) return 0; else *X=S-data1S-top1; return 1;int gettop_seqstack2(pseqstack2 S,datatype2 *X) if(empty_seqstack2(S) return 0; else *X=S-data2S-top2; return 1;/*判断字符是否为操作数。若是返回1，否则返回0*/int isnum(char c) if(c=0 & cA*/ S=init_seqstack1();/*初始化栈*/ while(ch!=#)/*遇到元素!=#时*/ if(isnum(ch)/*判断ch是否为数字字符,计算出操作数*/ operand=operand*10+(ch-0); else/*否则*/ if(operand)push_seqstack1(S,operand);/*当前字符不是数字,操作数结束,要入栈*/operand=0;if(ch!= & ch!= )pop_seqstack1(S,&b);/*运算符ch后的操作数出栈存入b*/pop_seqstack1(S,&a);/*运算符ch前的操作数出栈存入a*/switch(ch)/*求 a ch b=? ,将结果赋给 c */ case + : c=a+b;break;case - : c=a-b;break;case * : c=a*b;break;case / :if(b!=0)c=a/b;elseprintf(分母为零!); push_seqstack1(S,c);/*将c压入栈中*/ ch=*A+;/*指针向下移动一位*/ /*遇到#循环结束*/ gettop_seqstack1(S,&result);/*此时栈顶元素即为计算结果result*/ return result;/*优先级判断函数*/int priority(char op)switch(op)case #: return 1;case ): return 2;case +: case -: return 3;case *: case /: return 4;case (: return 5;default : return 0; /*将指针infixexp指向的中缀表达式转换为指针postfixexp指向的后缀表达式*/int infix_exp_value(char *infixexp,char *postfixexp)pseqstack2 S;/*定义栈S*/int count=0;char w;/*存放读取到的表达式(infixexp)的字符*/char c;/*存放栈顶元素*/char topelement;/*存出栈元素*/S=init_seqstack2();/*初始化栈*/if(!S)/*栈的初始化判断*/printf(栈初始化失败!);return 0;push_seqstack2(S,#);/*将结束符# 加入运算符栈S中*/w=*infixexp;/*读表达式字符=w*/while(gettop_seqstack2(S,&c),c)!=#|w!=#)/*栈顶元素不等于#或w不等于#时循环*/if(isnum(w)/*判断w是否为操作数,若是直接输出,读下一个字符=w,转*/if(count)*postfixexp=;postfixexp+;count=0;*postfixexp=w;postfixexp+;w=*(+infixexp);else/*w若是运算符分类如下*/count=1;if( (gettop_seqstack2(S,&c),c)=( & w=) )/*如果栈顶为(并且w为)则(出栈不输出,读下一个字符=w,转*/pop_seqstack2(S,&topelement); /*将(出栈存入topelement*/w=*(+infixexp);elseif( (gettop_seqstack2(S,&c),c)=( | priority( (gettop_seqstack2(S,&c),c) ) w，转*/push_seqstack2(S,w);w=*(+infixexp);else/*否则*/*从运算符栈中出栈并输出,转*/pop_seqstack2(S,&topelement);*postfixexp=topelement;postfixexp+;*postfixexp=#;/*在指针postfixexp指向的后缀表达式结尾追加字符#*/*(+postfixexp)=0;/*在指针postfixexp指向的后缀表达式最后追加结束符0*/return 1;/*主函数*/int main() int i=0;char Amaxsize;char Bmaxsize;printf(请输入表达式,如:11+22#,必须以#号结尾!n); /* 1+2*(9+7)-4/2# 23+(12*3-2)/4+34*5/7)+108/9# */Ai=getchar();while(Ai+!=#)Ai=getchar();Ai=0;infix_exp_value(A,B);printf(A=%sn,A);printf(B=%sn,B);printf(上式的结果为: );printf(%gn,postfix_exp(B);return 0; getch();6、 运行与调试分析等（6.1）、运行与调试（1）、先输入： 3+5*2# 后按回车求值，结果应为：13（2）、先输入： 1+2*(9+7)-4/2# 后按回车求值，结果应为：31（3）、先输入： 15+3-2+(9/4)# 后按回车求值，结果应为：18.25（4）、先输入： 1+3-2+(4*5/10)-2# 后按回车求值，结果应为：2（5）、先输入：23+(12*3-2)/4+34*5/7)+108/9# 后按回车求值，结果应为：67.785714（6.2）、分析根据以上结果可以知道本程序正确，本程序中int isnum(char c)double postfix_exp(char *A)int priority(char op)int infix_exp_value(char *infixexp,char *postfixexp)等函数原型为课本P64P68 的函数，单元函数只能对0-9之间的数进行基本的算术运算，无法对大于9的数进行运算，因而对函数double postfix_exp(char *A)与int infix_exp_value(char *infixexp,char *postfixexp)进行一定的修改，便可以运算整形数字，(6.2.1)函数double postfix_exp(char *A)修改前后对比 修改前 修改后(6.2.2)函数int infix_exp_value(char *infixexp,char *postfixexp)修改前后对比 修改前 修改后