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

目录1. 需求分析31.1问题描述31.2基本要求32. 系统设计33. 程序流程图44. 类关系图65. 实现代码76. 个人总结77. 参考书目7一需求分析1.1问题描述编写完整程序，将中缀表达式翻译成后缀表达式。表达式由操作数（变 量）、操作（运算符）以及小括弧“（”和“）”组成，其中：（1） 操作包括算术运算、关系运算和逻辑运算三类；（2）操作数为单个字符或由字母 和数字任意多个字符构成；（3）能够识别出简单的错误，如括弧不匹配。1.2基本要求输入：中缀表达式，80个字符以内。输出：运算结果功能：将中缀表达式转化为后缀表达式二系统设计根据题目要求，将中缀表达式转化为后缀表达式。问题的解决方案有两种， 分别是利用栈结构实现算数表达式的四则运算或者利用二叉树把中缀表达式转 化为前缀表达式，我选择栈结构与树结构相结合来实现算数表达式的转化。算法思想： ：运用栈和队列来将中缀转换为后缀，栈用来储存字符，队列用来存储后 缀表达式。 ：输入字符串c,若是数字的话直接进入队列，若是符号，为则线检查栈中的栈顶元素，前提是栈不为空，若栈不为空的话，栈顶元素为* II 则先将栈中的元素入队，如果栈顶是+ -这些优先级小的，则直接 将c入栈。 ：如果c是优先级为“+” “-”的字符，先看一下栈是否为空，接着判断栈 顶元素是否为“（”，若是，则继续将c进栈，否则的话，将栈中的元素全部出栈， 直到栈空。 ：若c为“）”则将栈中所有符号弹栈并进入队列。 ：若c为“#”，则结束，并将栈中的剩余的符号全部入队列。 ：打印队列中的，出队打印。If(!c!=.llc0将数组中第0.个存到队列中If（c，*，llc=，/，llc=，（，）f(c=)If栈空while栈空栈c顶2f进栈出入栈c栈进栈-If(c，+，llc=，-，)Ifc!=.llc0后e=(If(c2=*llc2=/元若为数else ifwhile栈空三程序流程图开始打 C!=#else if-存入数组,i=ielse ifelse ifelse ifelse栈中乘余的出栈入队操作结束I栈顶出栈给e、输入一个字符串c栈顶出栈给c2丿r1c2c进入队栈列1J-Jrr 1栈栈顶顶出出栈栈入入队队操操L作素四类关系图(1) .头文件：#includes tdio.h#includestdlib.h宏定义：#define OK 1#define ERROR 0#define STACK_SIZE 20#define STACK_INCREMENT 10#define QUEUE_SIZE 20(3)栈的定义结构体typedef int Status;typedef char St ackElem type;/栈的类型typedef struct StackStackElemtype* base;StackElemtype* top;int stackSize;Stack;(5)初始化栈：Status StackIni t(Stack* s)出栈：Status Pop(Stack* s,StackElemtype* value)进栈：Status Push(Stack* s,StackElemtype value)(8) 求栈的长度：int StackLength(Stack s)(9) 定义队列的结构体：typedef double QueueElemtype;typedef charQueueOperatorValue;/定义队列结构体typedef struct QueueNodeQueueElemtype data;QueueOperatorValue operator;struct QueueNode* next;int flag;QueueNode,*QueueNodePtr;typedef struct QueueQueueNodePtr front;QueueNodePtr rear;Queue;(10) 初始化队列Status QueueIn it( Queue* q)(11) 队列的插入：Status QueueInsert( Queue* q,QueueElemtype value)(12) 出队列Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value)(13) 中缀转后缀函数Status lnfix2Postfix(Queue* q)(14) 打印后缀表达式Status ShowQueue(Queue q)(15) 主函数int main()Queue q;Infix2Postfix(&q);ShowQueue(q);return 0;Status St acklni t(S tack* s)/初始化栈s-base = (StackElemtype*)malloc(sizeof(StackElemtype) * STACK_SIZE);/申请栈的空间if( !s-base )return ERROR;s-top = s-base;s-stackSize = STACK_SIZE;return OK;Status Pop(S tack* s,S tackElem type* value)/出栈操作if( s-base = s-top )printf (nstack emptyn);return ERROR;*value = *(-(s-to p);return OK;Status Push(S tack* s,S tackElem type value)/进栈操作if( s-top - s-base = s-stackSize)s-base = (StackElemtype*)realloc(s-base,sizeof(StackElemtype) * (STACK_INCREMENT +STACK_SIZE);if( !s-base )return ERROR;s-top = s-base + STACK_SIZE;s-stackSize = STACK_SIZE + STACK_INCREMENT;*(s-top) = value;s_top+;return OK;/求栈的长度int St ackLeng th(S tack s)ret urn s.top - s.base;typedef double QueueElemtype;typedef charQueueOperatorValue;typedef struct QueueNodeQueueElemtype data;QueueOperatorValue operator; struct QueueNode* next;int flag;QueueNode,*QueueNodePtr;typedef struct QueueQueueNodePtr front;QueueNodePtr rear;Queue;/定义队列结构体Status QueueIni t(Queue* q)q-front 二(QueueNodePtr)malloc(sizeof(QueueNode);if( !q-front )return ERROR;q-rear = q-front;q-rear-next = NULL;return OK;Status QueueInsert( Queue* q,QueueElemtype value)QueueNodePtr new;new = (QueueNodeP tr)malloc(sizeof(QueueNode);if( !new )return ERROR;new-data = value;new-flag = 1;new-next 二 NULL;/队列初始化/队列插入q-rear-next 二 new;q-rear = new;return OK;Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value)QueueNodePtr new;new = (QueueNodeP tr)malloc(sizeof(QueueNode);if( !new )return ERROR;new-operator = value;new-flag = 0;new-next 二 NULL;q-rear-next 二 new;q-rear = new;return OK;/利用栈将中缀表达式转化为后缀表达式:Status lnfix2Pos tfix(Queue* q)Stack s;St ackIn it(&s);char c,e;char bufferDigit10;int i = 0;double longDig it;printf (n);printf (n);prin tf (n);printf(”欢迎使用表达式翻译器n);prin tf (n);printf(”*请输入表达式*n);printf(”*结束符号为# *n);scanf(%c, & c);while( # != c)while( c = 0 | . = c )bufferDigiti+ = c;bufferDigiti = 0;scanf(%c, & c);if(!(c = 0 ) |. = c ) longDig it = ato f(bufferDig it); QueueInsert(q, longDigit);i = 0;return OK;int main()Queue q;Queuein it(&q); lnfix2Postfix(&q); ShowQueue(q);return 0;七.个人总结这个课程设计为期一周，在每一次的课程设计都给我很大的收获，至少是能彻底 的把思想给明白，首先，在写这个课程设计之前，一直都在想后缀的优点和他的 功能，每一次电脑运算的时候，转换成后缀都不需要进行运算符的优先级比较， 这是一回事，另外后缀运算能力明显提升，时间复杂度提升不少。在写的过程中 有一点没有考虑进去，我的思路是在遇到乘号和除号的时候直接入栈，结果经过 老师的验收把这个bug给找出来，经过仔细思考把代码给改正确了，所以说，如 果直接把思想能够弄清的话，那么写代码是很轻松的。以后要把代码的思想牢牢 掌握在脑中。这样才能提升自己的编程能力。八.参考书目1 谭浩强C+程序设计（第三版）清华大学出版社2 严蔚敏数据结构（C语言版）清华大学出版社19993 与所用编程环境相配套的C+相关的资料