数据结构课程设计表达式翻译本科论文.doc

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

1、数据结构课程考核报告表达式的翻译学号：姓名：专业：软件工程专业班级：15级云计算1班指导教师：南阳理工学院软件学院2016年12月目录1.需求分析-------------------------------------------------------------------31.1问题描述---------------------------------------------------------------31.2基本要求-----------------------------------------------------------

2、----32.系统设计-------------------------------------------------------------------33.程序流程图-----------------------------------------------------------------44.类关系图-------------------------------------------------------------------65.实现代码----------------------------------------------

3、--------------------76.个人总结-------------------------------------------------------------------77.参考书目-------------------------------------------------------------------7一．需求分析1.1问题描述编写完整程序，将中缀表达式翻译成后缀表达式。表达式由操作数(变量)、操作(运算符)以及小括弧“（”和“）”组成，其中：(1)操作包括算术运算、关系运算和逻辑运算三类；(2)操作数为单个字符或由

4、字母和数字任意多个字符构成；(3)能够识别出简单的错误，如括弧不匹配。1.2基本要求输入：中缀表达式，80个字符以内。输出：运算结果功能：将中缀表达式转化为后缀表达式二．系统设计根据题目要求，将中缀表达式转化为后缀表达式。问题的解决方案有两种，分别是利用栈结构实现算数表达式的四则运算或者利用二叉树把中缀表达式转化为前缀表达式，我选择栈结构与树结构相结合来实现算数表达式的转化。算法思想：①：运用栈和队列来将中缀转换为后缀，栈用来储存字符，队列用来存储后缀表达式。②：输入字符串c，若是数字的话直接进入队列，若是符号，为‘*’‘/’‘（’，则线检查栈中的栈

5、顶元素，前提是栈不为空，若栈不为空的话，栈顶元素为‘*’

6、

7、‘/’，则先将栈中的元素入队，如果栈顶是‘+’‘-’这些优先级小的，则直接将c入栈。③：如果c是优先级为“+”“-”的字符，先看一下栈是否为空，接着判断栈顶元素是否为“（”，若是，则继续将c进栈，否则的话，将栈中的元素全部出栈，直到栈空。④：若c为“）”则将栈中所有符号弹栈并进入队列。⑤：若c为“#”，则结束，并将栈中的剩余的符号全部入队列。⑥：打印队列中的，出队打印。开始三．程序流程图输入一个字符串celseifC!=’#’Ifc!=’.’

8、

9、c<9

10、

11、c>0If(!c!=’.’

12、

13、c<9

14、

15、

16、c>0)若为数存入数组,i=1elseif将数组中第0个存到队列中If(c'*'

17、

18、c=’/’

19、

20、c=’(’)elseifIf(c'+'

21、

22、c=’-’)If(c=’)’)If栈空栈顶出栈给c2while栈空栈顶出栈给eelseifIf(c2=’*’

23、

24、c2=’/’)栈顶出栈入队操作If(e!=’(’’)栈顶出栈入队操作栈顶元素出栈c2进栈后c进栈c2进队列c入栈elseife==’(’elseifwhile栈空e==’#’入栈栈中剩余的出栈入队操作结束三．类关系图(1).头文件：#include#include

25、>(2)宏定义：#defineOK1#defineERROR0#defineSTACK_SIZE20#defineSTACK_INCREMENT10#defineQUEUE_SIZE20(3)栈的定义结构体typedefintStatus;typedefcharStackElemtype;//栈的类型typedefstructStack{StackElemtype*base;StackElemtype*top;intstackSize;}Stack;(5)初始化栈：StatusStackInit(Stack*s)(6)出栈：StatusPop(Sta

26、ck*s,StackElemtype*value)(7)进栈：StatusPush(Stack*s,Stac