逆波兰式

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

逆波兰式详细介绍

逆波兰式（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栈。

（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算法即为进行下一轮循环，其中ω1

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

?

逆波兰式程序实现

C/C++语言版

//#include<iostream>#include <stdlib.h>#include <stdio.h>#include <stack>#include <math.h>#include <string.h>#definemax100usingnamespacestd;char ex; voidtrans(){                       char str;       char stack;     char ch;    int sum, i, j, t, top = 0;    printf("*****************************************n");    printf("*输入一个求值的表达式，以#结束。*n");    printf("******************************************n");    printf("算数表达式：");    i = 0;     do    {        i++;        //cin>>str;        scanf("%c", &str);    } while (str != '#' && i != max);    sum = i;    t = 1;    i = 1;    ch = str;    i++;    //    while (ch != '#')    {        switch (ch)        {        case '(':             top++;            stack = ch;            break;        case ')':             while (stack != '(')            {                ex = stack;                top--;                t++;            }            top--;            break;        case '+':         case '-':            while (top != 0 && stack != '(')            {                ex = stack;                top--;                t++;            }            top++;            stack = ch;            break;        case '*':         case '/':            while (stack == '*' || stack == '/')            {                ex = stack;                top--;                t++;            }            top++;            stack = ch;            break;        case'':            break;        default:            while (ch >= '0' && ch <= '9')            {                 ex = ch;                t++;                ch = str;                i++;            }            i--;            ex ='';            t++;        }        ch = str;        i++;    }    while (top != 0)    {        ex = stack;        t++;        top--;    }    ex ='';    printf("nt原来表达式：");    for (j = 1; j < sum; j++)        printf("%c", str);    printf("nt逆波兰式：", ex);    for (j = 1; j < t; j++)        printf("%c", ex);}voidcompvalue(){                           floatstack, d;     charch;    intt = 1, top = 0;     ch = ex;    t++;    while (ch !='')    {        switch (ch)        {        case '+':            stack = stack + stack;            top--;            break;        case '-':            stack = stack - stack;            top--;            break;        case '*':            stack = stack * stack;            top--;            break;        case '/':            if (stack != 0)                stack = stack / stack;            else            {                printf("nt除零错误!n");                exit(0);             }            top--;            break;        default:            d = 0;            while (ch >= '0' && ch <= '9')            {                d = 10 * d + ch - '0';                 ch = ex;                t++;            }            top++;            stack = d;        }        ch = ex;        t++;    }    printf("nt计算结果:%gn", stack);}intmain(){    trans();    compvalue();    system("pause");    return 0;}

数据结构版

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){    char *c;  c=(char*)malloc(sizeof(char)*20);  //不能用char cStack s1;InitStack(s1);  int i=0,j=0;  char ch;  Push(s1,'@');  ch=e;  while(ch!= 0){      if(ch=='('){          Push(s1,ch);          ch=e;        }      else           if(ch==')'){          while(Top(s1)!='('){                  Pop(s1,c);                }                    Pop(s1,ch);          ch=e;        }else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){          char w;          w=Top(s1);          while(precede(w)>=precede(ch)){              Pop(s1,c);              w=Top(s1);            }          Push(s1,ch);          ch=e;        }else{          //while((ch='a')||(ch='A')){c=ch;ch=e;          //}          //c=' ';}        }      Pop(s1,ch);      while(ch!='@'){          c=ch;          Pop(s1,ch);       }      //c=;c=0;      return c;    }

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

逆波兰式二叉树法

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