数据结构与算法课程设计

数据结构与算法

课程设计报告

信息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=数字，则需要考虑两位以上数的情形，编写程序凑数后再发给操作

数，若是一位数可直接发给操作数栈。

1

接收一个表达式 放在Str[ ]中 定义一个操作符栈op，对运算符进行进栈出栈操作 将数字直接存入exp[ ]中，判断多位数，用#分隔开 将表达式转化为后缀形式放入exp[ ]定义一个操作数栈st，对数进行进栈出栈操作 利用#进行凑数并存入操作数栈中，进行运算 进行四则运算求得表达式的值 四． 源程序 #include #define MaxSize 99

void translate(char str[],char exp[]) /*将算术表达式转换成后缀表达*/ {

struct {

char data[MaxSize];

int top; /*top为栈顶*/

}op; /*定义一个含data和top的j结

构体*/

char ch; int i = 0,t = 0; op.top = -1; ch = str[i]; /*将str的每一个数转换成ch*/ i++;

2