西南大学数据结构实验报告
学院：
专业：
班级：
姓名：
学号：
实验报告
一、实验题目：表达式求值
二、实验目的和要求：
目的：（1）通过该算法的设计思想，熟悉栈的特点和应用方法；
（2）通过对算符优先法对算术表达式求值的算法执行过程的演示，理解在执行相应栈的操作时的变化过程。
（3）通过程序设计，进一步熟悉栈的基本运算函数；
（4）通过自己动手实现算法，加强从伪码算法到C语言程序的实现能力。
要求：（1）使用栈的顺序存储表示方式；
（2）使用算符优先法；
（3）用C语言实现；
（4）从键盘输入一个符合要求的算术表达式，输出正确的结果。
三、实验过程：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK 等
typedef int ElemType;
const int STACK_INIT_SIZE=100;
const int STACKINCREMENT=10;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
}Stack;
Status InitStack(Stack &S)
{//构造一个空栈S
S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base)
exit (ERROR);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(Stack &S, ElemType e)
{//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,
(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) exit (OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(Stack &S, ElemType &e)
{//若栈不空，则删除，用e返回其值，并返回OK；否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status GetTop(Stack &S)
{//若栈不空，用e返回S的栈顶元素，并返回OK；否则返回ERROR
if(S.top==S.base)
return ERROR;
return*(S.top-1);
}
Operate.h:
#include"Stack.h"
Status In(char c)
{//判别c是否为运算符
if (c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')
return OK;
else
return ERROR;
}
Status Operate(int a,char c,int b)
{//二元运算
switch (c)
{
case'+': return a+b; break;
case'-': return a-b; break;
case'*': return a*b; break;
case'/': if(b==0) {printf("（提示：存在除数为零错误）\n");return ERROR;}//除数不能为零
else return a/b; break;
}
}
char Precede(char a,char b)
{//算符间优先关系
switch(a)
{
case'+':
switch (b)
{
case'+': return'>'; break;
case'-': return'>'; break;
case'*': return'<'; break;
case'/': return'<'; break;
case'(': return'<'; break;
case')': return'>'; break;
case'#': return'>'; break;
}break;
case'-':
switch (b)
{
case'+': return'>'; break;
case'-': return'>'; break;
case'*': return'<'; break;
case'/': return'<'; break;
case'(': return'<'; break;
case')': return'>'; break;
case'#': return'>'; break;
}break;
