数据结构实验报告
报告名称 栈的应用
专 业 网络工程
班 级 1001
学 号苏州科技学院学报 ************
姓 名 张剑
指导教师 陈淑红 李珍辉 黄哲
2012 年 5 月 4日
一、实验目的：
二、实验内容与基本要求：
实验内容：
基本要求：
以字符序列的形式从终端输入语法正确的、不含变量的算术表达式，利用算符优先关系，实现对算术四则混合运算表达式求值。
三、实现提示：
1．利用栈辅助分析算符优先关系；
2．在读入表达式字符序列的同时，完成运算符和操作数的识别处理，以及相应的运算；
3．在识别出操作数的同时，要将其字符序列形式转换成相应的浮点数形式。
四．概要设计：
1.顺序栈的定义：
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
2.栈的基本操作：
InitStack(&S)
DestoryStack（&S）
初始条件：栈S存在。、
操作结果：栈S被销毁。
ClearStack(&S)
初始条件：栈S存在。、
操作结果：将S清为空栈。
StackEmpty（&S）
初始条件：栈S存在。、
操作结果：若S为空栈，则返回TUUE，否则FALSE.
StackLength(&S)
初始条件：栈S存在。、
操作结果：返回S的 元素个数，即栈的长度。
GetTop（S,&e）
初始条件：栈S存在且非空。
操作结果：用e 返回S的栈顶元素。
Push（&S，e）
初始条件：栈S存在。、
操作结果：插入元素e为新的栈顶元素。
pop (&s,&e)
初始条件： 栈S存在且非空。
操作结果： 删除S的栈顶元素，并用e返回其值。
StackTravse(S,vist())
初始条件:栈S存在且非空.
操作结果:从栈底到栈顶依次对S的每个元素调用函数vist()，一旦vist()失败，择操作结束。
3.表达式求职操作：
OpperandType EvauluateExpresseion(){
//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算式//栈OP为运算符集合。
TnitStack（OPTR）；Push（OPTR，”#”）;
intStack (OPND); c=getchar();
while(c!’#’||Gettop(OPTR)!=’#’){
if(!In(c,op))｛Push(OPND,c);c=getchar();
｝//不是运算符则进栈。
else
switch(Precede(GetTop(OPTR),c){
case’<’: //栈顶元素优先权低。
Push(OPTR,c);c=getchar();四棱锥
break;
case’=’: //脱括号并接收下一字符
Pop(OPTR,x): c=getchar();
笛卡儿坐标
break;
case ‘>’: //退栈并将运算结果入栈。
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a)
Push(OPND,Operate(a,theta,b));
Break;
}//switch
}//while
return GetTop(OPND);
}// EvauluateExpresseion
五、详细设计：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_MAX_SIZE 50
typedef struct
{
char symb; /*字符标记*/
int grade; /*运算级别 */
}elem_t;
typedef struct
{
elem_t data[STACK_MAX_SIZE];
int top;
}f_stack; /*符号栈*/
enum
{
S_DIGIT,
S_OPERATOR,
S_BRACKET,
};
f_stack *StackInit()
{www.bf99
f_stack *s;
s = (f_stack *)malloc(sizeof(f_stack));
ungelivable if (s==NULL)
{
printf("could not malloc memory for s!");
exit(1);
}
永不磨面的 memset(&s->data,0,sizeof(elem_t)*STACK_MAX_SIZE);
s->top = 0;
return s;
}
void StackDelete(f_stack *s)
{
free(s);
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议