数据结构课程设计(表达式计算).doc

福建农林大学计算机与信息学院 计算机类 课程设计报告 课程名称： 算法与数据结构 课程设计题目： 表达式计算 姓 名： 系： 数学系 专 业： 数学与应用数学 年 级： 学 号： 指导教师： 宁正元 职 称： 教授 20**年 12月 25 日 目 录 1、课程设计的目的…………………………………………………………… 1 2、课程设计的要求…………………………………………………………… 13、课程设计的内容?………………………………………………………… 1 3.1主函数中一些重要变量的作用………………………………………………… 1 3.2重要步骤算法思路分析 ………………………………………………………… 1 3.3源程序代码…………………………………………………………………… 3 3.4程序调试与测试结果?…………………………………………………………… 12 3.5结果分析……………………………………………………………………… 16 4、总结 ?……………………………………………………………………… 165、参考文献 ?………………………………………………………………… 16 表达式计算 1、课程设计的目的 1.掌握C语言的相关知识； 2.熟悉掌握结构体和共用体的定义和使用； 3.熟悉掌握栈和相关操作函数的定义和使用； 4.熟悉掌握数组和相关操作的定义和使用 2、课程设计的要求 1.对从键盘输入一个表达式，先检查合法性：如不合法，则给出错误信息，再返回；如合法，则对其进行整理，利用栈和数组进行相关数据保存，再进行运算，最后输出计算结果。 2.计算范围：包括一般的算术运算（加、减、乘、除、括号）和常用的函数运算（三角函数、自然指数函数、自然对数函数、绝对值函数、平方根函数）。 3.其他功能可自行添加。 3、课程设计的内容 3.1主函数中一些重要变量的作用 double sz[MAXSIZE];用于存放数值的数组 char fh[MAXSIZE]; 用于存放运算符的数组 char temp[MAXSIZE];用于存放输入的表达式的数组 float sum; 用于记录当前读到的数中以读到的数值 int i_b,i_t,ld,lsz; i_b后面备用; i_t记录读到哪一个字符; ld记录小数的位数; lsz记录sz的有效长度; shed KH,HS; KH用于放括号的栈； HS用于放函数的栈 3.2重要步骤算法思路分析(均以合法表达式为例) 先用数组temp对输入的表达式进行储存，再对其进行一位一位地读取和处理： 1.对数值和运算符的处理： 1)对运算符的处理比较简单，当遇到运算符时，直接存入数组fh即可； 2)对数值的处理，由于不知道数是几位，所以要用两个变量sum、ld，(sum记录已读取得数字，ld记录小数位数)，具体操作请见下面流程图： 2.对括号运算和函数运算的处理： 对括号运算和函数运算的处理比较麻烦，特别市它们的嵌套使用，如式子： 1+(2-(3+4)*5)*6 当读到2前的‘(’时，由于括号运算的优先级高于加、减、乘、除，所以应对其先进行保存，当读到3前的‘(’时，同样也要先进行保存。当读到4后的‘)’时，应把3前的‘(’取出来，与之配对，再运算之间的式子，同样当读到5后的‘)’时，应把2前的‘(’取出来，配对，再运算。所以对于‘(’的保存与读取具有先进后出的特点，栈刚好也有这个特点，因此用栈可以对其进行储存； 同理,对函数的处理也是这样的,如式子： sin(abs(-1)) 应先保存sin函数名，再保存abs函数名；而进行计算时，应先计算abs函数再计算sin函数，也有先进后出的特点。 再考虑这些栈的元素的特点： 对于保存函数名的栈，它的元素必要有两个分量：一个保存函数名，可以用char类型，另一个分量要记录该函数在式中的位置，可以用int类型。 对于保存扣号的栈，因为考虑到有2种括号：一种是一般算式中的括号，如式子2*(3+4)中的括号；另一种是函数中把参数与一般数值区分开的括号，如式子sin(-1)中的括号。又考虑到要保存的都是’(’，所以该栈也只要2个分量，一个是该括号的种类，可以用int类型的0和1表示（0表示一般算式中的括号，1表示函数参数前的括号），另一个分量是保存该括号在式中的位置。 又考虑到两种栈统一性，我们先定义一个共用体： union sig //sign1记录括号是属于函数的还是运算的，sign2记录是什么函数 { int sign1; char sign2; }; 在定义栈元素的结构体： typedef struct node { union sig sign; int jilu; }n