《数据结构
实验报告
化学实验报告单总流体力学实验报告观察种子结构实验报告观察种子结构实验报告单观察种子的结构实验报告单
》
◎实验题目: 栈的应用。
◎实验目的:熟悉掌握对栈的应用和基本操作。
◎实验内容:用算符优先法对算术表达式求值。
一、需求分析
通过程序设计实现算符优先法:
1 以字符串的形式输入整形数据和运算符号;
2、输出算术表达式的结果;
3、实现简单的一位整型数据的算术运算;
4、测试数据:算术表达式,其中的整型数据均只有一位。
二 概要设计
1.基本操作
void InitStack(SqStack *s)
操作结果:栈的初始化。
int GetTop(SqStack *s)
初始条件:栈已存在且不空;
操作结果:将栈顶元素返回。
void Push(SqStack *s,int e)
初始条件:栈已存在;
操作结果:插入e作为新的栈顶元素。
char Pop1(SqStack *s)
初始条件:运算符栈已存在且不空;
操作结果:栈顶元素出栈。
int Pop2(SqStack *s)
初始条件:运算数栈已存在且不空;
操作结果:栈顶元素出栈。
char precede(char A, char B)
操作结果:比较两个算符的优先级,并将比较结果返回。
int In(char Test)
操作结果:判断字符是否是运算符。
int EvaluateExpression()
操作结果:通过调用一系列的函数,对表达式求值。
main()
操作结果:主要通过调用函数EvaluateExpression得到最终结果。
2.本程序包含两个模块:
(1)构造栈的模块;
(2)主程序模块;
(三) 详细设计
1.声明,栈的结构体和判断运算符优先级的表格(以数组形式表达):
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define overflow 1
#define error 0
char OPSET[7]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'};//运算符种类
unsigned char Prior[7][7] =
{ // 算符间的优先关系
'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=',' ',
'>','>','>','>',' ','>','>',
'<','<','<','<','<',' ','='
};
2.各个函数的详细设计:
void InitStack(SqStack *s)//栈的初始化
{
s->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!s->base) exit(error); //存储分配失败
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}
int GetTop(SqStack *s)//若运算符栈不空则用e返回栈顶元素
{
if(s->top==s->base)
exit (overflow);
return (*(s->top-1));
}
void Push(SqStack *s,int e)//插入e为新的栈顶元素
{
if(s->top-s->base>=s->stacksize)
{
s->base=(int *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(int));
if(!s->base)exit(error);
s->top=s->base+s->stacksize;;
s->stacksize=s->stacksize+STACKINCREMENT;
}
*s->top=e;
s->top++;
}
char Pop1(SqStack *s)//运算符栈顶元素出栈
{
if(s->top==s->base)
return error;
return (*--s->top);
}
int Pop2(SqStack *s)//运算数栈顶元素出栈
{
if(s->top==s->base)
return error;
return (*--s->top);
}
char Precede(char A, char B) //实现两个算符优先级的比较
{
return Prior[FindOpOrd(A,OPSET)][FindOpOrd(B,OPSET)];
}
在Precede函数中再调用FindOpOrd函数,设计如下:
int FindOpOrd(char op,char *TestOp) //在Prior数组中按行或者按列找到算符对应的位置
{
int i;
for(i=0; i< 7; i++)
{
if (op == TestOp[i])
return i;
}
}
int Operate(int a,unsigned char theta, int b) //根据运算符进行二元运算
{
switch(theta)
{
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': if(b!=0)
return a/b;
else
exit(error);
default : return error;
}
}
int In(char Test) //判断字符是否为运算符,如果是运算符返回1,否则返回0
{
if('0'<=Test&&Test<='9')
return 0;
else
return 1;
}
int EvaluateExpression()//算符优先法的实现
{
SqStack OPTR,OPND;
char c,theta;
int a,b,result;
InitStack (&OPTR); //创建运算符栈
Push (&OPTR, '#'); //在运算符栈栈底放上#
InitStack (&OPND); //创建运算数栈
c =getchar();
while (c!= '#'||GetTop(&OPTR)!='#')
{
if (In(c)==0) // 不是运算符则进栈
{
Push(&OPND,c-48);
printf("
运算数%d直接进运算数栈\n",c-48);
c=getchar();
}
else
{
switch (Precede(GetTop(&OPTR), c))
{
case '<': // 栈顶元素优先级低
Push(&OPTR, c);
printf("
运算符%c直接进运算符栈\n",c);
c=getchar();
break;
case '=': // 脱括号并接收下一字符
Pop1(&OPTR);
printf("
输入)后运算符栈进行脱括号操作\n");
c=getchar();
break;
case '>': // 退栈并将运算结果入栈
theta=Pop1(&OPTR);
printf("
运算符%c从运算符栈顶弹出\n",theta);
b=Pop2(&OPND);
printf("
运算数%d从运算数栈顶弹出\n",b);
a=Pop2(&OPND);
printf("
运算数%d从运算数栈顶弹出\n",a);
Push(&OPND, Operate(a, theta, b));
printf("
运算数%d和运算数%d进行%c运算并将结果进运算数栈\n",a,b,theta);
break;
} // switch
}
} // while
return (Pop2(&OPND));
} // EvaluateExpression
函数EvaluateExpression通过调用其它函数实现了算符优先法计算表达式,因此主函数主要通过调用该函数进行运算。
int main()
{
int result;
printf("请输入表达式(以#表示输入结束):\n");
result=EvaluateExpression();
printf("result=%d\n",result);
return 0;
}
3.完整的程序见源文件。
(四) 程序使用说明及测试结果
1.程序使用说明
(1)本程序的运行环境为VC6.0。
(2)进入演示程序后即显示提示信息:
请输入表达式(以#表示输入结束):
例如输入:3+2*(5+8)#
点击回车即可得到结果及运算过程。
(3)运行界面如图所示:
(五)、实验
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
(实验心得)
1.关于函数调用过程中要注意参数的传递,以及函数的返回值问题。特别应注意参数类型和返回值的类型。
2.在设计比较两个运算符优先级函数Precede的过程中花费时间长,最后采用直接将比较表以数组形式保存到代码中,比较时再查找的这种方法。
3.输入的算术表达式是以字符串的形式输入的,在计算过程中最初没注意,从而导致将数字字符所对应的ASC码进行运算导致结果错误,改进方法是将数字字符入栈时直接将其减去48,这样结果正确。
4.在做表达式的计算的时候一定要注意何时入栈何时出栈。如果如栈与出栈的情况判断不清楚就无法得出
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
。
5..关于栈顶元素出栈设计了两个函数char Pop1(SqStack *s)和int Pop2(SqStack *s)分别用于运算符出栈和运算数出栈,因为运算数入栈时减去48,因此我认为要设计两个出栈函数。