中缀算术表达式求值.doc
文本预览下载声明
目 录
一、 设计内容 1
二、 概要设计 1
1.程序的功能。 1
2.输入输出的要求 1
3.程序构成： 1
4. 数据结构及存储方式 2
三、 详细设计 2
1.采用C语言定义相关的数据类型。 2
2.写出各模块的类C码算法。 3
3.各函数的调用关系图。 8
四、 调试分析以及设计体会 9
1.测试数据： 9
2.程序调试中遇到的问题以及解决问题的方法： 9
3.课程设计过程经验教训、心得体会 10
五、 附录 11
六、 评分表 16
设计内容
课题一：中缀算术表达式求值
我们很早就学习如何书写及计算表达式，诸如：8+5*（7-3）之类的表达式，先算括号内的7减去3，得到4，然后再算5乘以4，得到20，再计算8加上20，得到28，因此该表达式的值为28。这是人们熟悉的运算规则额：有括号先算括号内；无括号时，先做乘除法，后做加减法；对于相同级别的运算按从左到右的次序运算。而计算机是如何实现表达式的计算的呢？应用栈的相关知识，编程序实现之。
设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算术符优先关系，实现对算数四则混合运算表达式的求值，并演示在求值过程中运算符栈、操作符栈、输入字符和主要操作的变化过程。
1.程序的功能
该程序能够对任意的四则运算表达式进行中缀表达式向后缀表达式的转换，并得出其计算结果。
2.输入输出的要求
输入输出均是阿拉伯数字和四则运算操作符以及括号运算符，按照程序所给提示进行标准输入输出即可。
3.程序构成
1)StackInit函数，主要用来实现函数的初始化；
2)StackPush函数，主要用来执行入栈操作，为实现中缀转后缀提供可能；
3)StackPop函数，主要用来执行出栈操作，为转换函数所应用；
4)StackTop函数，主要用来执行取栈顶元素操作，为转换表达式做准备；
5)Compare函数，主要用来实现比较运算符的优先级别的比较，为后面的函数转换做准备；
6）Transfer函数，主要用来实现中缀表达式转换成为后缀表达式，为后面的计算提供条件；
7)Calculate函数，主要用来综合前面函数的结果，从而计算出表达式的值；
8）main函数，主要用来实现数据的输入输出以及测试；
各个函数之间均有其内在的数据以及结构上的联系，在main函数里面调用了Transfer函数和Calculate函数，而在Transfer函数内部，有调用了之前的StackInit函数、StackPush函数、StackTop函数以及Compare函数和StackPop函数。
4. 数据结构及存储方式
该课题程序主要涉及了栈的数据结构，其存储的字符型和整型。如：
typedef struct stack
{
Elemtype data;
struct stack * next;
}Sqstack;
1.采用C语言定义相关的数据类型
定义栈：
typedef struct stack
{
Elemtype data;
struct stack * next;
}Sqstack;
2.写出各模块的类C码算法
1）初始化函数
void StackInit(Sqstack **head)
{
if((*head=(Sqstack *)malloc(sizeof(Sqstack)))==NULL) exit(1);
(*head)-next=NULL;
}
2）入栈
int StackPush(Sqstack *head,Elemtype x)
{
Sqstack *p;
if ((p=(Sqstack *)malloc(sizeof(Sqstack)))==NULL)
{
printf(内存空间不足无法插入);
return 0;
}
p-data=x;
p-next=head-next;
head-next=p;
return 1;
}
3）出栈
int StackPop(Sqstack *head,Elemtype *d)
{
Sqstack *p =head-next;
if (p==NULL)
{
printf(堆栈已空出错!);
return 0;
}
head-next=p-next;
*d=p-
显示全部