算术表达式求值演示

1、实习报告题目：算术表达式求值演示。一、需求分析1. 以字符序列的形式从终端输入语法正确的、不含变量的整数表 达式。2. 利用教科书表给出的算符优先关系，实现对算数四则混合运算 表达式的求值。3. 仿照教科书的例子在求值中运用符栈、运算数栈、输入字符和 主要操作的变化过程。4. 程序执行的命令包括：(1) 构造空栈；(2) 判断符号优先级 ;(3) 判断是否为七种运算符之一 ;(4) 运算求解算术表达式。5. 测试数据(1) 3*(7-2);(2) 8;(3) 1+2+3+4;(4) 88-1*5;(5) 1024*4/8;(6) (20+2)*(6/2);(7) 3-3-3;(8) 8/(9-

2、9);(9) 2*(6+2*(3+6*(6+6);(10) (6+6)*6+3)*2+6)*2;二、概要设计1. 设定栈的抽象数据类型定义：ADT Stack数据对象：D=ai |a i CharSet,i=1,2,，n,n 0数据关系：R仁| a i -1, ai D,i=2,，n 基本操作：InitStack (&S)操作结果：构造一个空栈 S。GetTop (S ， &e)初始条件：栈 S 已存在。操作结果：若栈 S 不空，则以 e 返回栈顶元素。Push(&S, e)初始条件：栈 S 已存在。操作结果：在栈 S 的栈顶插入新的栈顶元素 e。Pop(&S, &e)初始条件：栈 S 已存在

3、。操作结果：删除S的栈顶兀素，用e返回其值。 ADT Stack2. 设定运算表达式的抽象数据类型为：ADT EvaluateExpression数据对象：D=ai | a i为数字及运算符，i=1,2，n,n 0 数据关系： R1= 基本操作：Precede(a1 , a2)初始条件：字符al, a2存在。 操作结果：判定运算符的优先级In( d )初始条件：字符 d 存在。操作结果：判断 c 是否为七种运算符之一Operate(a, theta, b )初始条件：字符 a, theta, b 存在。 操作结果：运算表达式结果。 ADT EvaluateExpression3. 本程序包含

4、3 个模块：(1 )主程序模块：int main()初始化；do接受命令：处理命令：return 0;(2) 栈模块实现栈抽象数据类型(3) 求解算术表达式模块实现算术表达式数据类型 各模块之间的调用关系如下：主程序模块V栈模块V求解算术表达式模块三、详细设计1. 数据类型、字符类型。typedef double SElemType; 类型typedef struct SqStack SElemType *base;SElemType *top;int stacksize;SqStack;栈的基本操作设置如下：void InitStack (SqStack &S)求解算术表达式的伪算法SEle

5、mType EvaluateExpression( )SqStack OPTR,OPND;Push(OPND,c-48);c=getchar();elsecouterror!输入错误 !endl;exit(-1);GetTop(OPTR,e);GetTop(OPND,e);return e;4. 主函数和其他函数的伪算法int main()数的调用关系图反映了演示程序的结构层次：主程序JJInitialization ReadCommand InterpretInitEvaluateExpressionPrintEvaluateExpressionJJInitStack Push Pop Ge

6、tTop四、调试分析1. 这次作业思路比较简单， 核心问题就是表达式的运算， 要区分运算 符的优先顺序。 通过运用栈后进先出的特点实现算法功能， 调用 push 和 pop 等函数，实现一系列操作。2. 调试过程中，起初想打换行符时打成了 ，忘了打字母 n, 结果 程序调试总是有错误，改成 n 后便成功运行了，可见，细节之处 也很重要3. 运用了很多的栈的基本操作， 让我对栈的内容熟悉了不少， 收获很 大。4本题中时间复杂度为 O(n)五、用户手册本程序的运行环境为DOS操作系统，执行文件为:六、测试结果(1) 请输入表达式:3*(7-2);结果为： 15(2) 请输入表达式：8;结果为： 8(3) 请输入表达式：1+2+3+4;结果为： 10(4) 请输入表达式：88-1*5;结果为： 82(5) 请输入表达式：1024*4/8;结果为： 512(6) 请输入表达式：(20+2)*(6/2);结果为： 6(7) 请输入表达式：3-3-3;结果为： -3(8) 请输入表达式：8/(9-9);结果为： erro