波兰式转换为逆波兰式

《波兰式转换为逆波兰式》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、波兰式转换为逆波兰式（中缀表达式转换为后缀表达式）逆波兰式（ReversePolishnotation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）一、定义一个表达式E的后缀形式可以如下定义：（1）如果E是一个变量或常量，则E的后缀式是E本身。（2）如果E是E1opE2形式的表达式，这里op是如何二元操作符，则E的后缀式为E1'E2'op，这里E1'和E2'分别为E1和E2的后缀式。（3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：

2、ab+(a+b)*c-(a+b)/e的后缀表达式为：(a+b)*c-(a+b)/e→((a+b)*c)((a+b)/e)-→((a+b)c*)((a+b)e/)-→(ab+c*)(ab+e/)-→ab+c*ab+e/-二、算法实现将一个普通的中序表达式转换为逆波兰表达式的一般算法是：首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为输入逆波兰式的栈S2（空栈），S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐

3、序进行如下步骤：（1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符优先级大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，则将该运算符送入S1栈。（3）若取出的字符是“（”，则直接送入S1栈栈顶。（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。（5）重复上面的1~4步

4、，直至处理完所有的输入字符（6）若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。完成以上步骤，S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！三、作用实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。四、举例下面

5、以(a+b)*c为例子进行说明：(a+b)*c的逆波兰式为ab+c*，假设计算机把ab+c*按从左到右的顺序压入栈中，并且按照遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈的原则来进行处理，那么ab+c*的执行结果如下：1）a入栈（0位置）2）b入栈（1位置）3）遇到运算符“+”，将a和b出栈，执行a+b的操作，得到结果d=a+b，再将d入栈（0位置）4）c入栈（1位置）5）遇到运算符“*”，将d和c出栈，执行d*c的操作，得到结果e，再将e入栈（0位置）经过以上运算，计算机就可以得到(a+b)*c的运算结果e了

6、。逆波兰式除了可以实现上述类型的运算，它还可以派生出许多新的算法，数据结构，这就需要灵活运用了。逆波兰式只是一种序列体现形式。五、程序实现//逆波兰式（C语言版）#include#include#include#include#definemax100charex[max];/*存储后缀表达式*/voidtrans(){/*将算术表达式转化为后缀表达式*/charstr[max];/*存储原算术表达式*/charstack[max];/*作为栈使用

7、*/charch;intsum,i,j,t,top=0;printf("*****************************************");printf("*输入一个求值的表达式，以#结束。*");printf("******************************************");printf("算数表达式：");i=0;/*获取用户输入的表达式*/do{i++;cin>>str[i];/*此步我用的是C++C语言的话在后面之所以用这个有一点区别都*///scanf("%

8、c",&str[i]);}while(str[i]!='#'&&i!=max);sum=i;t=1;i=1;ch=str[i];i++;//while(ch!='#'){switch(ch){case'(':/*判定为左括号*/top++;stack[top]=ch;break;case'