波兰表示法

波兰表示法（，或波兰记法）是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析。波兰记法是波兰数学家扬·武卡谢维奇于1920年代引入的，用于简化命题逻辑。

扬·武卡谢维奇本人提到：from Nicod's Axiom and Generalizing Deduction, page 180. 原文用波兰语写在一个平版报告上。

阿隆佐·邱奇在他的经典著作《数理逻辑》中提出该表达方法是一种值得被关注的记法系统，甚至将它与阿弗烈·諾夫·懷海德和伯特兰·罗素在《数学原理》中的逻辑表达式相提并论。 - p.38: "Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. ..."

算术形式
表达“三加四”时，前缀记法写作“”，而不是“3 + 4”。在复杂的表达式中，操作符仍然在操作数的前面，但操作数可能是包含操作符的平凡表达式。
例如，中缀運算式 ，在前缀表达式中可以表示為：
 *(− 5 6) 7
或省略括号：


由于简单的算术运算符都是二元的，该前缀表达式无需括号，且表述是无歧义的。在前面的例子里，中缀形式的括号是必需的，如果将括号移动到：

即：

则会改变整个表达式的值。而其正确的前缀形式是：

减法运算要等它的两个操作数（5；6和7的乘积）都完成时才会处理。在任何表示法中，最里面的表达式最先运算，而在波兰表达式中，决定“最里面”的是顺序而不是括号。

简单算术的前缀表达式主要是用于学术研究方面。与逆波兰表示法不同，前缀表达式基本没有在商业计算器中使用过，但是其体系经常在编译器构造的概念教学中首先使用。

计算机编程
LISP的S-表达式中广泛地使用了前缀记法，S-表达式中使用了括号是因为它的算术操作符有可变的元数（arity）。逆波兰表示法在许多基于堆栈的程序语言（如PostScript）中使用，以及是一些计算器（特别是惠普）的运算原理。

假定只有二元运算时，操作数的个数必然为操作符的个数加一，否则表达式就无意义。这样在计算更复杂，更长的表达式时，可以简单地忽略某些错误表达式，因此在使用前缀记法时必须小心仔细检查其表达意义。

运算顺序
前缀表达式的运算顺序很容易检测。需注意的是，当运算时，操作符是作用在第一个操作数上，特别是需注意不满足交换律的运算，如除法、减法。例如，下列式子：

  / 10 5 = 2  (前缀记法)

表示10/5，结果是2，而不是½。

基于堆栈的操作符由于其本身的特性，无需括号也很容易区分运算的顺序，因此大量使用波兰记法。运算波兰表达式时，无需记住运算的层次，只需要直接寻找第一个运算的操作符。以二元运算为例，从左至右读入表达式，遇到一个操作符后跟随两个操作数时，则计算之，然后将结果作为操作数替换这个操作符和两个操作数；重复此步骤，直至所有操作符处理完毕。因为在正确的前缀表达式中，操作数必然比操作符多一个，所以必然能找到一个操作符符合运算条件；而替换时，两个操作数和一个操作符替换为一个操作数，所以减少了各一个操作符和操作数，仍然可以迭代运算直至计算整个式子。多元运算也类似，遇到足够的操作数即产生运算，迭代直至完成。迭代结束的条件由表达式的正确性来保证。下面是一个例子，演示了每一步的运算顺序：

  - * / 15 - 7 + 1 1 3 + 2 + 1 1 =
  - * / 15 - 7   2   3 + 2 + 1 1 =
  - * / 15     5     3 + 2 + 1 1 =
  - *        3       3 + 2 + 1 1 =
  -          9         + 2 + 1 1 =
  -          9         + 2   2   =
  -          9         4         =
                 5
逻辑运算的波兰记法
下面的表格显示了命题逻辑的扬·武卡谢维奇记法，波兰记法中的某些字母代表特定的波兰语单词。普遍记法在1970和1980年代演变成下表的记法。
概念普遍记法波兰记法逻辑非φNφ逻辑与φψKφψ逻辑或φψAφψ逻辑条件φψCφψ逻辑双条件φψEφψ谢费尔竖线Dφψ可能性φMφ必然性φLφ全称量化φΠφ存在量化φΣφ

 注釋 

参见
Lisp
逆波兰表示法
 Forth
 PostScript
 HP计算器
 LIFO
 栈机器（Stack machine）

延伸阅读

Łukasiewicz, Jan, "Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls", Comptes rendus des séances de la Société des Sciences et des Lettres de Varsovie, 23:51-77 (1930). Translated by H. Weber as "Philosophical Remarks on Many-Valued Systems of Propositional Logics", in Storrs McCall, Polish Logic 1920-1939, Clarendon Press: Oxford (1967).

Category:數學表示法
Category:波兰发明
Category:波兰科技
Category:运算符 (编程)
Category:逻辑表达式