表达式翻译课程设计报告.docx

软件学院数据结构课程设计报告 -表达式翻译 指导老师：钱鸽 学 号： 1415925721专 业： 云计算班 级：三班姓 名：高笛1. 需求分析 1.1问题描述 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）操作符为+、-、*、/，用#表示结束。 算法输出：由中缀表达式转换为后缀表达式，如果不是括号配对的话则输出括号不配对。 算法要点：设置运算符栈和括号配对的栈在进行表达式的译过程进行判断括号的配对问题。1.2基本要求 设计友好的用户界面，利用所学栈的方法对表达式的中缀和后缀之间的转换，并且实现对括号配对的判断。编写完整程序，将中缀表达式翻译成后缀表达式。表达式由操作数 ( 变量 ) 、操作 ( 运算符 ) 以及小括弧“（”和“）”组成，其中：1）操作包括算术运算、关系运算和逻辑运算三类；2）操作数为单个字符或由字母和数字任意多个字符构成；3）能够识别出简单的错误，如括弧不匹配。输入：中缀表达式，80个字符以内。输出：运算结果。2 概要设计2.1总体功能结构表达式翻译是程序设计语言编译中的一个最基本的问题。它的实现是栈应用的一个典型例子。本程序使用通常使用的算法为“算符优先法”。 在计算机中如果想要计算出一个表达式的值，则需要先将表达式转换为计算机能够识别的表达式，即中缀表达式转换为后缀表达式。首先需要了解算数运算符的优先级等。即：1） 先乘除，后加减。2） 从左算到右。3） 先括号内，后括号外。故若中缀表达式为：1*2+(2-(6-4)*4)/2。后缀则为：12*264- 4*-2/+。算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。2.2 数据结构设计利用一个顺序栈可以实现将中缀表达式转换为后缀表达式，也能实现对括号是否匹配进行检测。通过从键盘输入字符算数表达式，经运行后由屏幕输出转化后的后缀表达式。2.3 程序原理栈（stack）是最常用和最重要的数据结构。操作运算符和左括号是放在栈中的，表达式的优先级处理也是基于栈来实现的，通过利用入栈和出栈来调整运算符的优先级。栈是限制在表的一端进行插入和删除的线性表（即一维数组）。允许插入删除的一端为栈顶，另一固定端为栈底。当表中没有元素时称为空栈。如图2-1所示，栈中有三个元素，进栈的顺序是a、b、c，当需要出栈时其顺序为c、b、a。所以栈又称为后进先出的线性表（Last In First Out）,简称LIFO表。而在日常生活中，有很多后进先出的例子。在程序设计中，常常需要使得与保存数据时相反顺序来使用这些数据，这时就需要用一个栈来实现。对于栈，常做的基本运算有： （1）栈初始化：Init_Stack(s) c出栈 入栈 图2-1 a b 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 程序设计和流程图3.1程序具体设计定义一个顺序栈类SqStack，首先构造一个空栈，包含的操作有进栈Push()，出栈Pop()，取栈顶元素GetTop()，判栈的长度StackLen()。利用这个顺序栈对中缀表达式进行检测，若出错（主要为括号比匹配），给出出错提示；否则，将中缀表达式转换为后缀表达式。判断表达式的的正确和如何转换中缀表达式的过程，共用了两个栈 s,s1。第一个栈用来将输入的字符进行判断是否需要进行入栈，而第二个栈则是用来存放小括号的，用来判断括号是否配对的。首先就是对于输入进来的表达式进行过滤数字，如果是数字则不进栈直接输出。如果是操作符，先判断栈是不是空的，是的话直接进栈，不是空栈，则需要将栈内的元素出栈判断是哪个操作符，进而判断其优先级。在这个过程中有两个问题： 第一就是栈内的操作符与栈外的操作符是同级别的，那么按照从左到右的顺序先进行栈内的操作符运算，再运算栈外的。 第二点如果栈内栈外的操作符不同级，要么是大于，要么是小于，当是大于的情况下，则直接进栈即可，否则需要判断s栈内的头元素是不是左括号，如果是则说明这个字符在括号内，先运算括号内的，即直接进栈。如果这个字符前面没有左括号，则将栈内出栈的元素输出。开始3.2流程图输入“#”输出ch输入chCh为操作数？是比较优先级否输出退 出4. 源代码#include#include#define STACK_INIT_SIZE 80#define STACKINCREMENT 10#define MAXBUFFER 10typedef int Status;typedef char ElemType;typedef struct ElemType *base;ElemType *top;int stackSize;sqStack; Status InitStack(sqStack *s)s-base=(ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType);if(!s-base) exit(0);s-top=s-base;s-stackSize=STACK_INIT_SIZE;Status Push(sqStack *s,ElemType e)if(s-top - s-base = s-stackSize)s-base = (ElemType *)realloc(s-base,(s-stackSize + STACKINCREMENT)* sizeof(ElemType);if(!s-base) exit(0);s-top=s-base + s-stackSize;s-stackSize=s-stackSize+STACKINCREMENT; *(s-top)=e;s-top+;Status Pop(sqStack *s,ElemType *e)if(s-top = s-base)return;*e= *-(s-top);Status Gettop(sqStack *s)if(s-top = s-base) return ;return *(s-top-1);int StackLen(sqStack s)return (s.top-s.base);int main()int j,sign=1; sqStack s,s1;char e,c;InitStack(&s);InitStack(&s1);printf(请输入中缀表达式，以#作为结束标志：n);scanf(%c,&c);printf(中缀表达式转为后缀表达式为:n);while(c!=#) while(c=0&c=9)printf(%c,c);scanf(%c,&c);if(c9)printf( );if()=c) if(Gettop(&s1)=()Pop(&s1,&c);elsesign=0;break;Pop(&s,&e);while(!=e)printf(%c ,e);Pop(&s,&e);else if(+=c | -=c )if(!StackLen(s)Push(&s,c);elsedoPop(&s,&e);if(=e)Push(&s,e);else printf(%c ,e);while(StackLen(s) &(!=e);Push(&s,c);else if(*=c | /=c) if(!StackLen(s) Push(&s,c);elsedoPop(&s,&e);if(=e | +=e | -=e)Push(&s,e);Push(&s,c);else printf(%c ,e);Push(&s,c);break;while(StackLen(s) &(!=e & +!=e & -!=e);else if(=c) Push(&s1,c); Push(&s,c);else if(#=c) break; elseprintf(您输入有误！);return -1; if(sign=0) break; else c=getchar(); if(StackLen(s1) /最后查看栈中是否为空 sign=0; while(StackLen(s)Pop(&s,&e);printf(%c ,e); if(sign=0) printf(n But该算术表达式圆括号配对错误!n); return 0;5. 课程总结 通过几天时间的课程设计，自己对于数据结构才算是真正的入门了。在这个过程中也遇到不少问题，也正是国为这些问题引发的思考给我带来了收获。从当初拿着问题不知从何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变。我发现无论是专业知识还是动手能力，自己都有很大程度的提高。 在实际上机操作过程中，不仅是让我们了解数据结构的基础理论知识，更重要的是培养解决实际