数据结构考研分类复习真题 第三章 答案[18]

[题目分析]逆波兰表达式(即后缀表达式)求值规则如下设立运算数栈OPND对表达式从左到右扫描(读入)当表达式中扫描到数时压入OPND栈当扫描到运算符时从OPND退出两个数进行相应运算结果再压入OPND栈这个过程一直进行到读出表达式结束符$这时OPND栈中只有一个数就是结果

float expr( )

//从键盘输入逆波兰表达式以$表示输入结束本算法求逆波兰式表达式的值

｛float OPND[]; // OPND是操作数栈

init(OPND); //两栈初始化

float num=; //数字初始化

scanf (%c&x);//x是字符型变量

while(x!=$)

{switch

{case<=x<=:while((x>=&&x<=)||x==) //拼数

if(x!=) //处理整数

{num=num*+（ord(x)ord()）; scanf(%c&x);}

else //处理小数部分

{scale=; scanf(%c&x);

while(x>=&&x<=)

{num=num+(ord(x)ord()/scale;

scale=scale*; scanf(%c&x); }

}//else

push(OPNDnum); num=;//数压入栈下个数初始化

case x= :break; //遇空格继续读下一个字符

case x=+:push(OPNDpop(OPND)+pop(OPND));break;

case x=:x=pop(OPND);x=pop(OPND);push(OPNDxx);break;

case x=*:push(OPNDpop(OPND)*pop(OPND));break;

case x=/:x=pop(OPND);x=pop(OPND);push(OPNDx/x);break;

default: //其它符号不作处理

}//结束switch

scanf(%c&x);//读入表达式中下一个字符

}//结束while（x！=$）

printf(后缀表达式的值为%fpop(OPND));

}//算法结束

[算法讨论]假设输入的后缀表达式是正确的未作错误检查算法中拼数部分是核心若遇到大于等于且小于等于的字符认为是数这种字符的序号减去字符的序号得出数对于整数每读入一个数字字符前面得到的部分数要乘上再加新读入的数得到新的部分数当读到小数点认为数的整数部分已完要接着处理小数部分小数部分的数要除以（或的幂数）变成十分位百分位千分位数等等与前面部分数相加在拼数过程中若遇非数字字符表示数已拼完将数压入栈中并且将变量num恢复为准备下一个数这时对新读入的字符进入+*/及空格的判断因此在结束处理数字字符的case后不能加入break语句

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []