《学士学位论文—-数据结构课程设计表达式翻译.doc》由会员分享，可在线阅读，更多相关《学士学位论文—-数据结构课程设计表达式翻译.doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程考核报告 表达式的翻译学号： 姓名： 专业： 软件工程专业 班级： 15级云计算1班 指导教师： 南 阳 理 工 学 院 软 件 学 院2016年12月 目录1.需求分析-3 1.1问题描述-3 1.2基本要求-32.系统设计-33.程序流程图-44.类关系图-65. 实现代码-76.个人总结-77.参考书目-7一需求分析 1.1问题描述 编写完整程序，将中缀表达式翻译成后缀表达式。表达式由操作数 ( 变量 ) 、操作 ( 运算符 ) 以及小括弧 “ （ ” 和 “ ） ” 组成，其中：(1)操作包括算术运算、关系运算和逻辑运算三类；(2)操作数为单个字符或由字母和数字任意多个字符
2、构成；(3)能够识别出简单的错误，如括弧不匹配。 1.2 基本要求 输入：中缀表达式，80个字符以内。 输出：运算结果 功能：将中缀表达式转化为后缀表达式 二系统设计 根据题目要求，将中缀表达式转化为后缀表达式。问题的解决方案有两种，分别是利用栈结构实现算数表达式的四则运算或者利用二叉树把中缀表达式转化为前缀表达式，我选择栈结构与树结构相结合来实现算数表达式的转化。算法思想：运用栈和队列来将中缀转换为后缀，栈用来储存字符，队列用来存储后缀表达式。：输入字符串c，若是数字的话直接进入队列，若是符号，为*/（，则线检查栈中的栈顶元素，前提是栈不为空，若栈不为空的话，栈顶元素为*|/，则先将栈中的元
3、素入队，如果栈顶是+-这些优先级小的，则直接将c入栈。：如果c是优先级为“+”“-”的字符，先看一下栈是否为空，接着判断栈顶元素是否为“（”，若是，则继续将c进栈，否则的话，将栈中的元素全部出栈，直到栈空。：若c为“）”则将栈中所有符号弹栈并进入队列。：若c为“#”，则结束，并将栈中的剩余的符号全部入队列。：打印队列中的，出队打印。 开始三 程序流程图输入一个字符串celse ifC!=#Ifc!=.|c0If(!c!=.|c0)若为数存入数组,i=1else if将数组中第0个存到队列中If(c*|c=/|c=()else ifIf(c+|c=-)If(c=)If栈空栈顶出栈给c2while
4、栈空栈顶出栈给eelse ifIf(c2=*|c2=/)栈顶出栈入队操作If(e!=()栈顶出栈入队操作栈顶元素出栈c2进栈后c进栈c2进队列c入栈else ife=(else ifwhile栈空e=#入栈栈中剩余的出栈入队操作结束四 类关系图(1) .头文件：#include#include(2)宏定义：#define OK 1#define ERROR 0#define STACK_SIZE 20#define STACK_INCREMENT 10#define QUEUE_SIZE 20(3) 栈的定义结构体typedef int Status;typedef char StackEle
5、mtype; /栈的类型typedef struct Stack StackElemtype* base; StackElemtype* top; int stackSize;Stack;(5)初始化栈：Status StackInit(Stack* s)(6)出栈：Status Pop(Stack* s,StackElemtype* value)(7)进栈：Status Push(Stack* s,StackElemtype value)(8)求栈的长度：int StackLength(Stack s)(9)定义队列的结构体：typedef double QueueElemtype;type
6、def char QueueOperatorValue;typedef struct QueueNode /定义队列结构体 QueueElemtype data; QueueOperatorValue operator; struct QueueNode* next; int flag;QueueNode,*QueueNodePtr;typedef struct Queue QueueNodePtr front; QueueNodePtr rear;Queue;(10)初始化队列Status QueueInit(Queue* q)(11)队列的插入：Status QueueInsert(Que
7、ue* q,QueueElemtype value)(12)出队列Status QueueInsert_operatorValue(Queue* q,QueueOperatorValue value)(13)中缀转后缀函数Status Infix2Postfix(Queue* q)(14)打印后缀表达式Status ShowQueue(Queue q)(15)主函数int main() Queue q; QueueInit(&q); Infix2Postfix(&q); ShowQueue(q); return 0;五 运行截图六实现代码#include#include#define OK 1
8、#define ERROR 0#define STACK_SIZE 20#define STACK_INCREMENT 10#define QUEUE_SIZE 20typedef int Status;typedef char StackElemtype; /栈的类型typedef struct Stack StackElemtype* base; StackElemtype* top; int stackSize;Stack;Status StackInit(Stack* s) /初始化栈 s-base = (StackElemtype*)malloc(sizeof(StackElemty
9、pe) * STACK_SIZE); /申请栈的空间 if( !s-base ) return ERROR; s-top = s-base; s-stackSize = STACK_SIZE; return OK;Status Pop(Stack* s,StackElemtype* value) /出栈操作 if( s-base = s-top ) printf(nstack emptyn); return ERROR; *value = *(-(s-top); return OK;Status Push(Stack* s,StackElemtype value) /进栈操作 if( s-to
10、p - 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 StackLength(Stack s) /求栈的长度 return s.
11、top - s.base;typedef double QueueElemtype;typedef char QueueOperatorValue;typedef struct QueueNode /定义队列结构体 QueueElemtype data; QueueOperatorValue operator; struct QueueNode* next; int flag;QueueNode,*QueueNodePtr;typedef struct Queue QueueNodePtr front; QueueNodePtr rear;Queue;Status QueueInit(Queu
12、e* 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 = (QueueNodePtr)malloc(sizeof(QueueNode); if( !new ) return ERROR; new-data = value
13、; 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 = (QueueNodePtr)malloc(sizeof(QueueNode); if( !new ) return ERROR; new-operator = value; new-flag = 0; new-next = NULL; q-rear-next =
14、new; q-rear = new; return OK;/利用栈将中缀表达式转化为后缀表达式：Status Infix2Postfix(Queue* q) Stack s; StackInit(&s); char c,e; char bufferDigit10; int i = 0; double longDigit; printf(n); printf(n); printf(n); printf( n); printf(n); printf( * 请输入表达式 *n); printf( * 结束符号为# *n); scanf(%c, &c); while( # != c) while( c
15、 = 0 | . = c ) bufferDigiti+ = c; bufferDigiti = 0; scanf(%c, &c); if(!(c = 0 ) | . = c ) longDigit = atof(bufferDigit); QueueInsert(q,longDigit); i = 0; if( ( = c | * = c | / = c ) if(c=/|c=*) Pop(&s, &e); if(e=/|e=*) QueueInsert_operatorValue(q, e); if(e=+|e=-) Push(&s,e); Push(&s, c); else if( +
16、= c | - = c ) if( !StackLength(s) ) Push(&s, c); else Pop(&s, &e); while( ( != e ) QueueInsert_operatorValue(q, e); if( StackLength(s) = 0 ) break; else Pop(&s, &e); if( ( = e ) Push(&s, e); Push(&s, c); else if( ) = c ) Pop(&s, &e); while( ( != e ) QueueInsert_operatorValue(q, e); Pop(&s, &e); else
17、 if( # = c) break; else printf(input ERROR!n); return ERROR; scanf(%c, &c); while(StackLength(s) Pop(&s, &e); QueueInsert_operatorValue(q, e); QueueInsert_operatorValue(q,#); return OK;Status ShowQueue(Queue q) printf(The Reverse Polish Notation is:); if(q.front = q.rear) printf(Queue Empty); return
18、 ERROR; QueueNodePtr p = q.front-next; while(p != q.rear) if(p-flag) printf(%g , p-data); else printf(%c , p-operator); p = p-next; printf(n); return OK;int main() Queue q; QueueInit(&q); Infix2Postfix(&q); ShowQueue(q); return 0;七. 个人总结这个课程设计为期一周，在每一次的课程设计都给我很大的收获，至少是能彻底的把思想给明白，首先，在写这个课程设计之前，一直都在想后缀的优点和他的功能，每一次电脑运算的时候，转换成后缀都不需要进行运算符的优先级比较，这是一回事，另外后缀运算能力明显提升，时间复杂度提升不少。在写的过程中有一点没有考虑进去，我的思路是在遇到乘号和除号的时候直接入栈，结果经过老师的验收把这个bug给找出来，经过仔细思考把代码给改正确了，所以说，如果直接把思想能够弄清的话，那么写代码是很轻松的。以后要把代码的思想牢牢掌握在脑中。这样才能提升自己的编程能力。 八.参考书目1 谭浩强 C+程序设计（第三版）清华大学出版社2 严蔚敏 数据结构（C语言版）清华大学出版社 19993 与所用编程环境相配套的C+相关的资料