数据结构 表达式求值(中缀)实验报告

1、江西理工大学软件学院数据结构课程设计报告20122013学年第一学期课程名称 数 据 结 构 设计题目 表达式求值 专业班级 姓 名 学 号 指导教师 2012年 11 月 30日目 录一设计题目.3二需求分析.3 2.1问题描述.32.2表达式程序分析.3三概要设计.33.1基本思想.33.2栈的抽象数据类型定义.4四基本算法.44.1基本操作思想44.2基本操作5五测试结果7六源代码8七心得体会12一 设计题目 表达式求值（中缀）二 需求分析2.1 问题描述：在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严

2、格地从左到右进行，在程序设计时，借助栈实现。2.2 表达式求值程序分析：主要利用栈和数组，把运算的先后步骤进行分析并实现简单的运算，以字符列的形式从终端输入语法的正确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则运算的求值，在求值中运用栈、运算栈、输入字符和主要操作的变化过程。该程序相当于一个简单的计算机计算程序，只进行简单的加减乘除和带括号的四则运算。三 概要设计3.1 基本思想（中缀表达式求值）要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，要了解算术四则运算的规则即：a先乘除后加减； b从左到右计算；c 先括号内，后括号外

3、。下表定义的运算符之间的关系: ba+-*/（）#+_*/(#= 为了实现运算符有限算法，在程序中使用了两个工作栈。分别是：运算符栈OPTR,操作数栈OPND.基本思想：（1） 首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2） 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈得栈顶运算符比较优先级后作相应操作。若大于栈顶元素优先级则如栈，若小于栈顶元素优先级则退出和OPND得操作数进行计算，并把计算结果如OPND栈。直至整个表达式求值完毕（即OPND栈的栈顶元素和当前读入的字符均为“#”）。3.2 栈的抽象数据类型的定义：ADT Stack 数据

4、对象：D=ai| aiIntegerSet，i=1，2，n，n0数据关系：R1=ai-1，ai|ai-1， aiD， i=1，2，n 约定an端为栈顶，ai端为栈底 四操作算法4.1基本操作思想： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty（S） 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回True，否则返回False。 StackLength（S） 初始条件：栈S已存在。 操作结果：返回S

5、的元素个数，即栈的长度。 GetTop（S，&e） 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push（&S，e） 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop（&S，&e） 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverse（S，visit（） 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit（）。一旦visit（）失败，则操作失败。ADT Stack4.2 基本操作中缀表达式求值，在转换和计算中主要用到了下列几个函数1) char Precede(c

6、har t1, char t2)作用：判断运算符t1和t2的优先关系。如：case +: case -: if(t1=(| t1=#) f=;/t1;/t1t2break; 2）bool IsOperator(char c)作用：判断c是否为7种运算符之一bool IsOperator(char c)/判断c是否为7种运算符之一switch(c)case +:case -:case *:case /:case (:case ):case #: return true;default: return false;3）int Operate(int a, char oper, int b)作用：i

7、nt Operate(int a, char oper, int b)switch(oper)case +:return a+b;case -:return a-b;case *:return a*b;default:break;return a/b; 4）int EvaluateExpression()作用：中缀表达式求值的算法int EvaluateExpression()stack OPTR, OPND;/设置操作数栈和操作符栈int a,b,d,x;char c;OPTR.push(#);c=getchar();x=OPTR.top();while(c!=#|x!=#)if(IsOpe

8、rator(c)switch(Precede(x,c)case:x=OPTR.top();OPTR.pop();b=OPND.top();OPND.pop();a=OPND.top();OPND.pop();OPND.push(Operate(a,x,b);else if(c=0&c=0&c=9)d = d*10+c-0;c = getchar();OPND.push(d);elsecout 出现非法字符 endl;exit( 0 );x=OPTR.top();x=OPND.top();if(OPND.empty()cout 表达式不正确# endl;exit( 0 );return x; 五

9、 测试结果 六源代码 中缀表达式求值.cpp#include #include using namespace std;int EvaluateExpression();int main()cout 请输入算术表达式,负数要用(0-正数)表示n;cout EvaluateExpression() endl;return 0;char Precede(char t1, char t2)/判断t1,t2两符号的优先关系(#用#代替)char f;switch(t2)case +:case -:if(t1=(| t1=#)f=;/t1;/t1t2break;case *:case /:if(t1=*

10、|t1=/|t1=)f=;/t1t2elsef=;/t1t2break;case (:if(t1=)cout 括号不匹配 endl;exit( 0 );elsef=;/t1t2break;case ):switch(t1)case (: f = =; /t1=t2break;case #: cout 缺乏左括号 ;/t1t2break;case #: switch(t1)case #: f= =;/t1=t2break;case (:cout 缺乏右括号 ;/t1t2return f;bool IsOperator(char c)/判断c是否为7种运算符之一switch(c)case +:ca

11、se -:case *:case /:case (:case ):case #: return true;default: return false;int Operate(int a, char oper, int b)/做运算a theta b,返回运算结果switch(oper)case +:return a+b;case -:return a-b;case *:return a*b;default:break;return a/b;int EvaluateExpression()stack OPTR, OPND;/设置操作数栈和操作符栈int a,b,d,x;char c;OPTR.p

12、ush(#);c=getchar();x=OPTR.top();while(c!=#|x!=#)if(IsOperator(c)switch(Precede(x,c)case:x=OPTR.top();OPTR.pop();b=OPND.top();OPND.pop();a=OPND.top();OPND.pop();OPND.push(Operate(a,x,b);else if(c=0&c=0&c=9)d = d*10+c-0;c = getchar();OPND.push(d);elsecout 出现非法字符 endl;exit( 0 );x=OPTR.top();x=OPND.top(

13、);if(OPND.empty()cout 表达式不正确# endl;exit( 0 );return x; while(ij);ri=r0;c+;q(r，s，j-1);q(r，j+1，t);七 附录和设计心得体会课程实验不仅要求对课本知识有较深刻的了解，同时要求我们有较强的思维和动手能力，需要进一步了解编程思想和编程技巧。通过课程实验，使我对课本知识掌握的更加深刻，增强了自己的思维和动手能力。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。 程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足，在以后的上机中应更加注意，同时体会到C+具有的语句简洁，使用灵活，执行效率高等特点。我通