数据结构与算法课程设计.doc

数据结构与算法 课程设计报告 信息102班历红影2010052210目录一问题描述-1二数据结构-1三算法设计思想及流程图-1四源程序-2五测试情况-6参考文献-6一 问题描述计算表达式的值(*)（1）问题描述：对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。（2）基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，计算后缀表达式的值。（3）测试数据：任意选取一个符合题目要求的表达式。二 数据结构本程序主要采用栈的思想，运用3个函数translate、cal value和value来实现程序要求 。它们的作用如下：（1）translate函数：将表达式转化为后缀表达式，设置一个暂存运算符栈op，再运用case语句判断操作符的优先级，而数字直接发送给后缀表达式。（2）cal value函数：计算后缀表达式的值，设置一个操作数栈st，再运用case语句进行+ - * / 四则运算，并提取操作数。（3）main函数：调用translate函数和cal value函数三 算法设计思想及流程图 本程序涉及到转换和计算两个算法。实现转换时使用的思想是设置一个运算符栈，并按以下规则进行：（1） 若ch=（，则直接压入栈底（2） 若ch=+或-，需要解决有括号时加减的优先级问题（3） 若ch=*或/，需判断优先级，若ch与op中栈顶的*或/同级则直接发给后缀表达式，否则插入op。（4） 若ch=，则忽略空格，排除误操作。（5） 若ch=），并且op栈顶是（，op出栈，从而消去了两个括号；否则）被解释为级别低于其他运算符，要按上面规则进行，直到碰到（，op出栈。（6） 若ch=数字，则直接发给后缀表达式，并且每一个数字以#结尾。实现计算时使用的思想是设置一个操作数栈，并按以下规则进行：（1） 若ch=+或-，则将栈st中相应两个数相加或相减，并将结果储存在前一个数中，然后退栈。（2） 若ch=*，则将栈st中相应两个数相乘，并将结果储存在前一个数中，然后退栈。（3） 若ch=/,先判断st栈顶元素是否为0，若不为0则将相应两个数相除，并将结果储存在前一个数中，然后退栈。否则，输出“除0是错误的”。（4） 若ch=数字，则需要考虑两位以上数的情形，编写程序凑数后再发给操作数，若是一位数可直接发给操作数栈。接收一个表达式放在Str 中定义一个操作符栈op，对运算符进行进栈出栈操作将数字直接存入exp 中，判断多位数，用#分隔开将表达式转化为后缀形式放入exp 中定义一个操作数栈st，对数进行进栈出栈操作利用#进行凑数并存入操作数栈中，进行运算进行四则运算求得表达式的值四 源程序#include#define MaxSize 99void translate(char str,char exp) /*将算术表达式转换成后缀表达*/ struct char dataMaxSize; int top; /*top为栈顶*/ op; /*定义一个含data和top的j结构体*/ char ch; int i = 0,t = 0; op.top = -1; ch = stri; /*将str的每一个数转换成ch*/ i+; while(ch != 0) /*ch对应不同的符号的时候对应的转换情况*/ switch(ch) case (: /*当是（的时候，将此括号存入栈op*/ op.top+;op.dataop.top=ch; break; case ): while(op.dataop.top != () /*括号内的转换优先级最高，故先提取表达式*/ expt=op.dataop.top; op.top-; t+; op.top-; break; case +: case -: while(op.top != -1&op.dataop.top != () expt = op.dataop.top; op.top-; t+; op.top+; /*恢复可插入位置*/ op.dataop.top = ch; break; case *: case /: while(op.top = /|op.top = *) /*优先级*/ expt = op.dataop.top; op.top-; t+; op.top+; op.dataop.top = ch; break; case : /*忽略空格，排除误操作*/ break; default: while(ch = 0&ch = 0&ch = 9) /*从后缀表达式中获取操作数，#作用在此体现*/ d = 10*d+ch-0; ch = expt; t+; st.top+; st.datast.top = d; ch = expt; t+; return st.datast.top;void main() /*可以提到前面去*/ char strMaxSize,expMaxSize; /*str为算术表达式,exps为后缀表达式*/ printf(=表达式求值程序=n请输入一个求值表达式n); printf(表达式:); gets(str); /*输入一个算术表达式*/ printf(原表达式是:%sn,str); translate(str,exp); /*将算术表达式转换成后追表达式*/ printf(后缀表达式：%sn,exp); printf(经过计算%s=%