逆波兰表示法

前缀表示法 （+ 3 4 ）

中缀表示法 （3 + 4）

后缀表示法 （3 4 + ）

影片：在 1991 年 Hewlett-Packard HP-32SII 上鍵入按鍵序列來計算八乘六

逆波兰表示法（英語：Reverse Polish notation，縮寫RPN，或逆波兰记法、逆卢卡西维茨记法），是一种由波兰数学家扬·卢卡西维茨于1920年引入的数学表达式形式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法、後序表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰结构由弗里德里希·L·鲍尔和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值，以利用堆栈结构减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·伦纳德·汉布林在1960年代中期扩充。

在1960和1970年代，逆波兰记法广泛地被用于台式计算器，因此也在普通公众（如工程、商业和金融等领域）中使用。

下面大部分是关于二元运算，一个一元运算使用逆波兰记法的例子是阶乘的记法。

解释

逆波兰记法中，操作符置于操作数的后面。例如表达“三加四”时，写作“3 4 + ”，而不是“3 + 4”。如果有多个操作符，操作符置于第二个操作数的后面，所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5 + ”：先3减去4，再加上5。使用逆波兰记法的一个好处是不需要使用括号。例如中缀记法中“3 - 4 * 5”与“（3 - 4）*5”不相同，但后缀记法中前者写做“3 4 5 * - ”，无歧义地表示“3 (4 5 *) -”；后者写做“3 4 - 5 * ”。

逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现，并且能很快求值。

注意：逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”；数字的数位写法也是常规顺序。

与中缀记法的转换

主条目：调度场算法

艾兹格·迪科斯彻引入了调度场算法，用于将中缀表达式转换为后缀形式。因其操作类似于火车編組場而得名。 大多数操作符优先级解析器(解析器用简单的查表操作即可实现，优先级表由开发者自己定制，在不同的应用场景中，开发者可自由改变操作符的优先级)能转换为处理后缀表达式，实际中，一般构造抽象语法树，树的后序遍历即为逆波兰记法。

逆波兰表达式求值

伪代码

• while 有输入
  • 读入下一个符号X
  • IF X是一个操作数
    • 入栈
  • ELSE IF X是一个操作符
    • 有一个先验的表格给出该操作符需要n个参数
    • IF堆栈中少于n个操作数
      • （错误） 用户没有输入足够的操作数
    • Else，n个操作数出栈
    • 计算操作符。
    • 将计算所得的值入栈
• IF栈内只有一个值
  • 这个值就是整个计算式的结果
• ELSE多于一个值
  • （错误） 用户输入了多余的操作数

例子

中缀表达式“5 + ((1 + 2) * 4) - 3”写作

5 1 2 + 4 * + 3 -

下表给出了该逆波兰表达式从左至右求值的过程，堆栈栏给出了中间值，用于跟踪算法。

输入	操作	堆栈	注释
5	入栈	5
1	入栈	5, 1
2	入栈	5, 1, 2
+	加法运算	5, 3	1, 2出栈，将结果3入栈
4	入栈	5, 3, 4
*	乘法运算	5, 12	3, 4出栈，将结果12入栈
+	加法运算	17	5, 12出栈，将结果17入栈
3	入栈	17, 3
-	减法运算	14	17, 3出栈，将结果14入栈

计算完成时，栈内只有一个操作数，这就是表达式的结果：14

C++程序实现

#include <iostream>
#include<queue>
#include<stack>
#define ERROR 0
#define OK 1

using namespace std;

typedef int Staus;
typedef double ElemType;

bool Get_ops(stack<ElemType>* st, ElemType* op1, ElemType* op2)
{
	if (st->size() < 2)
		return ERROR;
	*op1 = st->top();
	st->pop();
	*op2 = st->top();
	st->pop();

	return OK;
}

Staus Solve(stack<ElemType>* st, char oper)
{
	bool flag = 0;
	ElemType oper1, oper2;
	flag = Get_ops(st, &oper1, &oper2);
	if (flag)
	{
		switch (oper)
		{
		case('+'):st->push(oper2 + oper1); break;
		case('-'):st->push(oper2 - oper1); break;
		case('*'):st->push(oper2 * oper1); break;
		case('/'):if (!oper1)
		{
			cout << "Divide by 0！" << endl;
			return ERROR;
		}
				 else st->push(oper2 / oper1);
			break;
		case('^'):st->push(pow(oper2, oper1)); break;
		}
	}
	else return ERROR;

	return OK;
}

int main()
{
	stack<ElemType> suffix;
	char c;
	ElemType t;
	c = getchar();
	while (c != '#')
	{
		switch (c)
		{
		case(' '):break;
		case('+'):;
		case('-'):;
		case('*'):;
		case('/'):;
		case('^'):Solve(&suffix, c); break;
		default:ungetc(c, stdin);
			cin >> t;
			suffix.push(t);
		}
		c = getchar();
	}
	cout << suffix.top() << endl;
	return 0;
}

上述运算可以重写为如下运算链方法（用于HP的逆波兰计算器）：

1 2 + 4 * 5 + 3 -

实现

第一代实现了逆波兰架构的电子计算机是英国电气公司1963年交付使用的KDF9和美国的Burroughs B5000。Friden公司在它1963年推出的EC-130中，将逆波兰表达式引入了台式计算器市场。惠普1968年设计了9100A逆波兰计算器，首台手持式计算器HP-35也使用逆波兰表达式，惠普在HP-10A之前的所有手持计算器（包括科学计算，金融和可编程）中使用了逆波兰表达式，并在1980年代晚期的LCD显示计算器如HP-10C, HP-11C, HP-15C, HP-16C，等都是用了逆波兰表达式。

实际意义

• 当有操作符时就计算，因此，表达式并不是从右至左整体计算而是每次由中心向外计算一部分，这样在复杂运算中就很少导致操作符错误。
• 堆栈自动记录中间结果，这就是为什么逆波兰计算器能容易对任意复杂的表达式求值。与普通科学计算器不同，它对表达式的复杂性没有限制。
• 逆波兰表达式中不需要括号，用户只需按照表达式顺序求值，让堆栈自动记录中间结果；同样的，也不需要指定操作符的优先级。
• 逆波兰计算器中，没有“等号”键用于开始计算。
• 逆波兰计算器需要“确认”键用于区分两个相邻的操作数。
• 机器状态永远是一个堆栈状态，堆栈里是需要运算的操作数，栈内不会有操作符。
• 教育意义上，逆波兰计算器的使用者必须懂得要计算的表达式的含义。

目前逆波兰的实现有：

• 任何基于栈的程序语言：
  • Forth
  • Factor
  • PostScript语言。
• 线上的逆波兰计算器
• Windows下逆波兰计算器
• Windows XP下的Microsoft PowerToy calculator （页面存档备份，存于互联网档案馆）
• 手机逆波兰计算器 （页面存档备份，存于互联网档案馆）开源的JAVA计算器
• Palm PDA下的逆波兰计算器 （页面存档备份，存于互联网档案馆）
• Mac OS X计算器
• Mac OS X和iPhone下的逆波兰计算器 （页面存档备份，存于互联网档案馆）
• Unix下的计算程序dc
• 交互式JavaScript的逆波兰计算器：[2] （页面存档备份，存于互联网档案馆）和[3]
• Wikibooks:Ada Programming/Mathematical calculations (Ada语言中的逆波兰计算器)
• Emacs的lisp lib包: calc
• 基于GTK+的galculator （页面存档备份，存于互联网档案馆）
• 表达式转换[4] （页面存档备份，存于互联网档案馆）
• scratch

参见

• Forth
• PostScript
• HP计算器
• LIFO
• 栈机器（Stack machine）
• 波兰表示法
• 面向堆栈编程

参考

• RPN or DAL? A brief analysis of Reverse Polish Notation against Direct Algebraic Logic （页面存档备份，存于互联网档案馆） – By James Redin
• Postfix Notation Mini-Lecture （页面存档备份，存于互联网档案馆） – By Bob Brown
• Fith: An Alien Conlang With A LIFO Grammar – By Jeffrey Henning
• Good Ideas, Through the Looking Glass - By Nick Wurth