表达式翻译数据结构课程设计解读.doc

数据结构课程考核报告表达式的翻译学号: 1515925640 姓名: 王伊庆专业: 软件工程专业班级: 15 级云计算 1班指导教师:钱鸽南阳理工学院软件学院 2016 年 12月目录 1. 需求分析-------------------------------------------------------------------3 问题描述---------------------------------------------------------------3 基本要求---------------------------------------------------------------3 2. 系统设计-------------------------------------------------------------------3 3. 程序流程图-----------------------------------------------------------------4 4. 类关系图-------------------------------------------------------------------6 5. 实现代码- -----------------------------------------------------------------7 6. 个人总结- ------------------------------------------------------------------7 7. 参考书目-------------------------------------------------------------------7 问题描述编写完整程序,将中缀表达式翻译成后缀表达式。表达式由操作数(变量)、操作(运算符)以及小括弧“(”和“)”组成,其中:(1) 操作包括算术运算、关系运算和逻辑运算三类; (2) 操作数为单个字符或由字母和数字任意多个字符构成; (3) 能够识别出简单的错误,如括弧不匹配。 基本要求输入:中缀表达式, 80个字符以内。输出:运算结果功能:,将中缀表达式转化为后缀表达式。问题的解决方案有两种, 分别是利用栈结构实现算数表达式的四则运算或者利用二叉树把中缀表达式转化为前缀表达式,我选择栈结构与树结构相结合来实现算数表达式的转化。算法思想: ①:运用栈和队列来将中缀转换为后缀,栈用来储存字符,队列用来存储后缀表达式。②:输入字符串 c, 若是数字的话直接进入队列,若是符号,为‘*’‘/’‘(’, 则线检查栈中的栈顶元素,前提是栈不为空,若栈不为空的话,栈顶元素为‘*’||‘/’,则先将栈中的元素入队,如果栈顶是‘+’‘-’这些优先级小的,则直接将 c入栈。③:如果 c是优先级为“+”“-”的字符, 先看一下栈是否为空,接着判断栈顶元素是否为“(”,若是,则继续将 c进栈,否则的话,将栈中的元素全部出栈, 直到栈空。④:若 c为“)”则将栈中所有符号弹栈并进入队列。⑤:若 c为“#”,则结束,并将栈中的剩余的符号全部入队列。⑥:打印队列中的,出队打印。 else if 三. 程序流程图开始输入一个字符串 c C!= ’#’ Ifc!= ’.’||c<9||c>0 若为数存入数组,i=1 else if If(!c!= ’.’||c<9||c>0 ) 将数组中第 0 个存到队列中 If(c'*'||c= ’/’||c= ’(’) 栈顶出栈给 c2 If(c2= ’*’||c2= ’/’c2进队列 else if c2进栈后c进栈 else if If(c'+'||c= ’-’)c入栈 If 栈空栈顶元素出栈 else if If(c= ’)’)栈顶出栈入队操作 while 栈空栈顶出栈给 e If(e!= ’(’栈顶出栈入队操作 e== ’(’ else if入栈 while 栈空 e== ’#’栈中剩余的出栈入队操作结束四. 类关系图(1) .头文件: #include<> #include<> (2) 宏定义: #define OK1 #define ERROR 0 #define STACK_SIZE 20 #define STACK_INCREMENT 10 #define QUEUE_SIZE 20 (3) 栈的定义结构体 typedef int Status; typedef char StackElemtype; //栈的类型 typedef struct Stack{ StackElemtyp