逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式(将运算符写在操作数之后)

定义

算法实现

做法如下

逆波兰式的作用

举例

程序实现

二叉树法

算法图示

定义

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

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

（2）如果E是E1 op E2形式的表达式，这里op是如何二元操作符，则E的后缀式为E1'E2' op，这里E1'和E2'分别为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栈；若取出的是运算符，并且当前S1栈顶为(，则当前运算符直接入S1栈。

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

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

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

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

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

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

做法如下

将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。

(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

逆波兰式的作用

对于实现逆波兰式算法，难度并不大，但为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

举例

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

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

程序实现

//逆波兰式 （C语言版）

#include<iostream.h>

#include<stdlib.h>

#include<stdio.h>

#include<math.h>

#define max 100

char ex[max]; /*存储后缀表达式*/

void trans(){ /*将算术表达式转化为后缀表达式*/

char str[max]; /*存储原算术表达式*/

char stack[max]; /*作为栈使用*/

char ch;

int sum,i,j,t,top=0;

printf("*****************************************\");

printf("*输入一个求值的表达式，以#结束。*\");

printf("******************************************\");

printf("算数表达式：");

i=0; /*获取用户输入的表达式*/

do{

i++;

cin>>str[i];/*此步我用的是C++ C语言的话在后面 之所以用这个有一点区别 都*/

//scanf("%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 ')': /*判定为右括号*/

while(stack[top]!='('){

ex[t]=stack[top];top--;t++;

}

top--;

break;

case '+': /*判定为加减号*/

case '-':

while(top!=0&&stack[top]!='('){

ex[t]=stack[top];top--;t++;

}

top++;stack[top]=ch;

break;

case '*': /*判定为乘除号*/

case '/':

while(stack[top]=='*'||stack[top]=='/'){

ex[t]=stack[top];top--;t++;

}

top++;stack[top]=ch;

break;

case ' ':break;

default:while(ch>='0'&&ch<='9'){ /*判定为数字*/

ex[t]=ch;t++;

ch=str[i];i++;

}

i--;

ex[t]=' ';t++;

}

ch=str[i];i++;

}

while(top!=0){

ex[t]=stack[top];t++;top--;

}

ex[t]=' ';

printf("\\\t原来表达式：");

for(j=1;j<sum;j++)

printf("%c",str[j]);

printf("\\\t逆波兰式：",ex);

for(j=1;j<t;j++)

printf("%c",ex[j]);

}

void compvalue(){ /*计算后缀表达式的值*/

float stack[max],d; /*作为栈使用*/

char ch;

int t=1,top=0; /*t为ex下标，top为stack下标*/

ch=ex[t];t++;

while(ch!=' '){

switch(ch){

case '+':

stack[top-1]=stack[top-1]+stack[top];

top--;

break;

case '-':

stack[top-1]=stack[top-1]-stack[top];

top--;

break;

case '*':

stack[top-1]=stack[top-1]*stack[top];

top--;

break; case '/':

if(stack[top]!=0) stack[top-1]=stack[top-1]/stack[top];

else{

printf("\\\t除零错误!\");

exit(0); /*异常退出*/

}

top--;

break;

default:

d=0;

while(ch>='0'&&ch<='9'){

d=10*d+ch-'0'; /*将数字字符转化为对应的数值*/

ch=ex[t];t++;

}

top++;

stack[top]=d;

}

ch=ex[t];t++;

}

printf("\\\t计算结果:%g\",stack[top]);

}void main(){

trans();

compvalue();

}

数据结构版

int precede(char op)

{ int x;

switch(op)

{

case '*': x=2; break;

case '/': x=2; break;

case '+': x=1; break;

case '-': 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,'@');

ch=e[i++];

while(ch!= 0)

{

if(ch=='(')

{

Push(s1,ch);

ch=e[i++];

}

else if(ch==')')

{

while(Top(s1)!='(')

{

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

}

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

Pop(s1,ch);

ch=e[i++];

}

else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')

{

char w;

w=Top(s1);

while(precede(w)>=precede(ch))

{

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

w=Top(s1);

}

Push(s1,ch);

ch=e[i++];

}

else

{

//while((ch<='z'&&ch>='a')||(ch<='Z' && ch>='A')){

c[j++]=ch;

ch=e[i++];

//}

//c[j++]=' ';

}

}

Pop(s1,ch);

while(ch!='@')

{

c[j++]=ch;

Pop(s1,ch);

}

//c[j++]=;

c[j++]=0;

return c;

}

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

二叉树法

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

算法图示

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

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

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

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

pop（in）为输入栈栈顶元素出栈，pop（a，Q）为Q入a栈，NEXT算法即为进行下一轮循环，其中ω1<ω2为算符优先级，如“+”和“-”<“*”和“/”。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　若ω1<ω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)