数据结构_栈的应用—表达式求值课程设计.docVIP

《数据结构课程设计》报告 题目：栈的应用—表达式求值 专业 计算机科学与技术 学生姓名 班级 B计算机 学号 指导教师 完成日期 2012年1月11日 一、简介 栈是一种运算受限的线性表，仅允许在表的一端进行插入和删除。对一个栈最基本的操作包括进栈和出栈，即对栈的插入和删除。 表达式求值是程序设计语言编译中的一个基本问题，它的实现是栈应用的一个典型例子。 本实验的目的是设计一个表达式求值的程序。该程序必须可以接受包括(,),+,-,*,/,%和^(求幂运算符)的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。 输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有许多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。 输出要求：对于每一个表达式，将结果放在“output.txt”文件中每一行中。这个结果可能是值，也可能是错误信息“ERROR IN INFIX NOTATION” 二、算法设计 程序的整体算法分两步： 从“input。txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换成后缀表达式，将结果存放在一个temp文件中。 从temp文件中读取后缀表达式，并应用操作数栈Operands计算后缀表达式结果将结果输出到“output.txt”文件中。 为了实现算法，使用两个工作栈。一个称做OpHolder，用于寄存运算符；另一个称做Operands，用以寄存操作数或运算结果。算法的基本思想是： 首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素； 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。 具体算法如下： OperandType EvaluateExpression(){ InitStack(Operands); Push(Operands,#)； InitStack(Operands);c=getchar(); While(c!=#||GetTop(Operands)!=#) if(!In(c,OP)){Push((Operands,c);c=getchar();} else switch(Precede(GetTop(Operands),c)){ case: Push(Operands,c);c=getchar(); break case=: Pop(Operands,x); c=getchar(); break; case: Pop(Operands,theta); Pop(Operands,b); Pop(Operands,a); Push(Operands),Operate(a,theta,b)); berak } return GetTop(OPND); 三、测试与结果 设计针对程序的input.txt文件，并将运行结果与期望测试结果进行比较 输入数据： 输出数据： 测试项目 测试实例 期望测试结果 基本测试 3.00 3.00 1+2+3-4 2.00 1 + 2 3.00 4.99+5.99+6.99*1.06 18.39 (3*5*(4+8)%2) 0.00 2＾2＾3 256.00 2＾2.5＾3 50535.16 (2-4)＾3 -8.00 扩展测试 2.5-3.4/2+1*2 2.80 (2.5)*(3-2)+5.6-190%3＾2＾(1+1) -19.90 1+2+3 6.00 1*2*3 6.00 (1+2)*3+4/(5+1*4)+3.26 12.70 3+4-6.7+8 8.30 2.9*1.2+0.5-4%3/2+4＾(5-5) 4.48 2＾3-(5+2)/7*9 -1.00 50-3＾2＾2+4%2-7*(3) -52.00 (((2))-3） -1.00 2.5^2 6.25 2^(4.4-2.4) 4.00 2^(4.4-3.1) 2.46 (2-4)*3 -8.00 2-4)^(5-8) -0.13 容错测试 1+2( ERROR IN INFIX NOTATION 2/0 ERROR IN INFIX NOTATION 2%0 ERROR IN INFIX NOTATION (2-4)^3.1 ERROR IN INFIX NOTATION 2.5%2 ERROR IN INFIX NOTATION 2%2.5 ERROR IN INFIX NOTATION