算数表达式求值详解.docx

成绩评定教师签名 嘉应学院 计算机学院 《数据结构》实验报告 课程名称：数据结构开课学期：2016-2017学年第1学期班 级：1401指导老师：钟治初实验题目：算数表达式求值学 号：141110043姓 名：苏永达提交时间：2016年12月27日 一、 问题描述 1. 实验题目：算术表达式的求值。 2. 基本要求：以字符形式输入只含二目运算符的算术表达式，利用算符运算规则进行计算并输出运算结果。 3. 测试数据：12.5+34/8-(2-1)*3^2 4. 运算结果为：7.75 二、 需求分析 1. 本程序用来求出字符形式的算术表达式的值，需要将字符转换为数字，并区别运算符，比较运算符优先级。 2. 程序运行后显示提示信息，提示用户输入，用户可以输入小数进行运算。 3. 用户输入完毕后，程序自动输出运算结果。 三、 概要设计 为了实现上述功能，应建立栈，一个操作数栈，一个算符栈，因此需要用栈抽象数据类型。 1. 操作数栈抽象数据类型定义： ADT Stackchar{ 数据对象：D={ai| ai∈IntegerSet，i=1，2，…，n，n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1， ai∈D， i=1，2，…，n} 约定an端为栈顶，ai端为栈底。 GetTop（S，e） 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push（S，e） 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop（S，e） 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素。 }ADT Stackchar ADT Stackfloat{ 数据对象：D={ai| ai∈{+,-,*,/,(,),^,#}，i=1，2，…，n，n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1， ai∈D， i=1，2，…，n} 约定an端为栈顶，ai为栈底。 GetTop（S，e） 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push（S，e） 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop（S，e） 初始条件：栈S已存在且非空。 操作结果：删??S的栈顶元素。3. 主函数 调用关系： 运算函数 计算函数 优先级比较函数 四、 详细设计 1. 元素类型、结点类型和结点指针类型： #define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior[8][8] = { // 运算符优先级表 // + - * / ( ) # ^ /*+*/,,,,,,,, /*-*/,,,,,,,, /***/,,,,,,,, /*/*/,,,,,,,, /*(*/,,,,,=, ,, /*)*/,,,, ,,,, /*#*/,,,,, ,=,, /*^*/,,,,,,, }; typedef struct StackChar{ char c; StackChar* next; }SC; Typedef struct StackFloat{float c; StackFloat* next; }SF;  4. 主函数的伪码： void main() { char s[128]; puts(Please input:); gets(s); puts(the result is:); printf(%s\b=%g\n,s,EvaluateExpression(s)); system(pause); return 0; }  五、 调试分析 1. 采用链栈的存储方式，便于进行算符优先级的判断和运算。 2. 算法的时空分析： （1） 由于采用带头结点的链栈，采用动态申请内存方式，空间复杂度比较合理。 （2） 由于输入的字符串一般较短，因此讨论时间复杂度意义不大。 六、 使用说明 程序运行后用户根据提示输入字符形式的算术表达式，输入‘#’或回车键后自动计算出结果并显示。 七、 调试结果 Please input: 12.5+34/8-(2-1)*3^2 the result is: 1