数据�l�构�W�三章设计题及参考答案[3]_跨考网

 1. 从键盘上输入一个逆�L兰表辑ּ��Q�用伪码写出其求值程序。规定：逆�L兰表辑ּ�的长度不���过一行，�?/span>$�W�作�����入结束，操作��C��间用�I�格分隔,操作�W�只可能�?/span>+�?/span>-�?/span>*�?/span>/四种�q�算。例如：234 34+2*$�?a target="_blank">�׃��师范大学 1999 �?/span> �Q?/span>10分）�?/span>

　　【参考答案�?/span>

　　[题目分析]逆�L兰表辑ּ�(卛_���~�表达�?/span>)求��D��则如下：讄����q�算数栈OPND,对表辑ּ�从左到右扫描(��d��)�Q�当表达式中扫描到数�Ӟ��压入OPND栈。当扫描到运���符�Ӟ���?/span>OPND退��Z��个数�Q�进行相应运���，�l�果再压�?/span>OPND栈。这个过�E�一直进行到��d��表达式结束符$�Q�这�?/span>OPND栈中只有一个数�Q�就是结果�?/span>

　　float expr( )

　　//从键盘输入逆�L兰表辑ּ��Q�以�?/span>$’表�C����入结束，本算法求逆�L兰式表达式的倹{�?/span>

　　�?/span>float OPND[30]; // OPND是操作数栈�?/span>

　　init(OPND); //两栈初始化�?/span>

　　float num=0.0; //数字初始化�?/span>

　　scanf (�?/span>%c�?/span>,&x);//x是字�W�型变量�?/span>

　　while(x!=�?/span>$�?/span>)

　　{switch

　　{case�?/span>0�?/span><=x<=�?/span>9�?/span>:while((x>=�?/span>0�?/span>&&x<=�?/span>9�?/span>)||x==�?/span>.�?/span>) //拼数

　　if(x!=�?/span>.�?/span>) //处理整数

　　{num=num*10+�Q?/span>ord(x)-ord(�?/span>0�?/span>)�Q?/span>; scanf(�?/span>%c�?/span>,&x);}

　　else //处理���数部分�?/span>

　　{scale=10.0; scanf(�?/span>%c�?/span>,&x);

　　while(x>=�?/span>0�?/span>&&x<=�?/span>9�?/span>)

　　{num=num+(ord(x)-ord(�?/span>0�?/span>)/scale;

　　scale=scale*10; scanf(�?/span>%c�?/span>,&x); }

　　}//else

　　push(OPND,num); num=0.0;//数压入栈�Q�下个数初始�?/span>

　　case x=�?/span> �?/span>:break; //遇空��|���l�箋��M��一个字�W��?/span>

　　case x=�?/span>+�?/span>:push(OPND,pop(OPND)+pop(OPND));break;

　　case x=�?/span>-�?/span>:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;

　　case x=�?/span>*�?/span>:push(OPND,pop(OPND)*pop(OPND));break;

　　case x=�?/span>/�?/span>:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;

　　default: //其它�W�号不作处理�?/span>

　　}//�l�束switch

　　scanf(�?/span>%c�?/span>,&x);//��d��表达式中下一个字�W��?/span>

　　}//�l�束while�Q?/span>x�Q?/span>=�?/span>$’）

　　printf(“后�~�表达式的��gؓ(f��)%f�?/span>,pop(OPND));

　　}//���法�l�束�?/span>

　　[���法讨论]假设输入的后�~�表达式是正确的，未作错误���查。算法中拼数部分是核心。若遇到大于�{�于�?/span>0’且���于�{�于�?/span>9’的字符�Q�认为是数。这�U�字�W�的序号减去字符�?/span>0’的序号得出数。对于整敎ͼ�每读入一个数字字�W�，前面得到的部分数要乘�?/span>10再加新读入的数得到新的部分数。当��d�����数点，认�ؓ(f��)数的整数部分已完�Q�要接着处理���数部分。小数部分的数要除以10�Q�或10的幂敎ͼ�变成十分位，癑ֈ�位，千分位数�{�等�Q�与前面部分数相加。在拼数�q�程中，若遇非数字字�W�，表示数已拼完�Q�将数压入栈中，�q�且���变�?/span>num恢复�?/span>0�Q�准备下一个数。这时对新读入的字符�q�入�?/span>+’、�?/span>-’、�?/span>*’、�?/span>/’及�I�格的判断，因此在结束处理数字字�W�的case后，不能加入break语句�?/span>