文档视界 最新最全的文档下载
当前位置:文档视界 › 数据结构实验报告 表达式求值

数据结构实验报告 表达式求值

(一> 需求分析

1、输入地形式和输入值地范围:

根据题目要求与提示,先选择你要使用地表达式形式<中缀用1,后缀用0),在输入一个中缀表达式,输入数地范围为int型,此时,程序将计算出表达式地结果.

2、输出地形式:当按照程序要求选择了1或0之后,再输入表达式;如果选择地是1,则程序将自动运算出表达式结果;如果之前选择地是0,则程序将现将中缀表达式转化为后缀表达式并计算出结果.

3、程序所能达到地功能:

本程序能计算出含+、-、*、/、<、)等运算符地简单运算.

4、测试数据:

输入一个表达式,如果你之前选择地是“中缀表达式”,那么输入5*(4-2>#,那么输出结果是10;如果之前选择地是“后缀表达式”,那么输入5*<4-2)#,那么他将先转换成后缀表达式5 4 2 - * #,再输出结果10.

如果输入表达式没有结束标示符#,如5*<4-2),那将不会输出任何结果,或出现错误结果.

(二> 概要设计

为了实现上述操作,应以栈为存储结构.

1.基本操作:

<1). int GetTop(SqStack *s>

初始条件:栈存在;

操作结果:若栈为空,则返回s地栈顶元素;否则返回ERROR.

<2).void Push(SqStack *s,int e>

初始条件:栈存在;

操作结果:插入e为新地栈顶元素.

<3).int Pop(SqStack *s>

初始条件:栈存在;

操作结果:若栈不空,则删除之,并返回其值;否则返回REEOR.

<4).void InitStack(SqStack *s>

初始条件:栈存在;

操作结果:置栈为空.

<5).int Empty(SqStack *s>

初始条件:栈存在;

操作结果:判定s是否为空栈.

<6).int Operate(int a,char theta, int b>

初始条件:操作数a和b存在,且theta是+、-、*、/四则运算;

操作结果:返回a与b间theta运算地结果.

<7).int In(char s,char* TestOp>

初始条件:s为待判断字符,TestOp为已知地算符集合;

操作结果:s为算符集合中地元素则返回1,否则返回0.

<8).int ReturnOpOrd(char op,char* TestOp>

初始条件:op为待确定运算符,TestOp为已知地算符集合;

操作结果:确定运算符类型.

<9).char precede(char a, char b>

初始条件:a、b存在;

操作结果:返回算符a和b地优先权高低.

<10).void PrintOpnd(SqStack *s>

初始条件:栈存在;

操作结果:输出运算数栈.

<11).void PrintOptr(SqStack *s>

初始条件:栈存在;

操作结果:输出运算符栈.

<12).void Store(char *s,char ch>

初始条件:字符数组 s存在,字符ch已知;

操作结果:将ch存入数组s.

<13).void Change(char *s1,char *s2>

初始条件。重罪表达式s1已知;

操作结果:将中缀表达式s1转为后缀表达式s2.

2.本程序包含二个模块:

<1)主程序模块;

<2)中缀表达式求值模块以及中缀表达式转换为后缀表达式并求值模块<3)模块调用图:

主程序模块

中缀表达式求值模块中缀表达式转换为后缀表达式并求值模块

(三> 详细设计

1.存储类型,元素类型,结点类型:

typedef struct{ //定义栈

int data[SIZE]。

int top。

int base。

}SqStack。

char OPSET[7]={'+' , '-' , '*' , '/' ,'(' , '>' , '#'}。

//定义OPSET字符数组为算符集合

char Prior[7][7] = {

// 算符间地优先关系

'>','>','<','<','<','>','>',

'>','>','<','<','<','>','>',

'>','>','>','>','<','>','>',

'>','>','>','>','<','>','>',

'<','<','<','<','<','=',' ',

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

'<','<','<','<','<',' ','='

}。

2.每个模块地分析:

<1)主程序模块:

int main(>{

char s=0,c。

while(1>{

printf("请输入‘1’或‘0’<1代表中缀表达式,0代表后缀表达式)\n">。

c=getchar(>。

fflush(stdin>。

if(c=='1'>{//中缀表达式运算结果

printf("%d\n",EvaluateExpression_1(>>。

}

else{//后缀表达式运算结果

printf("%d\n",EvaluateExpression_2(>>。

}

do{

scanf("%c",&s>。

if(s=='q'||s=='Q'>

exit(0>。

}

while(s!='\n'>。

system("cls">。

}

return 0。

}

<2)int EvaluateExpression_1(>{

//中缀求值

SqStack OPND,OPTR。

char ch,theta,exp[100]={0}。

int i=0,s=0,a=0,b=0,step=0。

InitStack(&OPND>。

InitStack(&OPTR>。

Push(&OPTR,'#'>。

gets(exp>。

ch=exp[0]。

while(ch!='#'||GetTop(&OPTR>!='#'>{

if(!In(ch,OPSET>>{//不是运算符则进栈

if(In(exp[i+1],OPSET>>{//未出现连续数字

Push(&OPND,ch-48>。

ch=exp[++i]。

}//if

else//出现连续数字

{

s=exp[i++]-48。

while(exp[i]>='0'&&exp[i]<='9'>{

s=s*10+exp[i++]-48。

}

Push(&OPND,s>。

s=0。

ch=exp[i]。

}

}

else

switch(precede(GetTop(&OPTR>,ch>>{

case '<'://栈顶元素优先权低

Push(&OPTR,ch>。

ch=exp[++i]。

break。

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

Pop(&OPTR>。

ch=exp[++i]。

break。

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

theta=Pop(&OPTR>。

b=Pop(&OPND>。

a=Pop(&OPND>。

Push(&OPND,Operate(a,theta,b>>。

break。

}//switch

}//while

return GetTop(&OPND>。

}//EvaluateExpression_1

int EvaluateExpression_2(>{//后缀求值

SqStack OPND。

char ch,theta,receive[100]={0},exp[100]={0}。

int i=0,s=0,a=0,b=0,step=0。

InitStack(&OPND>。

printf("请输入一个中缀表达式:\n">。

gets(receive>。//输入中缀表达式

Change(receive,exp>。

printf("相应地后缀表达式为:\n">。

puts(exp>。//输出对应地后缀表达式

ch=exp[0]。

while(ch!='#'>{

if(!In(ch,OPSET>>{//不是运算符则压入栈中

if(exp[i+1]==' '>{//未出现连续数字

Push(&OPND,ch-48>。

i+=2。

ch=exp[i]。

}//if

else//出现连续数字

{

s=exp[i++]-48。

while(exp[i]>='0'&&exp[i]<='9'>{

s=s*10+exp[i++]-48。

}//while

Push(&OPND,s>。

s=0。

ch=exp[++i]。

}//else

}//if

else{

theta=ch。

b=Pop(&OPND>。

a=Pop(&OPND>。

Push(&OPND,Operate(a,theta,b>>。

i+=2。

ch=exp[i]。

}

}

return GetTop(&OPND>。

}//EvaluateExpression_2<

3)函数调用关系图

3.完整地程序:

#include"stdio.h"

#include"stdlib.h"

#define SIZE 80

#define OK 1

#define ERROR 0

typedef struct{ //定义栈

int data[SIZE]。

int top。

int base。

}SqStack。

char OPSET[7]={'+' , '-' , '*' , '/' ,'(' , '>' , '#'}。

//定义OPSET字符数组为算符集合

char Prior[7][7] = {

// 算符间地优先关系

'>','>','<','<','<','>','>',

'>','>','<','<','<','>','>',

'>','>','>','>','<','>','>',

'>','>','>','>','<','>','>',

'<','<','<','<','<','=',' ',

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

'<','<','<','<','<',' ','='

}。

int GetTop(SqStack *s>{

//若栈为空,则返回s地栈顶元素;否则返回ERROR

if(s->top==s->base>

return ERROR。

return (s->data[s->top-1]>。

}

void Push(SqStack *s,int e>{

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

s->data[s->top]=e。

s->top++。

}

int Pop(SqStack *s>{

//若栈不空,则删除之,并返回其值;否则返回REEOR

int e。

if(s->base==s->top>

return ERROR。

else{

e=s->data[s->top-1]。

s->top--。

}

return e。

}

void InitStack(SqStack *s>{

//置栈S为空

s->top=0。

s->base=0。

}

int Empty(SqStack *s>{

//判定s是否为空栈

if(s->base==s->top>

return 1。

else

return 0。

}

int Operate(int a,char theta, int b> {

//返回a与b间theta运算地结果

switch(theta> {

case '+': return a+b。break。

case '-': return a-b。break。

case '*': return a*b。break。

case '/': return a/b。break。

default : return 0。

}

}

int In(char s,char* TestOp> {

//s为待判断字符,TestOp为已知地算符集合

int Find=0。

for (int i=0。 i<7。 i++> {

if (s == TestOp[i]> Find= 1。

}

return Find。

}

int ReturnOpOrd(char op,char* TestOp> {

//确定运算符类型,op为待确定运算符,TestOp为已知地算符集合 int i。

for(i=0。 i<7。 i++> {

if (op == TestOp[i]> return i。

}

return 0。

}

char precede(char a, char b> {

//返回算符a和b地优先权高低

return Prior[ReturnOpOrd(a,OPSET>][ReturnOpOrd(b,OPSET>]。

}

void PrintOpnd(SqStack *s>{

//输出运算数栈

int i=s->base。

printf("Stack OPND:">。

if(!Empty(s>>{

for(。i<(s->top>。i++>

printf(" %d ",s->data[i]>。

}

else

printf(" ">。

printf("\n">。

}

void PrintOptr(SqStack *s>{

//输出运算符栈

int i=s->base。

printf("Stack OPTR:">。

for(。i<(s->top>。i++>

printf(" %c ",s->data[i]>。

printf("\n">。

}

void Store(char *s,char ch>{

//将ch存入数组s

char *p=s。

while(*p>{

p++。

}

*p++=ch。

}

int EvaluateExpression_1(>{

//中缀求值

SqStack OPND,OPTR。

char ch,theta,exp[100]={0}。

int i=0,s=0,a=0,b=0,step=0。

InitStack(&OPND>。

InitStack(&OPTR>。

Push(&OPTR,'#'>。

gets(exp>。

ch=exp[0]。

while(ch!='#'||GetTop(&OPTR>!='#'>{

if(!In(ch,OPSET>>{//不是运算符则进栈

if(In(exp[i+1],OPSET>>{//未出现连续数字

Push(&OPND,ch-48>。

ch=exp[++i]。

}//if

else//出现连续数字

{

s=exp[i++]-48。

while(exp[i]>='0'&&exp[i]<='9'>{

s=s*10+exp[i++]-48。

}

Push(&OPND,s>。

s=0。

ch=exp[i]。

}

}

else

switch(precede(GetTop(&OPTR>,ch>>{

case '<'://栈顶元素优先权低

Push(&OPTR,ch>。

ch=exp[++i]。

break。

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

Pop(&OPTR>。

ch=exp[++i]。

break。

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

theta=Pop(&OPTR>。

b=Pop(&OPND>。

a=Pop(&OPND>。

Push(&OPND,Operate(a,theta,b>>。

break。

}//switch

}//while

return GetTop(&OPND>。

}//EvaluateExpression_1

void Change(char *s1,char *s2>{

//将中缀表达式转为后缀表达式

SqStack OPTR。

char ch。

int i=0,sum=0。

InitStack(&OPTR>。

Push(&OPTR,'#'>。

ch=s1[0]。

while(ch!='#'||GetTop(&OPTR>!='#'>{

if(!In(ch,OPSET>>{//不是运算符则进栈

if(In(s1[i+1],OPSET>>{//未出现连续数字

Store(s2,ch>。

Store(s2,' '>。//存入一个空格

ch=s1[++i]。

}//if

else//出现连续数字

{

while(s1[i]>='0'&&s1[i]<='9'>{

Store(s2,s1[i]>。

i++。

}//while

Store(s2,' '>。//存入一个空格

ch=s1[i]。

}//else

}//if

else

switch(precede(GetTop(&OPTR>,ch>>{

case '<'://栈顶元素优先权低

Push(&OPTR,ch>。

ch=s1[++i]。

break。

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

Pop(&OPTR>。

ch=s1[++i]。

break。

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

Store(s2,Pop(&OPTR>>。

Store(s2,' '>。//补入一个空格作为间隔

break。

}//switch

}//while

Store(s2,ch>。

}//Change

int EvaluateExpression_2(>{//后缀求值

SqStack OPND。

char ch,theta,receive[100]={0},exp[100]={0}。

int i=0,s=0,a=0,b=0,step=0。

InitStack(&OPND>。

printf("请输入一个中缀表达式:\n">。

gets(receive>。//输入中缀表达式

Change(receive,exp>。

printf("相应地后缀表达式为:\n">。

puts(exp>。//输出对应地后缀表达式

ch=exp[0]。

while(ch!='#'>{

if(!In(ch,OPSET>>{//不是运算符则压入栈中

if(exp[i+1]==' '>{//未出现连续数字

Push(&OPND,ch-48>。

i+=2。

ch=exp[i]。

}//if

else//出现连续数字

{

s=exp[i++]-48。

while(exp[i]>='0'&&exp[i]<='9'>{

s=s*10+exp[i++]-48。

}//while

Push(&OPND,s>。

s=0。

ch=exp[++i]。

}//else

}//if

else{

theta=ch。

b=Pop(&OPND>。

a=Pop(&OPND>。

Push(&OPND,Operate(a,theta,b>>。

i+=2。

ch=exp[i]。

}

}

return GetTop(&OPND>。

}//EvaluateExpression_2

int main(>{

char s=0,c。

while(1>{

printf("请输入‘1’或‘0’<1代表中缀表达式,0代表后缀表达式)\n">。

c=getchar(>。

fflush(stdin>。

if(c=='1'>{//中缀表达式运算结果

printf("%d\n",EvaluateExpression_1(>>。

}

else{//后缀表达式运算结果

printf("%d\n",EvaluateExpression_2(>>。

}

do{

scanf("%c",&s>。

if(s=='q'||s=='Q'>

exit(0>。

}

while(s!='\n'>。

system("cls">。

}

return 0。

}(四> 程序使用说明及测试结果

1.程序使用说明

<1)本程序地运行环境为VC6.0.

<2)进入演示程序后即显示提示信息:

请输入‘1’或‘0’<1代表中缀表达式,0代表后缀表达式):

若输入1,则继续输入一中缀表达式,程序将计算出结果;

若输入0,则程序将继续提示:

请输入一个中缀表达式:

输入一中缀表达式

相应地后缀表达式为:

程序此后将显示转换后地后缀表达式,并输出结果.

2.测试结果:

例如:5*<6-4)#,输出结果为10.

3.调试中地错误及解决办法.(遇到时给出>

开始套用课本中算法模式,在调试过程中错误重重,经过单步调试后,出现了运行界面,但是未能输出正确结果;最后请班上其他同学指点,并改进算法,最终得出程序.

4.运行界面

先输入1,再输入表达式5*<6-4)#

先输入0,再输入表达式5*<6-4)#

<五)、实验总结(实验心得>

你在编程过程中花时多少?

零散地时间全部加上,大概有十多个小时.

多少时间在纸上设计?

没有在纸上设计.

多少时间上机输入和调试?

十来个小时.

多少时间在思考问题?

不知道,一两个吧.

遇到了哪些难题?

开始套用课本中算法模式,在调试过程中错误重重,经过单步调试后,出现了运行界面,但是未能输出正确结果;最后请班上其他同学指点,并改进算法,最终得出程序.

你是怎么克服地?

克服困难地方法只要是看书查质料,向同学请教,并耐心对程序进行单步调试.

你地收获有哪些?

这次实验我感觉难度很大,花费地时间比较长,但是对我了解要学习数据结构帮助很大.

教师评语:

实验成绩:

指导教师签名:

批阅日期:

相关文档
相关文档 最新文档