算数表达式的求解课程设计报告

1、学院计算机科学与技术系课程设计报告20 1220 13学年第2学期课程数据结构与算法课程设计名称算数表达式的求解学生周丽娟学号1104012013专业班级11计本3班指导教师红20 13年3月【问题描述】(算数表达式的求解)给定一个算数表达式，通过程序求出最后的结果。【要求】1、从键盘输入要求解的算术表达式；2、采用栈结构进行算数表达式的求解过程；3、能够判斷算数表达式的正确与否；4、对于错误表达式给出提示；5、对于正确表达时给出最后的结果。1、问题分析和任务定义有题目可知，程序要求给定一算数表达式并计算最后的结果，我们知道，在高级语言中， 任何一个表达式都是有操作数、运算符和界限符组成。在计

2、算过程中，还要考虑表达式中有 无括号以及左右括号之分。由于运算符有优先级的高低，因此一个算数表达是不可能总是按 顺序执行。通过以上可知，可以用栈来实现运算符的优先级完成算术表达式的求解。为实现算法的优先级，设置两个栈：一个称为操作数栈opnd，用以寄存操作数和运算结果 另一个为操作符栈optr，用以寄存运算符。该算法的基本思想是：(1) 首先置操作数栈opnd为空栈，表达式结束符“*”为操作符栈optr的栈底元素。(2) 依次读入表达式中每个字符，若为操作数，则进opnd栈；若是运算符，则与optr栈 的栈顶运算符比较优先级后做相应操作：若当前操作符大于optr栈的栈顶，则当前操作符 入栈；否

3、则5 opnd栈的栈顶元素、次栈顶元素出栈，同时optr栈的栈顶元素也出栈，形成 运算，并将结果压入opnd栈，直至整个表达式求值完毕(即optr栈的栈顶元素和当前读入 的字符均为“#”)。对于算术表达式的输入，本程序采用gcts()的方法读入，将运算符 宇，y，*，7,， r，j，r存储在数组中时，定义表达式求解函数，在函数中判斷读入的字符，如果 是运算符，将这些字符入操作符optr栈，并比较优先级，判斷是否运算。若读入的字符为'0'到9'之间的数字时，用字符相减转化为整型，然后将转化后的整型再转化为ASCII 的形式压入操作数栈opnd中。2、数据结构的选择和概要设

4、计(1) 存储结构设计本程序主要采用顺序栈结构类型(Stack)来存储表达式计算中的数振。程序中需要建 立两个栈，一个栈用于寄存运算符，另一个则用于寄存操作数和计算结果，故需要建立两个 顺序栈结构类型。(2) 算数优先级设计对一任意的表达式，由于表达式中运算符的优先级不同，可能会使表达式不按顺序进行 计算。在本程序中定义函数Proceed ()来比较运算符的优先级，而函数中冬优先级的比较 主要根据以下优先级比较的表格：表1 :运算符优先级运算符+一*/()#用数字表示0123456栈操作符的优先级3355160栈外操作符的优先级22111.在Precede ()函数中定义两个字符型参数变量op

5、和c，其中op表示栈顶运算符，c 表示当前读入运算符，对于当前运算符是否入栈，进行如下操作：比较当前运算符和栈顶运算符的优先级的大小：1、如果当前运算符的优先级大于栈顶运算符的优先级，即op<c;令函数返回值为， 并将当前运算符进optr栈。2 如果当前运算符的优先级小于栈顶运算符的优先级，即op>c ；令函数返回值为>'， 此时应将栈顶运算符出栈和栈顶次栈顶操作数出栈并进行相应的运算。3 '如果当前元素的优先级等于栈顶运算符的优先级，即op二c ；令函数的返回值为， 此时界限符的表达式已计算完毕。(3) 程序棋块设计1) 程序模块本程序主要包含3个模块：主程

6、序模块、计算模块以及顺序栈操作模块，调用关系如图 所示：图1 :程序模块图2) 系统功能模块本程序大致包含10个函数，其中包含主函数。每个函数都有其相对应的功能实现。 操作符的输入函数int In(char c); 运算符比较优先级函数char ProcccdCchar op,char c); 进行四则运算函数 int Operate(int a, char ah int b); 实现表达式的求值函数int EvalExpres(void); 初始化栈函数 void InitStack(Stack *s); 入栈函数 void Push(Stack *s, int x); 出栈函数 int P

7、op(Stack *s); 取栈顶元素函数int GctTop(Stack *s); 判栈空函数 void Empty (Stack *s); 主函数int mainO3) 函数之间主要调用的关系图本程序主要包含10个程序，冬程序之间的关系如图所示：(部分函数用以上的编号表示)图2 :函数之间调用关系图3、详细设计和编码(1) 、结构体类型的定义typcdcf structint dataMAXSIZE;int top;int base;/栈底Stack;(2) 、全局变量定义/以下为函数声明void InitStackCStack *);/初始化栈int Empty (Stack *); /

8、判空栈void Push (Stack *, int ); /进栈int Pop( Stack *);/出栈int GctTop(Stack *); /取栈顶元素int Operate(int »char , int ); / 计算结果char ProceedCchar , char ); / 比校优先级int In(char );/判斷输入符i nt Eva 1 ExpresCvo id);/ 表达式计算函数/定义两个栈分别存放运算符和操作数Stack StackR, StackD;(3) 、系统主要子程序的详细设计1) 、主函数模块设计int inainO/主函数int v;ch

9、ar ch; whi led)pr4ntfCt*欢迎使用算术表达式的求解的小程序*、)v = EvalExpresO;printfC't表达式的计算结果为:%dn,v);printf(nntInput ' rf to quit and ENTER run again:"); doscanf(,r%c&ch);if(ch = * if 11 ch = ' N')exit(O);wh订e(ch!- n );systcmCcls");return 0;在主函数中，设定用户操作界面的形式，通过调用表达式求解的子函数实现算法所要实 现的功能，然

10、后通过while()循环语句控制/可以实现多次调试。2) 、计算函数模块int Opcrate(ir)t a» char ah int b)int s;int dl = a;int d2 = b; /把字符ab变为对应数字switch(al)case ' +':s = dl+d2; break;case ' 一':s = d2-dl; break; a,case * :s = dl*d2; break;case ' P :s = d2/dl;return (s+ 0);/将运算结果转化为ascii码的形式入栈，在计算函数中，定义3个变量 >

11、; 表示基本运算中的变量。采用开关语句实现表达式的基 本运算，将运算结果转化为ASCII的形式返回。3) 、表达式求解的函数模块int EvalExpres(void)/表达式求解函数int a, b, i=0, s=0;char c80, r;Ini tStack(SStackR); /初始化栈Push(&StackR,');将表达式起始符压入栈InitStackC&StackD);printfC' t请输入表达式并以结束：");gcts(c);whilc(ci!=, 11 GctTop(&StackR)!=, )if(!In(ci)判断读入

12、的字符是不是运算符 不是则进opnd栈 if(ci >0' && ci <= '9')s += ci-'(r ;/字符的ascii相减将字符型转化为整型while(!In(c+i)/继续判断下一个字符，若不是运算符，表明为多位数，直到读取到字符为运算符为止s*=10;s += ci- 0* ;Push(&StackD,s+'(T); /将整型转化为ascii的形式入栈，使字符在栈以 ascii的形式保存，实现多位数的计算s = 0;/初始化s，继续判斷elseprintfC1你输入的表达式有误!nH);return 0

13、;elseswitch(Procccd(GetTop(SStackR), ci) 此函数用来比较读取的运算符 和栈顶运算符的优先级case/栈顶的元素优先级低，当前运算符入栈Push(&StackR,ci);i+;break;case '二:Pop(&StackR);i+;break;case '>' :/栈顶的优先级高则岀栈，并将计算结果压入栈r = Pop(&StackR);a = Pop(&StackD)-'O' ; /操作数在栈以ascii的形式存储，出站后要将ascii 转化为整型，然后进行运算b = Po

14、p(&StackD)- 0* ;Push(&StackD, Operate(a, r> b);break;return (GctTop(&StackD)-' O'); /将栈顶元素转化为整型的形式输出对于表达式求解函数，在程序中主要思想是对读入的表达式进栈进行判斷。若读入的 是O'到9之间的字符，将这些字符采用ascii相减的形式转化为整型，再入opnd栈， 若读入的字符为运算符，则将运算符入栈，并比较运算符之间的优先级，看是否运算，若栈 顶的运算符小于当前输入的运算符，则不需运算，只要将当前运算符入栈即可。否则，运算。 运算时先将optr

15、栈的栈顶运算符和opnd栈的栈顶、次栈顶元素出栈并将opnd栈中出栈 的元素的ASCII形式转化为整型再计算，最后讲计算结果再转化为ASCII码的形式压入opnd 栈中。使表达式求解函数返回值为opnd的栈顶元素。4、上圾调试过程遇到问题以及解决方案问题1、调试时没有错误，但运行时显示错误。解决方案：通过它提示的错误和警告，在判断是否为运算符的子函数中出现错误，如果为运 算符时返回1，其次返回0，在返回0时没有用else，这样使得整个子函数可以返回一个有 效值。问题2 -调试时程序显示没有错误，可以运行，但在运行时结果却出现错误。解决方案：把程序从头看了一遍，发现在比较优先级的函数中，优先级的

16、比较比较乱，而且 部分出错，后来査了关于运算符优先级的资料，通过在纸上把各种优先级列出，解决这个错 误°算法的时间复杂度由于在主函数用到嵌套循环，故算法的时间复杂度为0 (72)。5、測试结果及其分析(1) 、实现基本的加减乘除运算，当想要细续输入表达式时点击enter键，若要结束， 点击n或N縫即可，而且可实现多位数的运算。ir“uhrbr un= hminb PUIT5axnb 03 u ndul I 鼠lai44聂 PJOM“U-HR6R wmzw pue TFsb 03 u G- IL囂叟心赚筷fi场m盘m一 6nq®2 士強矍囂吧軽doplsgE£sc一

17、 Epsskmgxq-pfip =n& Kw-zw AT£h9A = 302111SG<戏Msg科省喋 :.、勺!?米2£-?、Y1申试故舲 <苗» '-sx/kSY. A、*FP.-.x.xx.xx.xx.xx.x.x.x叟心赚倏盘乌鹏轟-onqQQX帝矍餐抵参doppQQy££s:iulp<p:5ng C:UsersAdministratorDe5ktop燉揭结构课程设计Debug算数表达式的求昇ex贰*茨迎傍用算术表达式的求解的小程序 H*酣辭蠶肿束:12/3#Input 9nJ to quit and

18、ENTER run again：n?ress any key to continue(2) 实现复杂的算术表达式C:UsersAdmini$tratorDesktcp竣揭结沟课程设计Debug算数表达式的求解exhC:UMwAdminktnatorDEktopVg採结勺课程i&i+DmbugM数表迂式为求解(3) 错误表达式的处理C:UsersAdmini$tatorDesktop徴揭结构课程设计Debug算数表达式的求解exeI E 冋error!Press any key to continueC:Uscr3AdminbtR)torDe3ktop徴扃结构谋程设计Dcbug厲数表达式

19、的求解I I 叵 1使用具术轰达式的求解的小程序*>请输入裘达式笄以升腐:12/3-<5+2*3«EmM没有石括号？Pi*eee any key to cont inueC:UsersAdministvtor'iDesktop数捋结构课fl设计'Debug'骂数表达式的求解丄*卄样样咲炎迎使用算术表达式的求解的小程序“杯心曲丄 请领入表达式幷以#*结束：34+345/0-23*2# 除巍不可以为衣Press any key to continue6、用户使用说明(1) 本程序执行的文件为“算数表达式的求解问题”。(2) 所求表达式中都只是仅包含加、

20、减、乘、除4种基本运算的，其中也包含括号的应 用，所有的运算对象均为简单变董，要求将表达式中的数字字符转化为整型，且输入表达式 以“#”结束。(3) 输入表达式时，以结束，当点击回车键时即可得到运算结果，当想继续输入表 达式时、再次点击回车縫即可，当想结束时，点击字母b或N 0(4) 当输入错误表达式时，程序会给出相应的提醒。7、参考文献(1) 王昆仑、红主编，数据结构与算法 < 中国铁道，2007年5月(2) 阮宏一、鲁静主编，数据结构课程设计(C/C+描述)，：电子工业，2011年1月8 附录(源程序)：#include <malloc. h>#include <s

21、tdio. h>define MAXSIZE 16typcdcf structint dataMAXSIZE;int top;int base; /栈低Stack; /顺序栈的定义/以下为函数声明void InitStack(Stack *);/初始化栈int Empty (Stack *); /判空栈void Push(Stack *, int ); /进栈int Pop( Stack *);/出栈int GetTop(Stack *); /取栈顶元素int Operate(int ,char , int ); / 计算结果char Proceed(char ,char ); / 比校

22、优先级int InCchar );/判斷输入符i nt Eva 1 ExpresCvo id);/ 表达式计算函数/定义两个栈分别存放运算符和操作数Stack StackR, StackD;int mainO/主函数int v;char ch;while(l)printfCt*欢迎使用算术表达式的求解的小程序*2 )； v = EvalExpresO;printf(nt表达式的计算结果为:%d",v);printf(HntInput ' n' to quit and ENTER run again:");doscanf(f,%c&ch);if(ch

23、= ' n* | ch = ' N')exit(0);while(ch!= n );systciii(”cls”);return 0;void InitStack(Stack *s) /初始化栈s->top = 0;s->base = 0;int Empty (Stack *s)/判斷栈是否为空Iif(s->top =s->base)return 1;/栈空时返回1，否则返回0elsereturn 0;void Push(Stack *s> int x) / 进栈 if(s->top = MAXSIZE)printf(H terror

24、! rf); exit(0);elses->datas->top = x; s->top+;int PopCStack *s)/ 出栈int e;if(Empty(s)printfCtcrror!if); exit(0);elses->top;e = s->datas->top: return e;int GctTop(Stack *s)/取栈顶元素if(Empty(s)printf(Hterror!nn);exit(O);elsereturn s->datas->top-lJ;int EvalExpres(void) /表达式求解函数int a

25、, b, i=0, s=0;char c80, r;InitStackC&StackR);Push(&StackR,');InitStackC&StackD);printfC' t请输入表达式并以结束：");gcts(c);whilc(ci!=, 11 GctTop(&StackR)!=, )if(!In(ci)/判斷读入的字符不是运算符是则进栈 if(ci >0' && ci <= '9')s += ci-'(r ；/字符相减将字符型转化为整型whiled In(c+i)/继

26、续判斷下一个字符，若不是运算符，表明为多位数，直到读取到字符为运算符为止s*=10;s += ci- 0* ;Push(&StackD,s+'(T); /将整型转化为ascii的形式入栈，使字符在栈以 ascii的形式保存，实现多位数的计算s = 0;/初始化s，继续判斷else printf(nt你输入的表达式有误!nn); exit(0);elseswi tch( Procccd(GetTop(&StackR), c i ) 此函数用来比较读取的运算符 和栈顶运算符的优先级case '： 栈顶的元素优先级低，当前运算符入栈Push(&StackR,

27、ci);i+;break;case '二:Pop(&StackR);i+;break;case '>': 栈顶的优先级高则出栈，并将计算结果压入栈r = Pop(&StackR);a二Pop(&StackD)-'O' ; /操作数在栈以ascii的形式存储，出站后要将ascii 转化为整型，然后进行运算b = Pop(&StackD)- 0* ;Push(&StackD, Operate(a, r> b);break;return (GctTop(&StackD)-' O' );

28、/将栈顶元素转化为整型的形式输出int In(char c)/判斷C是否为运算符是返回1否则返回0charint i;for(i = 0; i < 7; i+)if(c = chi)return 1:return 0;char Proceed (char op» char c) /op为栈顶元素，c为当前读入的运算符，比较二者的优先级char ch;if(op=, C && c= X 11 op='h && c= #* )ch 宀；else if(op=, V 11 op二二')/*栈顶元素为 宇 或-的时候*/switch(c)case +case，一'：case')':case:ch ='>'break;case:case'/':case'(:ch =else if(o