数据结构课程设计表达式求值问题-1

1/1数据结构课程设计-表达式求值问题

嘉应学院计算机学院

试验报告

课程名称：数据结构课程设计

开课学期：2022-2023学年第2学期

班级：

指导老师：

试验题目：同学通讯录管理系统

学号：

姓名：

上机时间：

(一)需求分析

1、输入的形式和输入值的范围：

依据题目要求与提示，先选择你要使用的表达式形式（中缀用1，后缀用0），在输入一个中缀表达式，输入数的范围为int型，此时，程序将计算出表达式的结果。

2、输出的形式：

当根据程序要求选择了1或0之后，再输入表达式；假如选择的是1，则程序将自动运算出表达式结果；假如之前选择的是0，则程序将现将中缀表达式转化为后缀表达式并计算出结果。

3、程序所能达到的功能：

本程序能计算出含+、-、*、/、（、）等运算符的简洁运算。

4、测试数据：

输入一个表达式，假如你之前选择的是“中缀表达式”，那么输入5*(4-2)#,那么输出结果是10；假如之前选择的是“后缀表达式”，那么输入5*（4-2）#，那么他将先转换成后缀表达式542-*#，再输出结果10。

假如输入表达式没有结束标示符#，如5*（4-2），那将不会输出任何结果，或消失错误结果。

(二)概要设计

为了实现上述操作，应以栈为存储结构。

1．基本操作：

（1）.intGetTop(SqStack*s)

初始条件：栈存在；

操作结果：若栈为空，则返回s的栈顶元素；否则返回ERROR。

（2）.voidPush(SqStack*s,inte)

初始条件：栈存在；

操作结果：插入e为新的栈顶元素。

（3）.intPop(SqStack*s)

初始条件：栈存在；

操作结果：若栈不空，则删除之，并返回其值；否则返回REEOR。

（4）.voidInitStack(SqStack*s)

初始条件：栈存在；

操作结果：置栈为空。

（5）.intEmpty(SqStack*s)

初始条件：栈存在；

操作结果：判定s是否为空栈。

（6）.intOperate(inta,chartheta,intb)

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

操作结果：返回a与b间theta运算的结果。

（7）.intIn(chars,char*TestOp)

初始条件：s为待推断字符，TestOp为已知的算符集合；

操作结果：s为算符集合中的元素则返回1，否则返回0.

（8）.intReturnOpOrd(charop,char*TestOp)

初始条件：op为待确定运算符，TestOp为已知的算符集合；

操作结果：确定运算符类型。

（9）.charprecede(chara,charb)

初始条件：a、b存在；

操作结果：返回算符a和b的优先权凹凸。

（10）.voidPrintOpnd(SqStack*s)

初始条件：栈存在；

操作结果：输出运算数栈。

（11）.voidPrintOptr(SqStack*s)

初始条件：栈存在；

操作结果：输出运算符栈。

（12）.voidStore(char*s,charch)

初始条件：字符数组s存在，字符ch已知；

操作结果：将ch存入数组s。

（13）.voidChange(char*s1,char*s2)

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

操作结果：将中缀表达式s1转为后缀表达式s2。

2．本程序包含二个模块：

（1）主程序模块；

（2）中缀表达式求值模块以及中缀表达式转换为后缀表达式并求值模块（3）模块调用图：

主程序模块

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

(三)具体设计

1．存储类型，元素类型，结点类型：

typedefstruct{//定义栈

intdata[SIZE];

inttop;

intbase;

}SqStack;

charOPSET[7]={'+','-','*','/','(',')','#'};

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

charPrior[7][7]={

//算符间的优先关系

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

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

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

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

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

'='0'

}

Push(

s=0;

ch=exp[i];

}

}

else

switch(precede(GetTop(

ch=exp[++i];

break;

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

Pop(

ch=exp[++i];

break;

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

theta=Pop(

b=Pop(

a=Pop(

Push(

break;

}//switch

}//while

returnGetTop(

}//EvaluateExpression_1

intEvaluateExpression_2{//后缀求值

SqStackOPND;

charch,theta,receive[100]={0},exp[100]={0};

inti=0,s=0,a=0,b=0,step=0;

InitStack(

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(

i+=2;

ch=exp[i];

}//if

else//消失连续数字

{

s=exp[i++]-48;

while(exp[i]>='0'

}//while

Push(

s=0;

ch=exp[++i];

}//else

}//if

else{

theta=ch;

b=Pop(

a=Pop(

Push(

i+=2;

ch=exp[i];

}

}

returnGetTop(

}//EvaluateExpression_2（

3）函数调用关系图

3．完整的程序：

#include"stdio.h"

#include"stdlib.h"

#defineSIZE80

#defineOK1

#defineERROR0

typedefstruct{//定义栈

intdata[SIZE];

inttop;

intbase;

}SqStack;

charOPSET[7]={'+','-','*','/','(',')','#'};//定义OPSET字符数组为算符集合

charPrior[7][7]={

//算符间的优先关系

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

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

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

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

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

'top==s->base)

returnERROR;

return(s->data[s->top-1]);

}

voidPush(SqStack*s,inte){

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

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

s->top++;

}

intPop(SqStack*s){

//若栈不空，则删除之，并返回其值；否则返回REEORinte;

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

returnERROR;

else{

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

s->top--;

}

returne;

}

voidInitStack(SqStack*s){

//置栈S为空

s->top=0;

s->base=0;

}

intEmpty(SqStack*s){

//判定s是否为空栈

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

return1;

else

return0;

}

intOperate(inta,chartheta,intb){

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

switch(theta){

case'+':returna+b;break;

case'-':returna-b;break;

case'*':returna*b;break;

case'/':returna/b;break;

default:return0;

}

}

intIn(chars,char*TestOp){

//s为待推断字符，TestOp为已知的算符集合

intFind=0;

for(inti=0;ibase;

printf("StackOPND:");

if(!Empty(s)){

for(;itop);i++)

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

}

else

printf("");

printf("\n");

}

voidPrintOptr(SqStack*s){

//输出运算符栈

inti=s->base;

printf("StackOPTR:");

for(;itop);i++)

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

printf("\n");

}

voidStore(char*s,charch){

//将ch存入数组s

char*p=s;

while(*p){

p++;

}

*p++=ch;

}

intEvaluateExpression_1{

//中缀求值

SqStackOPND,OPTR;

charch,theta,exp[100]={0};

inti=0,s=0,a=0,b=0,step=0;

InitStack(

InitStack(

Push(

gets(exp);

ch=exp[0];

while(ch!='#'||GetTop(

ch=exp[++i];

}//if

else//消失连续数字

{

s=exp[i++]-48;

while(exp[i]>='0'

}

Push(

s=0;

ch=exp[i];

}

}

else

switch(precede(GetTop(

ch=exp[++i];

break;

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

Pop(

ch=exp[++i];

break;

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

theta=Pop(

b=Pop(

a=Pop(

Push(

break;

}//switch

}//while

returnGetTop(

}//EvaluateExpression_1

voidChange(char*s1,char*s2){

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

SqStackOPTR;

charch;

inti=0,sum=0;

InitStack(

Push(

ch=s1[0];

while(ch!='#'||GetTop(

Store(s2,'');//存入一个空格

ch=s1[++i];

}//if

else//消失连续数字

{

while(s1[i]>='0'

i++;

}//while

Store(s2,'');//存入一个空格

ch=s1[i];

}//else

}//if

else

switch(precede(GetTop(

ch=s1[++i];

break;

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

Pop(

ch=s1[++i];

break;

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

Store(s2,Pop(

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

break;

}//switch

}//while

Store(s2,ch);

}//Change

intEvaluateExpression_2{//后缀求值

SqStackOPND;

charch,theta,receive[100]={0},exp[100]={0};

inti=0,s=0,a=0,b=0,step=0;

InitStack(

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(

i+=2;

ch=exp[i];

}//if

else//消失连续数字

{

s=exp[i++]-48;

while(exp[i]>='0'

}//while

Push(

s=0;

ch=exp[++i];

}//else

}//if

else{

theta=ch;

b=Pop(

a=Pop(

Push(

i+=2;

ch=exp[i];

}

}

returnGetTop(

}//EvaluateExpression_2

intmain{

chars=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",

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

exit(0);

}

while(s!='\n');

system("cls");

}

return0;

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

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）#

（五）、试验总结(试验心得)

开头套用课本中算法模式，在调试过程中错误重重，经过单步调试后，消失了运行界面，但是未能输出正确结果；最终请班上其他同学教导，并改进算法，最终得出程序。

这次试验我感觉难度很大，花费的时间比较长，但是对我了解要学习数据结构关心很大。

完整代码如下：

#include

#include

#include

#include

#defineMAXSIZE100

typedefintbool

#definetrue1

#definefalse0

typedefintelemtype;

charch[7]={'+','-','*','/','(',')','#'};

intf1[7]={3,3,5,5,1,6,0};

intf2[7]={2,2,4,4,6,1,0};

intn=0;

typedefstructsqstack//挨次栈结构

{

elemtypestack[MAXSZIE];

inttop;

}sqstack;

//1.把操作符转换成相应的数字

elemtypecton(charc)

{

switch(c)

{

case'+':return0;

case'-':return1;

case'*':return2;

case'/':return3;

case'(':return4;

case')':return5;

default:return6;

}

}

//2.按设定比较两个字符的优先级

charCompare(charc1,charc2)

{

inti1=cton(c1);