中缀表达式转化成后缀表达式的计算.docx
- 文档编号:4225484
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:30
- 大小:96.50KB
中缀表达式转化成后缀表达式的计算.docx
《中缀表达式转化成后缀表达式的计算.docx》由会员分享,可在线阅读,更多相关《中缀表达式转化成后缀表达式的计算.docx(30页珍藏版)》请在冰点文库上搜索。
中缀表达式转化成后缀表达式的计算
一、设计思想……………………………………………………….01
二、算法流程图…………………………………………………….02
三、源代码………………………………………………………….03
四、运行结果……………………………………………………….16
五、遇到的问题及解决…………………………………………….17
六、心得体会……………………………………………………….18
一、设计思想
第一种算法
先把算术表达式转化成后缀表达式,在对后缀表达式进行计算。
首先建立一个符号栈,用于存放字符和字符的优先级别;然后在建立一个数栈,用于辅助后缀表达式的计算;最后在定义一个字符串数组,用于存放后缀表达式。
建立一个计算的函数,该函数用于两个数的计算,在调用这个函数的时候,传入三个参数,两个浮点型参数和一个字符型参数,根据不同的符号进行不同的计算。
定义一个判断优先级别的函数,用于判断两个操作符的优先级别,在根据优先级的不同决定不同的操作。
后缀表达式的取得,对算术表达式字符串进行挨个的扫描,如果是数字或者是小数点,
则将数字或者小数点存放到字符数组中,每取完一个数字,则在后面用“|”隔开,如果是操作符,则和栈中得操作符进行比较,若扫描到的符号优先级比栈里的符号优先级低,则栈中元素出栈并存放到字符数组中。
每出一个字符到字符数组中就在后面加“|”分隔。
继续检查栈顶比较优先级,直到栈中元素优先级比扫描到的符号优先级低或者符号栈为空,则将此操作符入栈。
若是“(”则无条件入字符栈,若是“)”则从字符栈中出字符直到遇到“(”为止。
当字符数组扫描到最后的时候,计算并没有结束。
然后得进行字符栈的判断,看是否已经为空栈,若不是空栈,则出栈字符,将字符存放到数组中。
最后字符串数组中存放的就是后缀表达式。
得到后缀表达式后,要用数栈进行后缀表达式的计算,后缀表达式的计算中,对新的数组进行从道到尾的扫描,如果遇到数字,以“|”为标记取出完整的操作数,用辅助数组存放,然后转化成浮点数存放到数栈中,遇到“|”则直接将数组下标往后走。
遇到字符,则从数栈取出两个数进行计算,将计算的结果从新存放到数栈中,循环直到接到结束。
最后存放在数栈中的数就是计算的结果。
最后在主函数中调用此函数,进行结果的输出。
第二种算法
对表达式直接进行计算,也称为边走边计算
首先建立一个符号栈,用于存放字符和字符的优先级别;然后建立一个数栈,用于存放数。
建立一个计算的函数,该函数用于两个数的计算,在调用这个函数的时候,传入三个参数,两个浮点型参数和一个字符型参数,根据不同的符号进行不同的计算。
定义一个判断优先级别的函数,用于判断两个操作符的优先级别,在根据优先级的不同决定不同的操作。
边走边计算实现,扫描算术表达式,如果遇到数字或者是小数点,则进行循环的扫描直到将整个数字从字符数组中取出,把取出的字符存放到一个数组中,在利用c语言的函数把这个字符串的数字转化成浮点型的数字,然后存放到数栈中,若果是字符,则将字符的优先级与字符栈中的字符优先级进行比较,若优先级别低于字符栈中的符号优先级别,则从字符栈中取出操作符,再从数栈中取出两个数字,进行计算,计算的结果存放到数栈中,继续检查符号栈中的元素直到遇到优先级别比扫描到的字符优先级别低或者符号栈为空,将扫描到的符号入栈。
。
若是“(”则无条件入字符栈,若是“)”则从字符栈中出栈字符从数栈中取数进行计算,直到遇到“(”为止。
当字符数组扫描到最后的时候,计算并没有结束。
然后得进行字符栈的判断,看是否已经为空栈,若不是空栈,则出栈字符,每出栈一个字符就出栈两个数字,进行计算,直到字符栈空为止。
最终存放在数栈中的数就是计算的结果。
最后在主函数中调用此函数,进行结果的输出。
二、算法流程图
第一种算法:
先将中缀表达式转化成后缀表达式,然后计算。
图1中缀转后缀流程图
图2后缀表达式的计算
图3直接计算中缀表达式
三、源代码
先将中缀表达式转化成后缀表达式,在进行后缀表达式的计算,最后将结果显示。
下面给出的是用第一种算法实现的的程序的源代码:
#include
#include
#include
//创建存放字符的结构体
typedefstruct
{
charch;//定义ch存放操作符
intlevel;//定义level存放操作符的优先级
}OpNode;
//创建字符栈
typedefstruct
{
OpNodeopNode[100];
inttop;//存放栈顶的数
intsize;//存放当前栈的大小
}OpStack;
//对字符栈的初始化
voidOp_init(OpStack*ops)
{
ops->top=0;
ops->size=0;
}
//字符栈的入栈操作
voidOp_push(OpStack*ops,OpNodeop)
{
ops->size++;
ops->opNode[(ops->top)++]=op;
}
//字符栈的出栈操作
OpNodeOp_pop(OpStack*ops)
{
if(ops->size==0)//判断栈是否为空,如果为空,则退出程序,否则出栈
{
exit(-1);
}
ops->size--;
returnops->opNode[--(ops->top)];
}
//看字符栈顶操作
OpNodeOp_getTop(OpStack*ops)
{
intlen=ops->size;
returnops->opNode[len-1];
}
//创建存放数的结构体
typedefstruct
{
doubled;//定义d存放操作数
}TdNode;
//创建数栈
typedefstruct
{
TdNodetdNode[100];
intsize;
inttop;
}TdStack;
//数栈的初始化
voidTd_init(TdStack*tds)
{
tds->size=0;
tds->top=0;
}
//数栈的入栈
voidTd_push(TdStack*tds,TdNodetd)
{
tds->size++;
tds->tdNode[(tds->top)++]=td;
}
//数栈的出栈
TdNodeTd_pop(TdStack*tds)
{
if(tds->size==0)//判断栈是否为空,如果为空,则退出程序,否则出栈
{
exit(-1);
}
tds->size--;
returntds->tdNode[--(tds->top)];
}
//看数栈栈顶
TdNodeTd_getTop(TdStack*tds)
{
intlen=tds->size;
returntds->tdNode[len-1];
}
//创建一个返回值为double函数,用于两个数的计算,传入三个变量,
//第一个变量为操作数1,第二个变量为操作数2,第三个变量为操作符
doubleCal(doublenum_1,doublenum_2,charop)
{
doublenum=0;//定义一个变量用于接收计算的结果
switch(op)
{
case'+':
num=num_1+num_2;break;
case'-':
num=num_1-num_2;break;
case'*':
num=num_1*num_2;break;
case'/':
if(num_2==0)//如果除数为零,则推出程序并打印错误信息
{
printf("\ndivisorzerocan't");
exit(-1);
}
else
num=num_1/num_2;
}
returnnum;
}
//创建一个返回值为int型的函数,用于比较两个操作符的优先级
intCompare_opeate(intlevel_1,intlevel_2)
{
if(level_1>=level_2)//判断优先级别,返回相应的值
return0;
return-1;
}
//创建一个返回值为double型的函数,用于返回整个表达式的计算结果
doubleCalResult()
{
//charch[]="23+12-34";
//charch[]="19-(2*3)+12/2";
charch[]="(23-3)/0+12*2";
chartempCh[100];//存放后缀表达式
intindex=0,i=0;
OpStackops;//定义操作符栈
TdStacktds;//定义操作数栈
OpNodeop;//定义字符节点
TdNodetd;//定义数节点
Op_init(&ops);//初始化字符栈
Td_init(&tds);//初始化操作数栈
while(ch[index]!
='\0')
{
charchr=ch[index];
if(chr>='0'&&chr<='9'||chr=='.')
{
inttempIndex=index;
while(chr>='0'&&chr<='9'||chr=='.')//判断是否为操作数
{
tempCh[i++]=ch[tempIndex];
tempIndex++;
chr=ch[tempIndex];
}
tempCh[i++]='|';//在一个操作数取完之后,后面加分隔符
index=tempIndex;
continue;
}
//判断是否为加法或者减法运算
if(chr=='+'||chr=='-')
{
op.ch=chr;//存放操作符到操作符节点
op.level=2;//给操作符赋值优先级
intlevel_2=2;//存放优先级别,用于比较优先级
while(ops.size!
=0)//若字符栈不为空,则进行字符的优先级比较
{
intlevel_1=Op_getTop(&ops).level;
//两个字符比较优先级,若新的字符优先级比栈中的字符优先级高,则
//从字符栈中字符出栈,将出栈的字符放到后续数组中
if(Compare_opeate(level_1,level_2)==0)
{
charop1=Op_pop(&ops).ch;
tempCh[i++]=op1;
tempCh[i++]='|';
}
else
{
Op_push(&ops,op);
break;
}
}
if(ops.size==0)//若字符栈是空栈,则直接进行入栈的操作
{
Op_push(&ops,op);
}
index++;
continue;
}
//判断是否为乘法或者除法的运算符
if(chr=='*'||chr=='/')
{
op.ch=chr;//存放操作符到操作符节点
op.level=3;//给操作符赋值优先级
intlevel_2=3;//存放优先级别,用于比较优先级
while(ops.size!
=0)
{
intlevel_1=Op_getTop(&ops).level;
//两个字符比较优先级,若新的字符优先级比栈中的字符优先级高,则
//从字符栈中字符出栈,将出栈的字符放到后续数组中
if(Compare_opeate(level_1,level_2)==0)
{
charop1=Op_pop(&ops).ch;
tempCh[i++]=op1;
tempCh[i++]='|';
}
else
{
Op_push(&ops,op);
break;
}
}
if(ops.size==0)//若字符栈是空栈,则直接进行入栈的操作
{
Op_push(&ops,op);
}
index++;
continue;
}
//判断是否为左括号,直接进行入栈操作
if(chr=='(')
{
op.ch=chr;
op.level=-1;
Op_push(&ops,op);
index++;
continue;
}
//判断是否为右括号
if(chr==')')
{
charch1=Op_getTop(&ops).ch;
//进行出栈的操作,知道遇到左括号为止。
将出栈的字符加入后续字符中
while(ch1!
='(')
{
charop1=Op_pop(&ops).ch;
tempCh[i++]=op1;
tempCh[i++]='|';
ch1=Op_getTop(&ops).ch;
}
Op_pop(&ops);
index++;
continue;
}
}
//如果字符栈不为空,则一直出栈直到字符栈为空。
while(ops.size!
=0)
{
charop1=Op_pop(&ops).ch;
tempCh[i++]=op1;
tempCh[i++]='|';
}
tempCh[i++]='\0';//最后在字符数组中加字符的结束标志\0
intj=0;
//打印后缀表达式
printf("follow-upexpression:
");
while(tempCh[j]!
='\0')
{
printf("%c",tempCh[j]);
j++;
}
intk=0;
//将后缀表达式进行计算
while(tempCh[k]!
='\0')
{
charcc=tempCh[k];
if(cc>='0'&&cc<='9'||cc=='.')//判断是否为操作数
{
inttempIndex=k;
inti=0;
charassch[10]={0};//定义数组存放一个操作数,并进行初始化
while(cc>='0'&&cc<='9'||cc=='.')
{
assch[i++]=tempCh[tempIndex];
tempIndex++;
cc=tempCh[tempIndex];
}
td.d=atof(assch);
Td_push(&tds,td);//将取出的操作数入栈
k=tempIndex;
continue;
}
elseif(cc=='|')//如是|则直接跳过
{
k++;
}
else//如果是字符,则出栈两个数进行计算
{
charop1=cc;
doublenum_2=Td_pop(&tds).d;
doublenum_1=Td_pop(&tds).d;
doublenum=Cal(num_1,num_2,op1);
td.d=num;
Td_push(&tds,td);
k++;
}
}
returnTd_pop(&tds).d;
}
main()
{
doubleresult=CalResult();//调用函数,得到计算的结果
printf("\nResultis:
");
printf("%.2f",result);
}
第二种算法对中缀表达式直接进行计算,并将结果输出,实现的源代码:
#include
#include
#include
//创建存放字符的结构体
typedefstruct
{
charch;//定义ch存放操作符
intlevel;//定义level存放操作符的优先级
}OpNode;
//创建字符栈
typedefstruct
{
OpNodeopNode[100];
inttop;//存放栈顶的数
intsize;//存放当前栈的大小
}OpStack;
//对字符栈的初始化
voidOp_init(OpStack*ops)
{
ops->top=0;
ops->size=0;
}
//字符栈的入栈操作
voidOp_push(OpStack*ops,OpNodeop)
{
ops->size++;
ops->opNode[(ops->top)++]=op;
}
//字符栈的出栈操作
OpNodeOp_pop(OpStack*ops)
{
if(ops->size==0)//判断栈是否为空,如果为空,则退出程序,否则出栈
{
exit(-1);
}
ops->size--;
returnops->opNode[--(ops->top)];
}
//看字符栈顶操作
OpNodeOp_getTop(OpStack*ops)
{
intlen=ops->size;
returnops->opNode[len-1];
}
//创建存放数的结构体
typedefstruct
{
doubled;//定义d存放操作数
}TdNode;
//创建数栈
typedefstruct
{
TdNodetdNode[100];
intsize;
inttop;
}TdStack;
//数栈的初始化
voidTd_init(TdStack*tds)
{
tds->size=0;
tds->top=0;
}
//数栈的入栈
voidTd_push(TdStack*tds,TdNodetd)
{
tds->size++;
tds->tdNode[(tds->top)++]=td;
}
//数栈的出栈
TdNodeTd_pop(TdStack*tds)
{
if(tds->size==0)//判断栈是否为空,如果为空,则退出程序,否则出栈
{
exit(-1);
}
tds->size--;
returntds->tdNode[--(tds->top)];
}
//看数栈栈顶
TdNodeTd_getTop(TdStack*tds)
{
intlen=tds->size;
returntds->tdNode[len-1];
}
//创建一个返回值为double函数,用于两个数的计算,传入三个变量,
//第一个变量为操作数1,第二个变量为操作数2,第三个变量为操作符
doubleCal(doublenum_1,doublenum_2,charop)
{
doublenum=0;//定义一个变量用于接收计算的结果
switch(op)
{
case'+':
num=num_1+num_2;break;
case'-':
num=num_1-num_2;break;
case'*':
num=num_1*num_2;break;
case'/':
if(num_2==0)//如果除数为零,则推出程序并打印错误信息
{
printf("divisorzerocan't");
exit(-1);
}
else
num=num_1/num_2;
}
returnnum;
}
//创建一个返回值为int型的函数,用于比较两个操作符的优先级
intCompare_opeate(intlevel_1,intlevel_2)
{
if(level_1>=level_2)//判断优先级别,返回相应的值
return0;
return-1;
}
//创建一个返回值为double型的函数,用于返回整个表达式的计算结果
doubleCalResult()
{
//charch[]="23+12-34";
charch[]="19-(2*3)+12/0";
//charch[]="(23-3)/2+12*2";
intindex=0;//定义字符串的索引
OpStackops;//定义操作符栈
TdStacktds;//定义操作数栈
OpNodeop;//定义字符节点
TdNodetd;//定义数节点
Op_init(&ops);//初始化字符栈
Td_init(&tds);//初始化操作数栈
while(ch[index]!
='\0')
{
charchr=ch[index];//取出字符串的而一个字符
if(chr>='0'&&chr<='9'||chr=='.')//判断是否为操作数
{
inttempIndex=index;//定义辅助索引
inti=0;
chartempCh[10]={0};//定义数组存放一个操作数,并进行初始化
//将一个操作数从字符数组中取出,并存
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中缀 表达式 转化 后缀 计算