发布时间 : 星期一 文章(强烈推荐)算数表达式的求解毕业论文报告更新完毕开始阅读76cb44426d175f0e7cd184254b35eefdc8d315cb
合肥学院
计算机科学与技术系
课程设计报告
20 12 ～20 13 学年第 2 学期
课
程
数据结构与算法 算数表达式的求解
周丽娟
11计本3班
课程设计名称 学学专
业
班生
姓
名 号 级
指导教师 李红
20 13 年 3 月
【问题描述】
（算数表达式的求解）给定一个算数表达式，通过程序求出最后的结果。 【要求】
1、从键盘输入要求解的算术表达式； 2、采用栈结构进行算数表达式的求解过程； 3、能够判断算数表达式的正确与否； 4、对于错误表达式给出提示； 5、对于正确表达时给出最后的结果。 1、问题分析和任务定义
有题目可知，程序要求给定一算数表达式并计算最后的结果，我们知道，在高级语言中，任何一个表达式都是有操作数、运算符和界限符组成。在计算过程中，还要考虑表达式中有无括号以及左右括号之分。由于运算符有优先级的高低，因此一个算数表达是不可能总是按顺序执行。
通过以上可知，可以用栈来实现运算符的优先级完成算术表达式的求解。 为实现算法的优先级，设置两个栈：一个称为操作数栈opnd，用以寄存操作数和运算结果，另一个为操作符栈optr，用以寄存运算符。 该算法的基本思想是：
（1）首先置操作数栈opnd为空栈，表达式结束符“#”为操作符栈optr的栈底元素。
（2）依次读入表达式中每个字符，若为操作数，则进opnd栈；若是运算符，则与optr栈的栈顶运算符比较优先级后做相应操作：若当前操作符大于optr栈的栈顶，则当前操作符入栈；否则，opnd栈的栈顶元素、次栈顶元素出栈，同时optr栈的栈顶元素也出栈，形成运算，并将结果压入opnd栈，直至整个表达式求值完毕（即optr栈的栈顶元素和当前读入的字符均为“#”）。
对于算术表达式的输入，本程序采用gets()的方法读入，将运算符‘+’，‘-’，‘*’，‘’，‘（’，‘）’，‘#’存储在数组中时，定义表达式求解函数，在函数中判断读入的字符，如果是运算符，将这些字符入操作符optr栈，并比较优先级，判断是否运算。若读入的字符为‘0’到‘9’之间的数字时，用字符相减转化为整型，然后将转化后的整型再转化为ASCII的形式压入操作数栈opnd中。 2、数据结构的选择和概要设计 （1）存储结构设计
本程序主要采用顺序栈结构类型（Stack）来存储表达式计算中的数据。程序中需要建立两个栈，一个栈用于寄存运算符，另一个则用于寄存操作数和计算结果，故需要建立两个顺序栈结构类型。 （2）算数优先级设计
对一任意的表达式，由于表达式中运算符的优先级不同，可能会使表达式不按顺序进行计算。在本程序中定义函数Proceed（）来比较运算符的优先级，而函数中各优先级的比较主要根据以下优先级比较的表格：
表1：运算符优先级
运算符 用数字表示 栈内操作符的优先级 栈外操作符的优先级 + 0 3 2 - 1 3 2 * 2 5 4 3 5 4 （ 4 1 6 ） 5 6 1 # 6 0 0 在Precede（）函数中定义两个字符型参数变量op和c，其中op表示栈顶运算
符，c表示当前读入运算符，对于当前运算符是否入栈，进行如下操作： 比较当前运算符和栈顶运算符的优先级的大小：
1、如果当前运算符的优先级大于栈顶运算符的优先级，即op 2、如果当前运算符的优先级小于栈顶运算符的优先级，即op>c；令函数返回值为'>'，此时应将栈顶运算符出栈和栈顶、次栈顶操作数出栈并进行相应的运算。 3、如果当前元素的优先级等于栈顶运算符的优先级，即op=c；令函数的返回值为'='，此时界限符内的表达式已计算完毕。 （3）程序模块设计 1）程序模块 本程序主要包含3个模块：主程序模块、计算模块以及顺序栈操作模块，调用关系如图所示： 图1：程序模块图 2）系统功能模块 本程序大致包含10个函数，其中包含主函数。每个函数都有其相对应的功能实现。 ○1操作符的输入函数 int In(char c); ○2运算符比较优先级函数 char Proceed(char op,char c); ○3进行四则运算函数 int Operate(int a,char a1,int b); ○4实现表达式的求值函数 int EvalExpres(void); ○5初始化栈函数 void InitStack(Stack *s);