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

数据结构课程设计-表达式翻译.doc:..数据结构课程考核报告表达式的翻译学号: 姓名: 专业:软件工程专业班级:15级云计算1班指导教师: 7—・,将中缀表达式翻译成后缀表达式。表达式由操作数(变量)、操作(运算符)以及小括弧“(”和“)”组成,其中:(1)操作包括算术运算、关系运算和逻辑运算三类;(2)操作数为单个字符或由字母和数字任意多个字符构成;(3)能够识别出简单的错误,如括弧不匹配。:中缀表达式,80个字符以内。输出:运算结果功能:,将中缀表达式转化为后缀表达式。问题的解决方案有两种,分别是利用栈结构实现算数表达式的四则运算或者利用二叉树把中缀表达式转化为前缀表达式,我选择栈结构与树结构相结合来实现算数表达式的转化。算法思想:©:运用栈和队列來将屮缀转换为后缀,栈用來储存字符,队列用來存储后缀表达式。②:输入字符串c,若是数字的话直接进入队列,若是符号,为则线检查栈中的栈顶元素,前提是栈不为空,若栈不为空的话,栈顶元素为仔‘II 则先将栈中的元素入队,如果栈顶是'+ 这些优先级小的,则直接将C入栈。(§):如果C是优先级为“+”“・”的字符,先看一下栈是否为空,接着判断栈顶元素是否为“(”,若是,则继续将C进栈,否则的话,将栈中的元素全部岀栈,肓到栈空。④:若C为“)”则将栈中所有符号弹栈并进入队列。⑤:若C为“#”,则结束,并将栈屮的剩余的符号全部入队列。打印队列中的,出队打印。(1).头文件:#include<>#include<>(2)宏定义:#defineOK1#defineERROR0#defineSTACKSIZE20#defineSTACK_INCREMENT10#defineQUEUE_SIZE20(3)栈的定义结构体typedefintStatus;typedefcharStackElemtype; //栈的类型typedefstructStack{StackElemtype*base;StackElemtype*top;intstackSize;)Stack;(5)初始化栈:StatusStackInit(Stack*s)⑹出栈:StatusPop(Stack*sFStackElemtype*value)⑺进栈:StatusPush(Stack*s,StackElemtypevalue)⑻求栈的长度:intStackLength(Stacks)(9)定义队列的结构体:typedefdoubleQueueElemtype;typedefchar QueueOperatorVaIue;〃定义队列结构体typedefstructQueueNode{QueueElemtypedata;QueueOperatorValueoperator;struetQueueNode*next;intflag;)QueueNode,*QueueNodePtr;typedefstructQueue{QueueNodePtrfront;QueueNodePtrrear;(Queue;(10)初始化队列StatusQueueInit(Queue*q)CM)队列的插入:StatusQueueInsert(Queue*qFQueueElemtypevalue)(12)出队列StatusQueueInsert_operatorVaIue(Queue*qFQueueOperatorValuevalue)Cl3)中缀转后缀函数StatusInfix2Postfix(Queue*q)(14)打印后缀表达式StatusShowQueue(Queueq)(15)主函数intmain(){Queueq;QueueInit(&q);lnfix2Postfix(&q);ShowQueue(q);return0;)■ G:\程序邂结构天作业题目\表达式翻译exe〈欢迎使用表达式翻译器〉*^L*a^L*a^L*a^L*a^L**^L**^L*.Y••Y…Y…Y…Y…Y…Y…Y…Y••'^L**^L*a^L*a^L*a^L*a^L**^L**^L*.Y••Y…Y…Y…Y…Y…Y…Y…Y•*'^L**^L*a^L*a^L*a^L*a^L**^L**^L*.Y••Y…Y…Y…Y…Y…Y…Y…Y•*'^L**^L*a^L*a^L*a^L*a^L**^L**^L*