逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）
精选百科
本文由作者推荐
逆波兰式
后缀表达式
中文名
逆波兰式
外文名
Reverse Polish notation
别名
后缀表达式
使用方式
将运算符写在操作数之后
定义
一个表达式E的后缀形式可以如下定义：
（1）如果E是一个变量或常量，则E的后缀式是E本身。
（2）如果E是E1opE2形式的表达式，这里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/-
作用
实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。逆波兰算法(RPN)在不使用括号的情况下即能完成表达式的表达和求值。[1]
算法实现
将一个普通的中序表达式转换为逆波兰表达式的一般算法是：
首先需要分配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栈，输入栈以#号结尾。
输入流 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 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++语言版
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 | //#include<iostream> #include <stdlib.h> #include <stdio.h> #include <stack> #include <math.h> #include <string.h> #definemax100 usingnamespacestd; charex[max]; /*存储后缀表达式*/
voidtrans() { /*将算术表达式转化为后缀表达式*/ charstr[max]; /*存储原算术表达式*/ charstack[max]; /*作为栈使用*/ charch; intsum, 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(" 原来表达式："); for (j = 1; j < sum; j++) printf("%c", str[j]); printf(" 逆波兰式：", ex); for (j = 1; j < 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 !='') { 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(" 除零错误! "); 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(" 计算结果:%g ", stack[top]); }
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){
/* 返回表达式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[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='a')||(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;
}
二叉树法
将最终进行的运算符记为根节点，将两边的表达式分别记为左右子树，依次进行直到所有的运算符与数字或字母标在一棵二叉树上。然后对二叉树进行后序遍历即可。
参考资料
1.中缀式到逆波兰式的转换及求值·知网空间
逆波兰式 相关的文章
为适应通信建设发展需要，合理和有效控制工程建设投资，规范通信建设概、预算的编制与管理，根据国家法律、法规及有关规定，我部修订了《通信建设工程概算、预算编制办法及费用定额》（邮部[1995]626号）以及通信建设工程预算定额等标准。
浙江大学成立于1897年，前身"求是书院"，是中国人最早自己创办的新式高等学府之一。是首批进入国家"211工程"和"985工程"建设的重点大学之一。浙江大学基础医学院的历史来源最早可追溯到1912年创办的浙江医学专门学校和1945年创设的国立浙江大学医学院。被列为教育部“985”二期建设项目，设有免疫学、细胞生物学、病理学与法医学、神经科学等4个校级研究所；医学神经生物学是卫生部重点实验室，呼吸药物研究实验室是国家食品药品监督管理局重点实验室，疾病蛋白质组学是省重点实验室。
汀溪是由造水、茂林、西源3条溪汇流而成。造水溪发源于汀溪镇造水村的铁峰山，海拔878米，河长10.35公里，比降2.75‰，流域面积23.4平方公里。汀溪河长17.34公里，比降2.85‰。茂林溪(五峰溪)发源于汪前村云顶山，海拔1175米，流域面积77.4平方公里，流经荇后、汪前、茂林，在墩后附近又汇入源于东山尖(海拔1110米)的东堤溪，于坂头村附近注入汀溪水库。1956年在汀溪村修建汀溪水库,现在的汀溪自大坝下游流经汀溪镇的上埔、隘头，在坤泽洋汇入西源溪，再流至草仔市汇入西溪。
痔疮（Hemorrhoids），或者称痔，是临床上一种最常见的肛门疾病。根据发生部位的不同，痔可分为内痔、外痔和混合痔。内痔的常见临床症状是间歇性便后出鲜血。部分患者可伴发排便困难。当内痔合并发生血栓、嵌顿、感染时则出现疼痛。外痔发生于肛门外部，入厕时有痛感，有时伴瘙痒。常见的外痔主要为结缔组织外痔（皮垂、皮赘）和炎性外痔。
莆田第十七中学创建于1979年，校园占地面积22000平方米，校舍建筑面积9020平方米，现有27个教学班，学校教学设备较为完善，配有图书馆、阅览室、多媒体教室、电脑室、音乐室、美术室、实验室、语音室。
阿拉善沙漠(Ala Shan Desert )是统称阿拉善盟境内三大沙漠即巴丹吉林沙漠、腾格里沙漠和乌兰布和沙漠，是戈壁大沙漠最南部分，位于中国中北部的银额盆地底部。包括内蒙古的西部和甘肃省的北部。东倚贺兰山，南接祁连山，西达黑河，北部有结构洼地与外蒙为界。占地约8万平方公里。
