数据结构课程设计-表达式求值

《数据结构课程设计-表达式求值》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、“数据结构”课程设计报告系（院）：信息工程学院设计题目：表达式求值专业班级：计算机科学与技术1301B小组成员：指导教师：完成时间：2014~2015学年第二学期-16-数据结构课程设计报告²课程设计目的1、能够灵活地应用所学数据结构知识，根据加工数据对象的特征，选择适当的数据结构、存贮结构及相应算法，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。2.初步掌握各种算法在时间和空间的分析技巧；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.能够进行算法设计和程序设计，并且使所设计的程序结构清楚，正确易读，并上

2、机调试通过；提高综合运用所学的理论知识和方法独立分析和解决问题的能力。4.用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。5.培养较强的实习和实践能力；较强的分析问题和解决问题的能力。²课程设计任务与要求：[问题描述]为了解决人们生活中经常遇到的表达式求值问题。免去人们复杂的计算，输入算式即得出结果。[基本要求]算式中无错误，否则将程序会直接退出。输入中缀式可以输出前缀式和后缀式。[测试数据]1.2*2-2.1+5.12*3.1*(1+23)/2.4+3.3^2=9

3、.1212+121/21+49*20.13/(3*6.9)-2.1^2.1=4^5-(12.65+12)/12+32*12=[实现提示]这个需要用栈，利用，其实用二叉树也可以做的出来。按照顺序把二叉树建立了，直接按照遍历的顺序计算就行了。一需求分析1．问题描述：在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。2．实现功能：算法输入：表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为了增加难度，我加入了幂运算符，

4、操作符为“+、-、*、/、^”，操作数为实数范围。算法运行：将输入的中缀表达式改为后缀表达式或者后缀式，并进行运算。-16-数据结构课程设计报告算法输出：输出后缀表达式和表达式运算结果。二概要设计总体分为两大块，一个是求值函数，一个是二叉树建立函数，二叉树建立之后就可以按照不同的遍历顺序求出前缀式或者后缀式。三详细设计-16-数据结构课程设计报告先说说求值部分，这个需要用到优先级的比较，所以需要用到一个比较函数，返回运算符的优先级。算法是分离数字和运算符，分别设立运算符栈和操作数栈。具体参见程序。在变换式子形式的方法上需要用二叉树，所有有个结构体typ

5、edefstructTree{doublen;charc;chars[20];Tree*leftchild,*rightchild;}tree;下面详细说这些成员的作用。n是存储字符串转换后的数。C是存储操作符。S数组是存储未转化成数字的字符串，leftchild和rightchild分别指向左孩子和右孩子。四设计与调试分析程序分块设计，便于维护和调整。有五个主要的函数，（一）、doublework(char*);计算表达式的值。（二）、tree*creat_tree(char*);根据字符串建立二叉树。（三）、voidvisit(tree*);从根结

6、点开始后序遍历。（四）、void_visit(tree*);从根结点开始先序遍历。（五）、doublecalculata(doublenum1,charop,doublenum2);计算。五用户手册注：任意输入一个数据后进入系统，然后根据系统提示操作即可。六测试成果1.2*2-2.1+5.12*3.1*(1+23)/2.4+3.3^2=-16-数据结构课程设计报告-16-数据结构课程设计报告输入前缀输入前缀和后缀-16-数据结构课程设计报告更换表达式七附录（源程序清单）-16-数据结构课程设计报告#include#include

7、th.h>#include#include#include#includeusingnamespacestd;templateclassmystack{//自定义栈类，方便栈的输出Tsta[500];ints_top;public:mystack(){s_top=0;}voidpush(Tn){if(s_top>=499)printf("栈满了，进栈失败！");elsesta[++s_top]=n;}voidpop(){if(s_top==0){pri

8、ntf("栈为空，不能出栈。");exit(1);}else--s_top;}Ttop()