数据结构课程设计- 算术表达式求值

课 程 设 计 报 告

课程名称 数据结构课程设计 题 目 算术表达式求值 指导教师

设计起始日期 4.18~4.25

学 院 计算机学院 系 别 计算机科学与工程 学生姓名 班级/学号

成 绩

一、 需求分析

设计一个算术表达式四则运算的程序，要求完成包括加、减、乘、除运算，

包含括号的基本整数表达式的运算。在这里运算数可以1位长度，也可以多位长度。在运算之后输出的正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 （1） 输入：3*（7-2）

（2） 输出：数据栈栈顶元素：3,7,2,7,5,3,15

结果：15

（3） 自选数据

二、 概要设计

1、 使用栈的数据结构表示数据的存储。

2、 设计算法将中缀表达式转换成后缀表达式，用栈的数据结构实现表

达式的运算。

3、 把中缀表达式转换为后缀 表达式算法的基本思路是从头到尾地扫描中缀表达

式中的每个字符，对于不同类型的字符按不情况进行处理。

三、 详细设计

数据结构：字符类型栈

/* 定义字符类型栈*/

typedef struct{ char stackname[20]; char *base; char *top;

} Stack;

算法：将中缀表达式转换为后缀 表达式 void Change(char* s1, char* s2)

// 将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式 {

Stack R; // 定义用于暂存运算符的栈 InitStack(R); // 初始化栈

Push(R,'#'); // 给栈底放入’#’字 符，它具有最低优先级0 int i,j;

i=0; // 用于指示扫描s1串中字符的位置，初值为0 j=0; // 用于指示s2串中待存字符的位置，初值为0

char ch=s1[i]; // ch保存s1串中扫描到的字符，初值为第一个字符 while( ch!='#')

{ // 顺序处理中缀表达式中的每个字符 if(ch==' ')

// 对于空格字符不做任何处理，顺序读取下一个字符 ch=s1[++i]; else if(ch=='(')

{ // 对于左括号，直接进栈 Push(R,ch); ch=s1[++i]; }

else if(ch==')')

{ // 对于右括号，使括号内的仍停留在栈中的运算符依次

// 出栈并写入到s2中 while(Peek(R)!='(') s2[j++]=Pop(R);

Pop(R); // 删除栈顶的左括号 ch=s1[++i]; }

else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')

{ // 对于四则运算符，使暂存在栈中的不低于ch优先级 // 的运算符依次出栈并写入到s2中 char w=Peek(R);

while(Precedence(w)>=Precedence(ch))

{ // Precedence(w)函数返回运算符形参的优先级 s2[j++]=w;

Pop(R); w=Peek(R); } }

四、 调试分析

调试：

在设计过程中出现程序不能运行，发现不能找到结束标识符，因此在设计的时候需要人为动态添加结束标识符‘#’，顺利运行 算法时间和空间分析：

算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个

数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据组成，则 此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个 数与运算符（假定把’#’也看作为一个特殊运算符，即结束运算符）的个数相等，所以此算法的空间复杂度也同样为O(n)。

五、 使用说明和测试结果

1、使用说明：用户按照屏幕所显示的提示来输入表达式

2、测试结果：