表达式求值实验报告

西 南 大 学

数据结构实验报告

学院：

专业：

班级： 姓名： 学号：

实验报告

一、实验题目：表达式求值 二、实验目的和要求： 目的：（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 \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;

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; case '(': switch (b) { 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; } break; case '#': switch (b)