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

1、信号%才方的数据结构课程设计实验报告模拟计算器班级:学号：姓名：模拟计算器1、问题描述对于模拟计算器的设计，实际便是利用栈对一个表达式求值的问题。要求：对包含加，减，乘，除，括号的任意整型表达式进行求解2、设计思路表达式：任何表达式都是由操作数、运算符和界限符组成的有意义的式子。表达式求值时一般有后缀表示、中缀表示、前缀表示。操作数：可以是常数、变量、常量。运算符：从运算对象上分有单目运算符、双目运算符、三目运算符。界限符：左右括号和表达式结束符。思路：我们平时用到的表达式即为我们所输入的表达式(以#结束)，此表达式为中缀表达式，只要将此表达式利用栈来进出运算的符号转换为后缀表达式，之后利用栈

2、来进出运算的数字将后缀表达式的值求出即可。3、数据结构定义一般表达式的长度不会过长所以将顺序栈的容量设为100已经算是比较大了具体数据结构如下：#definemaxsize100typedefdoubledatatypel;typedefchardatatype2;typedefstructstack1datatype1data1maxsize;inttop1;/*栈顶元素*/seqstack1,*pseqstack1;/*顺序栈*/typedefstructstack2datatype2data2maxsize;inttop2;/*栈顶元素*/seqstack2,*pseqstack2;/*

3、顺序栈*/4、系统功能模块介绍(1) 判断字符是否为操作数函数intisnum(char)当输入表达式时要利用栈对表达式中的数字和符号进行进栈出栈，因此要判断表达式中的内容是操作数、运算符还是界限符，给出相关信息。(2) 求运算符优先级函数intpriority(char)对输入的表达式中的内容，若为运算符和界限符则要判断其优先级已完成其计算的先后顺序。(3) 中缀表达式转换为后缀表达式函数intinfix_exp_value(char*,char*)我们平时使用的为中缀表达式，但若利用栈则利用后缀表达式比较容易计算，因此要将中缀表达式转换为后缀表达式，具体算法步骤如下：<1>co

4、unt=0,初始化运算符栈s,将结束符#加入运算符栈s中。<2>读表达式字符=>w。<3>当栈顶为#'并且w也是#'时结束；否则循环做下列步骤：<3.1>如果w是操作数判断若count=0直接输出，读下一个字符=>w;转<3>。若count!=0追加字符'',读下一个字符=>w,转<3>。<3.2>w若是运算符，则：count=1;<3.2.1>如果栈顶为(并且w为)则(出栈不输出，读下一个字符=>w,转<3>。<3.2.1>如果栈

5、顶为(或者栈顶优先级小于w优先级，则w入栈，读下一个字符=>w,转<3>。否则：从运算符栈中出栈并输出，转<3>(4) 后缀表达式的求值函数doublepostfix_exp(char*)使用一个操作数栈，当从左到右扫描表达式时，每遇到一个操作数就送入栈中保存，如果操作数不止一位，则保存在operand中，遇到下一个操作数时，执行operand=operand*10+(ch-'0'),便可将操作数转化为数字。每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果在入栈，直到整个表达式结束，这时送入栈顶的值就是结果。5、程序清单# incl

6、ude<stdio.h># include<malloc.h># include<conio.h># definemaxsize100typedefdoubledatatype1;typedefchardatatype2;typedefstructstack1datatype1data1maxsize;inttop1;/*栈顶元素*/seqstack1,*pseqstack1;/*顺序栈*/typedefstructstack2datatype2data2maxsize;inttop2;/*栈顶元素*/seqstack2,*pseqstack2;/*顺序栈*

7、/*栈的初始化*/pseqstacklinit_seqstack1(void)(pseqstack1S;S=(pseqstack1)malloc(sizeof(pseqstack1);if(S)S->top1=-1;returnS;pseqstack2init_seqstack2(void)(pseqstack2S;S=(pseqstack2)malloc(sizeof(pseqstack2);if(S)S->top2=-1;returnS;/*判断栈空*/intempty_seqstack1(pseqstack1S)(if(S->top1=-1)return1;elsere

8、turn0;intempty_seqstack2(pseqstack2S)(if(S->top2=-1)return1;elsereturn0;/*X入栈*/intpush_seqstack1(pseqstack1S,datatype1X)(if(S->top1=maxsize-1)(printf("栈满，无法入栈！n");return0;)else(S->top1+;S->data1S->top1=X;return1;)intpush_seqstack2(pseqstack2S,datatype2X)(if(S->top2=maxsiz

9、e-1)(printf("栈满，无法入栈！n");return0;)else(S->top2+;S->data2S->top2=X;return1;)/*X出栈*/intpop_seqstack1(pseqstack1S,datatype1*X)(if(empty_seqstack1(S)return0;else(*X=S->data1S->top1;S->top1-;return1;)intpop_seqstack2(pseqstack2S,datatype2*X)(if(empty_seqstack2(S)return0;else(*

10、X=S->data2S->top2;S->top2-;return1;/*求栈顶元素*/intgettop_seqstack1(pseqstack1S,datatype1*X)(if(empty_seqstack1(S)return0;else*X=S->data1S->top1;return1;)intgettop_seqstack2(pseqstack2S,datatype2*X)(if(empty_seqstack2(S)return0;else*X=S->data2S->top2;return1;)/*判断字符是否为操作数。若是返回1,否则返回

11、0*/intisnum(charc)(if(c>='0'&&c<='9')return1;elsereturn0;)/*求后缀表达式的值*/doublepostfix_exp(char*A)(pseqstack1S;/*定义栈S*/doubleoperand=0;doubleresult;/*存放栈顶元素*/doublea;/*运算符ch前的操作数出栈存入a*/doubleb;/*运算符ch后的操作数出栈存入b*/doublec;/*c=achb*/charch;/*存放读取到的表达式(A)的字符*/ch=*A+;/*读表达式字符=&

12、gt;A*/S=init_seqstack1();/*初始化栈*/while(ch!='#')/*遇至U元素！='#'时*/(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);pop_se

13、qstack1(S,&a);/*运算符ch后的操作数出栈存入b*/*运算符ch前的操作数出栈存入a*/switch(ch)/*求achb=?，将结果赋给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+;/*指针向下移动一位*/*遇到'#'循环结束*/gett

14、op_seqstack1(S,&result);/*此时栈顶元素即为计算结果result*/returnresult;/*优先级判断函数*/intpriority(charop)switch(op)case'#':return1;case')':return2;case'+':case'-':return3;case'*':case'/':return4;case'(':return5;default:return0;/*将指针infixexp指向的中缀表达式转换为指针pos

15、tfixexp指向的后缀表达式*/intinfix_exp_value(char*infixexp,char*postfixexp)(pseqstack2S;/*定义栈S*/intcount=0;charw;/*存放读取到的表达式(infixexp)的字符*/charc;/*存放栈顶元素*/chartopelement;/*存出栈元素*/S=init_seqstack2();/*初始化栈*/if(!S)/*栈的初始化判断*/(printf("栈初始化失败！");return0;push_seqstack2(S,'#');/*将结束符'#'加入

16、运算符栈S中*/w=*infixexp;/*读表达式字符=>w*/while(gettop_seqstack2(S,&c),c)!='#'|w!='#')/*<3>栈顶元素不等于#'或w不等于'#'时循环*/if(isnum(w)/*判断w是否为操作数，若是直接输出，读下一个字符=>w,转<3>*/(if(count)(*postfixexp=''postfixexp+;count=0;*postfixexp=w;postfixexp+;w=*(+infixexp);else/*

17、w若是运算符分类如下*/count=1;if(gettop_seqstack2(S,&c),c)='('&&w=')')/*如果栈顶为'('并且w为')'则'('出栈不输出，读下一个字符=>w,转<3>*/pop_seqstack2(S,&topelement);/*将'('出栈存入topelement*/w=*(+infixexp);elseif(gettop_seqstack2(S,&c),c)='('|priority(

18、gettop_seqstack2(S,&c),c)<priority(w)/*如果栈顶为('或者栈顶优先级小于w优先级，则w入栈,读下一个字符=>w,转<3>*/push_seqstack2(S,w);w=*(+infixexp);else/*否贝U*/*从运算符栈中出栈并输出，转<3>*/pop_seqstack2(S,&topelement);*postfixexp=topelement;postfixexp+;*postfixexp='#'/*在指针postfixexp指向的后缀表达式结尾追加字符'#&#

19、39;*/*(+postfixexp)='0'/*在指针postfixexp指向的后缀表达式最后追加结束符0'*/return1;/*主函数*/intmain()inti=0;charAmaxsize;charBmaxsize;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)

20、;printf("A=%sn",A);printf("B=%sn",B);printf("上式的结果为：");printf("%gn",postfix_exp(B);return0;getch();)6、运行与调试分析等(6.(1) 行与调试(1)、先输入：3+5*2#后按回车求值，结果应为：13-数据结构上数据结构.侏浩与2。12年课程谡讨、书上八模拟讨算器.课本一|请输入表达式，如：11十22#,必须以#号结尾!3+5*2#卜=3+5毋B二二352址+"上式的结果为：13Pressanykeytoco

21、ntinue(2)、先输入：1+2*(9+7)-4/2#后按回车求值，结果应为：31“比磷;I据结构-数据结构徐洁立口12年课程设计"书上模搜讨算器一课本一请输入表达式，如：11+22葩必须以首号结尾!1+2*(9+7)-4/2UA=l+2*(9+7)-4/2#B二二l20907+*-H9402/-#上式的结果为：31Pressanykeytocontinue_(3)、先输入：15+3-2+(9/4)#后按回车求值，结果应为：18.25国数据结构I数据结构除浩谊012年课程谩讨，书上mtrn式模拟讨算器_课本请输入表达式，如：11+22#,必须以#号结尾!15+3-2+(9/4)#A

22、=15+3-2+(9/4)#B=153+02Y94/+#上式的结果为：18.25Pressanykeytocontinue(4)、先输入：1+3-2+(4*5/10)-2#后按回车求值，结果应为:35,数据结构'数据结构.徐浩口1W年课程设过书上模拟计算器_谡本”电“请输入表达式,如：11+22",必须以#号结尾!1+3-2+(4*5710)-2#A-=l+3-2+(4*B/10)-2#B-l3-n®2-405*010/+02-#上式的结果为：2Pressanykeytocontinue(5)、先输入：23+(12*3-2)/4+34*5/7)+108/9#后按回车

23、求值，结果应为：67.78571403"H：'数据结构数据结构一徐浩场年课程设计书上起也、模拟计翼器一理本请输入表达式,如：11+22礼必须以#号结尾!23+(12*3-2)/4+34*5/7)+108/9#A=23+(12*3-2)74+34*5/7)+108/9#E=2301203+(32H34/93405*07/-hH910809/+#上式的结果为：67,7857Pressanykeytocontinue(6.(2) 析根据以上结果可以知道本程序正确，本程序中intisnum(charc)doublepostfix_exp(char*A)intpriority(char

24、op)intinfix_exp_value(char*infixexp,char*postfixexp)等函数原型为课本P64-P68的函数，单元函数只能对0-9之间的数进行基本的算术运算，无法对大于9的数进行运算，因而对函数doublepostfix_exp(char*A)与int(6.2.1)函数doublepostfix_exp(char*A)修改前后对比修改前infix_exp_value(char*infixexp,char*postfixexp)进行一定的修改，便可以运算整形数字，doublepostfi«_ewp(char*A)<一p5eqstacKS;charr

25、esultcharch;ch=*A+;S-init_seqstack();(if(isnuii(ch)pushseqst.ack(S,(char)(cti,fl*);else<pop_5eqstack(SB&b);pop_seqstack(S;5uitch(ch)doublypostfix_exp(ctiar*fi)pseqstacklS;/看定义栈$江/Uourieoperand=0;Idoubleresult;/*存放低顶元素量/doublea;/喳黑铢h前的速作薮出筏存入a*/doubleb;/啮簟将M后的榛作数出程特入皿/doublec;/*c-actib*/charch

26、;八在放读取到的表达式(射的字符wch=*ft+;/联表达式字符=>口*/S-init_seqstack1()£仁初始化栈巡到元素，=#时黑/“(isrHm(cli)/,判断cii是否为数字帖符，计写operand=operand*1B+(ch-'flbelse/否则”IF(operand)<一push_5eqstack1(Svoperand)operand-fl;if(ch*='0,&&chf=,1)pop_seqstack1CS;/*jzpop_seq弓tacH1(S,&a);/噬switch(cti)外求achU=?1将至修改后(6.2.2)函数in