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

数据结构课程考核报告

表达式的翻译
学号: 1515925640
姓名: 王伊庆
专业: 软件工程专业
班级: 15级云计算1班
指导教师: 钱鸽
南阳理工学院软件学院
2016年12月
目录
-------------------------------------------------------------------3
---------------------------------------------------------------3
---------------------------------------------------------------3
-------------------------------------------------------------------3
-----------------------------------------------------------------4
-------------------------------------------------------------------6
5. 实现代码------------------------------------------------------------------7
-------------------------------------------------------------------7
-------------------------------------------------------------------7


编写完整程序,将中缀表达式翻译成后缀表达式。表达式由操作数( 变量) 、操作( 运算符) 以及小括弧“( ”和“) ”组成,其中:(1)操作包括算术运算、关系运算和逻辑运算三类;(2)操作数为单个字符或由字母和数字任意多个字符构成;(3)能够识别出简单的错误,如括弧不匹配。
基本要求
输入:中缀表达式,80个字符以内。
输出:运算结果
功能:将中缀表达式转化为后缀表达式

根据题目要求,将中缀表达式转化为后缀表达式。问题的解决方案有两种,分别是利用栈结构实现算数表达式的四则运算或者利用二叉树把中缀表达式转化为前缀表达式,我选择栈结构与树结构相结合来实现算数表达式的转化。
算法思想:
①:运用栈和队列来将中缀转换为后缀,栈用来储存字符,队列用来存储后缀表达式。
②:输入字符串c,若是数字的话直接进入队列,若是符号,为‘*’‘/’‘(’,则线检查栈中的栈顶元素,前提是栈不为空,若栈不为空的话,栈顶元素为‘*’||‘/’,则先将栈中的元素入队,如果栈顶是‘+’‘-’这些优先级小的,则直接将c入栈。
③:如果c是优先级为“+”“-”的字符,先看一下栈是否为空,接着判断栈顶元素是否为“(”,若是,则继续将c进栈,否则的话,将栈中的元素全部出栈,直到栈空。
④:若c为“)”则将栈中所有符号弹栈并进入队列。
⑤:若c为“#”,则结束,并将栈中的剩余的符号全部入队列。
⑥:打印队列中的,出队打印。

开始
程序流程图
输入一个字符串c
else if
C!=’#’
Ifc!=’.’||c<9||c>0
If(!c!=’.’||c<9||c>0)
若为数
存入数组,i=1
else if
将数组中第0个存到队列中
If(c'*'||c=’/’||c=’(’)
else if
If(c'+'||c=’-’)
If(c=’)’)
If栈空
栈顶出栈给c2
while栈空
栈顶出栈给e
else if
If(c2=’*’||c2=’/’)
栈顶出栈入队操作
If(e!=’(’
’)
栈顶出栈入队操作
栈顶元素出栈
c2进栈后c进栈
c2进队列
c入栈
else if
e==’(’
else if
while栈空
e==’#’
入栈
栈中剩余的出栈入队操作
结束
类关系图
.头文件:
#include<>
#include<>
宏定义:
#define OK 1
#define ERROR 0
#define STACK_SIZE 20
#define STACK_INCREMENT 10
#define QUEUE_SIZE 20
栈的定义结构体
typedef int S