波兰表示法

✍ dations ◷ 2025-11-04 00:06:11 #波兰表示法

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

扬·武卡谢维奇本人提到:

阿隆佐·邱奇在他的经典著作《数理逻辑》中提出该表达方法是一种值得被关注的记法系统,甚至将它与阿弗烈·诺夫·怀海德和伯特兰·罗素在《数学原理》中的逻辑表达式相提并论。


表达“三加四”时,前缀记法写作“+ 3 4 ”,而不是“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年代演变成下表的记法。

相关

  • 古元古代古元古代(英语:Paleoproterozoic,符号PP)是地质时代中的一个代,开始于同位素年龄25亿年前(Ma),结束于16亿年前(Ma)。而古元古代期间蓝藻、细菌非常繁盛。古元古代属于前寒武纪元古宙,上
  • 自体输血自体输血,也即将病人自己的血液重新输给自己,其优点在于不会出现免疫反应,也无需担心感染新的疾病。自体输血的形式主要有:
  • 2015年菲律宾APEC峰会2015年菲律宾APEC峰会,全称亚太经合组织第二十三次领导人非正式会议(英语:THE 23RD APEC ECONOMIC LEADERS' MEETING)。这是菲律宾第二次主办APEC峰会,第一次是在1996年。此年领
  • eval在一些程序语言中,eval 是一个把字符串当作表达式执行而返回一个结果的函数;在另一些之中,它执行多行的代码就好像它们被包括在其中,而不是包括 eval 的这一行。eval 的输入不一
  • 吉村佣吉村佣,艺名:吉村よう(本名、旧艺名:吉村 佣,1954年7月10日-1991年11月27日),日本男演员、配音员。从属于剧团青年座。京都府出身。吉村从出道以来,大多参加海外电影帮配角进行日语配
  • talkSPORTtalkSPORT是英国的一家体育广播电台,也是是英超联赛全球官方音频合作伙伴,目前为Wireless Group(新闻集团控股,旧称UTV Media)旗下电台。1995年2月14日,talkSPORT的前身“Talk Rad
  • 宇都宫货物总站宇都宫货物总站(日语:宇都宮貨物ターミナル駅/うつのみやかもつターミナルえき  */?)是一由日本货物铁道(JR货物)所经营的货运专用铁路车站,位于日本栃木县河内郡上三川町大字多
  • 炮决炮决是一种处决方法,受刑者通常被绑在加农炮口,然后被炮弹打死。乔治·卡特·斯滕特(George Carter Stent)描述的过程如下:囚犯通常被绑在炮上,被炮口抵着后腰的上边。开炮后,只见他的头直冲上天飞了四五十英尺;上肢飞向天上,落到四处,也许有一百码那么远;下肢落在炮口下;躯干全被轰碎,看不出一点痕迹。据传莫卧儿帝国早在16世纪就开始使用炮决,直到20世纪。16世纪和17世纪,最早在1509年,葡萄牙殖民者跨越他们的帝国,从锡兰(今斯里兰卡)到莫桑比克再到巴西都使用了这种处决方式。莫卧儿人在整个1
  • 何熙何熙(1世纪-110年),字孟孙,东汉陈国阳夏县(今河南省太康县)人。何熙少有大志。永元年间,举孝廉担任谒者。身高八尺五寸,体貌魁梧,表情威严,在殿中朝拜唱导行礼,声音振动左右。汉和帝觉得他很伟岸,擢升他为御史中丞,历任司隶校尉、大司农。汉安帝永初三年(109年),汉人韩琮向南匈奴万氏尸逐鞮单于宣称:关东大水,人民饥饿死尽,可乘机攻掠。南单于信他的话,十月南单于起兵与乌丸反汉,于美稷(今内蒙古伊克昭盟准格尔旗西北)率兵围攻汉中郎将耿种。十一月,汉派行车骑将军何熙、中郎将庞雄率军二万,合辽东郡太守耿夔所率鲜
  • 海因茨·弗斯滕多夫海因茨·弗斯滕多夫(德语:Heinz Förstendorf,1907年12月28日-1988年9月2日),德国男子曲棍球运动员,所属俱乐部是莱比锡SC。他曾代表德国参加1928年夏季奥林匹克运动会曲棍球比赛,获得一枚铜牌。