下载此文档

数据结构课程设计报告--表达式翻译.docx


文档分类:IT计算机 | 页数:约17页 举报非法文档有奖
1/17
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/17 下载此文档
文档列表 文档介绍
软件学院数据结构课程设计报告-- 表达式翻译指导老师:钱鸽学号: 1415925721 专业: 云计算班级:三班姓名:高笛 1. 需求分析 问题描述在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序设计时,借助栈实现。算法输入:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)操作符为+、-、*、/, 用#表示结束。算法输出:由中缀表达式转换为后缀表达式,如果不是括号配对的话则输出括号不配对。算法要点:设置运算符栈和括号配对的栈在进行表达式的译过程进行判断括号的配对问题。 基本要求设计友好的用户界面, 利用所学栈的方法对表达式的中缀和后缀之间的转换,并且实现对括号配对的判断。编写完整程序, 将中缀表达式翻译成后缀表达式。表达式由操作数( 变量)、操作( 运算符) 以及小括弧“(”和“)”组成,其中: 1) 操作包括算术运算、关系运算和逻辑运算三类; 2) 操作数为单个字符或由字母和数字任意多个字符构成; 3) 能够识别出简单的错误,如括弧不匹配。输入:中缀表达式, 80 个字符以内。输出:运算结果。 2 概要设计 总体功能结构表达式翻译是程序设计语言编译中的一个最基本的问题。它的实现是栈应用的一个典型例子。本程序使用通常使用的算法为“算符优先法”。在计算机中如果想要计算出一个表达式的值,则需要先将表达式转换为计算机能够识别的表达式, 即中缀表达式转换为后缀表达式。首先需要了解算数运算符的优先级等。即: 1) 先乘除,后加减。 2) 从左算到右。 3) 先括号内,后括号外。故若中缀表达式为: 1*2+(2-(6-4)*4)/2 。后缀则为: 12*264- 4*-2/+ 。算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。 数据结构设计利用一个顺序栈可以实现将中缀表达式转换为后缀表达式, 也能实现对括号是否匹配进行检测。通过从键盘输入字符算数表达式, 经运行后由屏幕输出转化后的后缀表达式。 程序原理栈( stack )是最常用和最重要的数据结构。操作运算符和左括号是放在栈中的,表达式的优先级处理也是基于栈来实现的,通过利用入栈和出栈来调整运算符的优先级。栈是限制在表的一端进行插入和删除的线性表(即一维数组)。允许插入删除的一端为栈顶,另一固定端为栈底。当表中没有元素时称为空栈。如图 2-1 所示,栈中有三个元素,进栈的顺序是 a、b、c,当需要出栈时其顺序为 c、b、a。所以栈又称为后进先出的线性表( Last In First Out ), 简称 LIFO 表。而在日常生活中,有很多后进先出的例子。在程序设计中, 常常需要使得与保存数据时相反顺序来使用这些数据, 这时就需要用一个栈来实现。对于栈,常做的基本运算有: (1 )栈初始化: Init_Stack(s) c 出栈入栈图 2-1 ab top 初始条件:栈 s 不存在操作结果:构造了一个空栈。(2 )判断栈空: Empty_Stack(s) 初始条件:栈s 已存在操作结果:若栈 s 为空栈返回为 1 ,否则返回为 0. (3 )入栈: Push_Stack(s,x) 初始条件:栈 s 已存在操作结果: 在栈 s 的顶部插入一个新元素 x,x 成为新的栈顶元素。栈发生变化。(4 )出栈: Pop_Stack(s) 初始条件:栈 s 存在且非空操作结果:栈s 的顶部元素从栈中删除, 栈中少了一个元素。栈发生变化。(5 )读栈顶元素: Top_Stack(s) 初始条件:栈 s 存在且非空操作结果:栈顶元素作为结果返回,栈不变化。栈可以用顺序表实现,称为顺序栈;也可以用链表实现,称为链栈。顺序栈和链栈的逻辑功能一样。顺序栈必须先开一定大小的内存空间, 执行起来简单并且速度快, 但可能溢出; 链栈的内存空间随用随开, 不会溢出; 但执行复杂( 不断地动态分配)且速度慢。 3 程序设计和流程图 程序具体设计定义一个顺序栈类 SqStack , 首先构造一个空栈, 包含的操作有进栈 Push() , 出栈 Pop() , 取栈顶元素 GetTop() , 判栈的长度 StackLen() 。利用这个顺序栈对中缀表达式进行检测, 若出错(主要为括号比匹配) ,给出出错提示;否则,将中缀表达式转换为后缀表达式。判断表达式的的正确和如何转换中缀表达式的过程, 共用了两个栈 s,s1 。第一个栈用来将输入的字符进行判断是否需要进行入栈, 而第二个栈则是用来存放小括号的, 用来判断括号是否配对的。首先就是对于输入进来的表达式进行过滤数字,如果是数字则不进栈直接输出。如果是操作符,先判断栈是不是空的

数据结构课程设计报告--表达式翻译 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数17
  • 收藏数0 收藏
  • 顶次数0
  • 上传人wsh309048309
  • 文件大小0 KB
  • 时间2016-05-16