实验一:栈的应用

中南大学

数据结构实验报告

学生姓名学号指导老师

专业班级实验一：栈的应用

一、实验目的

掌握栈的基本操作，比如，建立栈，出栈，入栈，取出栈顶元素等一些列操作。

二、实验内容

使用栈实现算术表达式求值的算符优先算法。

三、问题描述

在实际应用中，一个算术式由数字、运算符、括号组成，而因为运算符和括号的优先等级不同从而使算术式不能从左至右按顺序进行计算。利用栈和运算符括号之间的优先等级关系可以实现依次输入算术式得出正确结果这一过程。

四、具体实现方法

采用InitStack_OPND（），Gettop_OPND()，Push_OPND（），Pop_OPND（），Operate （），In()，ReturnOpOrd （），Precede （），EvluateExpression （）等函数实现了建立栈，取出栈顶元素，入栈，出栈，运算符优先级的比较等操作。

算符间的优先关系如下：

五、

实验结果

六、源代码

#include"stdio.h"

#include"stdlib.h"

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT 10

#defineOPSIZE 7

#defineOK 1

#defineOVERFLOW 0

#defineERROR 0

unsigned char Prior[7][7]={//算符间的优先关系

'>','>','','>',

'>','>','','>',

'>','>','>','>','','>',

'>','>','>','>','','>',

'

'>','>','>','>','','>','>',

'

};

char OP[OPSIZE]={'+','-','*','/','(',')','#'};

typedef struct

{

float *base;

float *top;

int stacksize;

}Sq_OPND;

typedef struct

{

char *base;

char *top;

int stacksize;

}Sq_OPTR;

//构造一个空栈

int InitStack_OPND(Sq_OPND&s)

{

s.base=(float*)malloc(STACK_INIT_SIZE*sizeof(float));

if(!s.base)exit(OVERFLOW);

s.top=s.base;

s.stacksize=STACK_INIT_SIZE;

return OK;

}

int InitStack_OPTR(Sq_OPTR&s)

{

s.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));

if(!s.base)exit(OVERFLOW);

s.top=s.base;

s.stacksize=STACK_INIT_SIZE;

return OK;

}

//若栈不空, 则用e 返回s 的栈顶元素

float Gettop_OPND(Sq_OPNDs)

{

float e;

if(s.top==s.base)exit(ERROR);

e=*(s.top-1);

return e;

}

char Gettop_OPTR(Sq_OPTRs)

{

char e;

if(s.top==s.base)exit(ERROR);

e=*(s.top-1);

return e;

}

//插入元素e 为新的栈顶元素

int Push_OPND(Sq_OPND&s,floate)

{

if(s.top-s.base>=s.stacksize)

{//栈满, 追加存储空间

s.base=(float

*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(float));

if(!s.base)exit(OVERFLOW);//存储分配失败

s.top=s.base+s.stacksize;

s.stacksize+=STACKINCREMENT;

}

*s.top++=e;

return OK;

}

int Push_OPTR(Sq_OPTR&s,chare)

{

if(s.top-s.base>=s.stacksize)

{

s.base=(char

*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));

if(!s.base)exit(OVERFLOW);

s.top=s.base+s.stacksize;

s.stacksize+=STACKINCREMENT;

}

*s.top++=e;

return OK;

}

/*若栈不空, 则删除s 的栈顶元素, 用e 返回其值, 并返回OK, 否则返回ERROR */

int Pop_OPND(Sq_OPND&s,float&e)

{

if(s.top==s.base)return ERROR;

else {e=*--s.top;return OK;}

}

int Pop_OPTR(Sq_OPTR&s,char&e)

{

if(s.top==s.base)return ERROR;

else {e=*--s.top;return OK; }

}

//运算

float Operate(floata,char theta,float b)

{

float temp;

switch(theta)

{

case '+':temp=a+b;break;

case '-':temp=a-b;break;

case '*':temp=a*b;break;

case '/':

if(b==0){printf("ERROR:分母为零\n");exit(ERROR);}

temp=a/b;break;

}

return temp;

}

//判断是否为运算符

int In(charc,char *OP){

bool Find=false;

for(inti=0;i

if(c==OP[i])

Find=true;

}

return Find;

}

//运算符优先关系比较

int ReturnOpOrd(charop,char*TestOp) {

int i;

for(i=0;i

if (op==TestOp[i])return i;

}

return 0;

}

char Precede(chartheta,char c) {

return Prior[ReturnOpOrd(theta,OP)][ReturnOpOrd(c,OP)];

}

float EvluateExpression()

//算术表达式求值的算符优先算法. 设OPTR 和OPND 分别为运算栈和运算数栈

{

Sq_OPTROPTR;

Sq_OPNDOPND;

char c,x,theta;

float a,b, tag=0,n=0;

InitStack_OPTR(OPTR);

Push_OPTR(OPTR,'#');

InitStack_OPND(OPND);

c=getchar();

while(c!='#'||Gettop_OPTR(OPTR)!='#')

{

if(!In(c,OP))

{

tag=1;//运算数标志符，输入是运算数时为1，输入是运算符

时为0

n=10*n+(c-48);

c=getchar();

}//不是运算符则进栈

else

{

if(n!=0){Push_OPND(OPND,n);tag=0;n=0;}//

else if(tag!=0)Push_OPND(OPND,n);

switch(Precede(Gettop_OPTR(OPTR),c))

{

case 0:

printf("ERROE:表达式输入错误!\n");exit(ERROR);

case '

Push_OPTR(OPTR,c);c=getchar();break;

case '='://脱括号并接收下一字符

Pop_OPTR(OPTR,x);c=getchar();break;

case '>'://退栈并将运算结果入栈

Pop_OPTR(OPTR,theta);

Pop_OPND(OPND,b);

Pop_OPND(OPND,a);

Push_OPND(OPND,Operate(a,theta,b));

}//switch

}//else

}//while

return Gettop_OPND(OPND);

}//EvluateExpression

int main()

{

printf("输入一个表达式，并以#结束:\n");printf("result=%.2f\n",EvluateExpression());return 1;

}