逆波兰式

逆波兰式（reverse polish notation，rpn，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）

逆波兰式定义

一个表达式e的后缀形式可以如下定义：

（1）如果e是一个变量或常量，则e的后缀式是e本身。

（2）如果e是e1 op e2形式的表达式，这里op是如何二元操作符，则e的后缀式为e1#39;e2#39; op，这里e1#39;和e2#39;分别为e1和e2的后缀式。

（3)如果e是（e1）形式的表达式，则e1的后缀式就是e的后缀式。

如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：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栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤：

（1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入s2栈

（2）若取出的字符是运算符，则将该运算符与s1栈栈顶元素比较，如果该运算符优先级大于s1栈栈顶运算符优先级，则将该运算符进s1栈，否则，将s1栈的栈顶运算符弹出，送入s2栈中，直至s1栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送入s1栈。

（3）若取出的字符是“（”，则直接送入s1栈顶。

（4）若取出的字符是“）”，则将距离s1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入s2栈，此时抛弃“（”。

（5）重复上面的1~4步，直至处理完所有的输入字符

（6）若取出的字符是“#”，则将s1栈内所有运算符（不包括“#”），逐个出栈，依次送入s2栈。

完成以上步骤，s2栈便为逆波兰式输出结果。不过s2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！

逆波兰式计算方法

新建一个表达式,如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。

逆波兰式举例

下面以(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了。

逆波兰式除了可以实现上述类型的运算，它还可以派生出许多新的算法，数据结构，这就需要灵活运用了。逆波兰式只是一种序列体现形式。

逆波兰式算法图示

其中△代表一个标识，ω代表预算法，名字q代表变量（如int a，b等），

算法用到三个栈：a栈，b栈，in栈。

其中a栈用来存储逆波兰式，b用来存储△号和运算符，in栈为输入栈。

第一竖排为b栈中符号，第一横排为输入栈中符号。

pop（in）为输入栈栈顶元素出栈，pop（a，q）为q入a栈，next算法即为进行下一轮循环，其中ω1lt;ω2为算符优先级，如“+”和“-”lt;“*”和“/”。pop（b，b），push（b，b）中b为临时变量，用来存储出栈的元素。stop为算法结束。

算法开始时，现将△如b栈，输入栈以#号结尾。

输入流

b[s-1]

名字q

(

ω2

)

#

△

pop(in);

push(a，q)

next

pop(in);

push(b，△)

next

pop(in)

push(b，ω2)

next

pop(in)

pop(b，b)next

stop

ω1

pop(in)

push(a，q)

next

pop(in)

push(b，△)

next

若ω1lt;ω2，则

pop(in)

push(b，ω2)

next

若ω1≥ω2，则pop(in)

pop(b，b），

push(a,b)

pop(b，b)

push(a，b)

pop(b，b)

push(a，b)

逆波兰式程序实现

逆波兰式c/c++语言版

//#includelt;iostreamgt;
#includelt;stdlib.hgt;
#includelt;stdio.hgt;
#includelt;stackgt;
#includelt;math.hgt;
#includelt;string.hgt;
#definemax100
usingnamespacestd;
charex[max];/*存储后缀表达式*/

voidtrans()
{/*将算术表达式转化为后缀表达式*/
charstr[max];/*存储原算术表达式*/
charstack[max];/*作为栈使用*/
charch;
intsum,i,j,t,top=0;
printf(*****************************************\n);
printf(*输入一个求值的表达式，以#结束。*\n);
printf(******************************************\n);
printf(算数表达式：);
i=0;/*获取用户输入的表达式*/
do{
i++;
//cingt;gt;str[i];/*此步我用的是c++c语言的话在后面之所以用这个有一点区别都*/
scanf(%c,amp;str[i]);
}while(str[i]!=#39;##39;amp;amp;i!=max);
sum=i;
t=1;i=1;
ch=str[i];i++;
//
while(ch!=#39;##39;)
{
switch(ch)
{
case#39;(#39;:/*判定为左括号*/
top++;stack[top]=ch;
break;
case#39;)#39;:/*判定为右括号*/
while(stack[top]!=#39;(#39;)
{
ex[t]=stack[top];top--;t++;
}
top--;
break;
case#39;+#39;:/*判定为加减号*/
case#39;-#39;:
while(top!=0amp;amp;stack[top]!=#39;(#39;)
{
ex[t]=stack[top];
top--;
t++;
}
top++;
stack[top]=ch;
break;
case#39;*#39;:/*判定为乘除号*/
case#39;/#39;:
while(stack[top]==#39;*#39;||stack[top]==#39;/#39;)
{
ex[t]=stack[top];
top--;
t++;
}
top++;
stack[top]=ch;
break;
case#39;#39;:break;
default:
while(chgt;=#39;0#39;amp;amp;chlt;=#39;9#39;)
{/*判定为数字*/
ex[t]=ch;t++;
ch=str[i];i++;
}
i--;
ex[t]=#39;#39;;t++;
}
ch=str[i];i++;
}
while(top!=0)
{
ex[t]=stack[top];
t++;top--;
}
ex[t]=#39;#39;;
printf(\n\t原来表达式：);
for(j=1;jlt;sum;j++)
printf(%c,str[j]);
printf(\n\t逆波兰式：,ex);
for(j=1;jlt;t;j++)
printf(%c,ex[j]);
}

voidcompvalue()
{/*计算后缀表达式的值*/
floatstack[max],d;/*作为栈使用*/
charch;
intt=1,top=0;/*t为ex下标，top为stack下标*/
ch=ex[t];t++;
while(ch!=#39;#39;)
{
switch(ch)
{
case#39;+#39;:
stack[top-1]=stack[top-1]+stack[top];
top--;
break;
case#39;-#39;:
stack[top-1]=stack[top-1]-stack[top];
top--;
break;
case#39;*#39;:
stack[top-1]=stack[top-1]*stack[top];
top--;
break;
case#39;/#39;:
if(stack[top]!=0)stack[top-1]=stack[top-1]/stack[top];
else
{
printf(\n\t除零错误!\n);
exit(0);/*异常退出*/
}
top--;
break;
default:
d=0;
while(chgt;=#39;0#39;amp;amp;chlt;=#39;9#39;)
{
d=10*d+ch-#39;0#39;;/*将数字字符转化为对应的数值*/
ch=ex[t];t++;
}
top++;
stack[top]=d;
}
ch=ex[t];
t++;
}
printf(\n\t计算结果:%g\n,stack[top]);
}

intmain()
{
trans();
compvalue();
system(pause);
return0;
}

逆波兰式数据结构版

int precede(char op)

{ int x;

switch(op)

{

case #39;*#39;: x=2; break;

case #39;/#39;: x=2; break;

case #39;+#39;: x=1; break;

case #39;-#39;: x=1; break;

default : x=0;

}

return x;

}

char *rpexpression(char *e)

{/* 返回表达式e的逆波兰式 */

char *c;

c=(char*)malloc(sizeof(char)*20); //不能用char c[]

stack s1;

initstack(s1);

int i=0,j=0;

char ch;

push(s1,#39;@#39;);

ch=e[i++];

while(ch!= 0)

{

if(ch==#39;(#39;)

{

push(s1,ch);

ch=e[i++];

}

else if(ch==#39;)#39;)

{

while(top(s1)!=#39;(#39;)

{

pop(s1,c[j++]);

}

/* to[j++]=pop(amp;s1);*/

pop(s1,ch);

ch=e[i++];

}

else if(ch==#39;+#39;||ch==#39;-#39;||ch==#39;*#39;||ch==#39;/#39;)

{

char w;

w=top(s1);

while(precede(w)gt;=precede(ch))

{

pop(s1,c[j++]);

w=top(s1);

}

push(s1,ch);

ch=e[i++];

}

else

{

//while((chlt;=#39;z#39;amp;amp;chgt;=#39;a#39;)||(chlt;=#39;z#39; amp;amp; chgt;=#39;a#39;)){

c[j++]=ch;

ch=e[i++];

//}

//c[j++]=#39; #39;;

}

}

pop(s1,ch);

while(ch!=#39;@#39;)

{

c[j++]=ch;

pop(s1,ch);

}

//c[j++]=;

c[j++]=0;

return c;

}

还有一种方法,用2叉树.

逆波兰式二叉树法

将最终进行的运算符记为根节点，将两边的表达式分别记为左右子树，依次进行直到所有的运算符与数字或字母标在一棵二叉树上。然后对二叉树进行后序遍历即可。

35百科网 原文地址：https://www.555baike.com/9999/2186.html