波兰表示法

✍ dations ◷ 2025-04-12 09:35:53 #波兰表示法

波兰表示法(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年代演变成下表的记法。

相关

  • Hh/孟买血型系统Hh血型系统或Hh抗原系统,又称孟买血型系统(英语:Hh/Bombay antigen system),是根据红血球表面是否存在H抗原而对血液分型的人类血型系统。Hh血型系统是人类最重要的血型系统——A
  • 清代机器局遗构清代机器局遗构,位在台北市塔城街两侧,为1885年建立的机器局遗迹,在2006年因台北捷运松山线施工整地时被发现,包含石砌墙、清代石板路和漆器局四进衙门的遗构,于2009年登录为台北
  • 培龙氏海蝶螺培龙氏海蝶螺(学名:)是一个海蝶螺科海蝶螺属的海螺物种,属于一种全浮游(英语:holoplankton)的海洋腹足纲软体动物,也是海蝶螺属的模式种。本物种有纪录最长的螺壳有11 mm。本物种见
  • 爨荣宗爨荣宗,唐朝爨氏豪酋,爨乾福的儿子。他的曾祖父是唐高祖的昆州(今云南省昆明市)刺史爨宏达,唐睿宗垂拱四年(688年),其父爨乾福担任昆州刺史。爨荣宗被唐朝封为左监门卫大将军、郎州(
  • 世界在跳跃/灼热“世界在跳跃/灼热”(日语:世界は踊る/灼熱)是BREAKERZ的第2张单曲。2008年9月24日由ZAIN RECORDS发售。DAIGO  – AKIHIDE  – SHINPEI1.SUMMER PARTY/LAST EMOTION  – 2.
  • 美国钢铁工人联合会美国钢铁工人联合会(United Steel, Paper and Forestry, Rubber, Manufacturing, Energy, Allied Industrial and Service Workers International Union,简称为United Steelwo
  • 爱河 (鸭绿江)爱河,原作叆河,唐代称乌骨江,位于中华人民共和国辽宁省东部,是鸭绿江右岸支流,发源于辽宁省宽甸满族自治县双山子镇四平街村北千山山脉的摩天岭(又称高丽盘道岭),上游段又称牛牲河,向
  • 大卫·海曼大卫·乔纳森·海曼(英语:David Jonathan Heyman,1961年7月26日-) 是一名英格兰企业家和电影监制,为英国制片公司盛日影业的创始人。1999年他取得《哈利波特》系列小说的电影改编权,先后将该系列小说拍摄成八部电影,取得全球性成功。2013年他与墨西哥导演Alfonso Cuarón联合制片的3D科幻片《地心引力》获得奥斯卡最佳影片提名,并获得最佳导演等7个奖项成为第86届奥斯卡金像奖的大赢家。大卫·海曼生于伦敦。父亲John Heyman是制片人,有德国犹太人血统。母亲Norma
  • 奥西耶克-巴拉尼亚县奥西耶克-巴拉尼亚县(Osječko-baranjska županija),或译欧谢丘可·巴拉尼斯卡县,是克罗地亚的一个县,位于该国东北部。北邻匈牙利,南为塞尔维亚。面积4,155平方公里,人口330,506(2001年)。首府奥西耶克。是巴兰尼亚地区的一部分。下分七市、三十五镇。县议会有51席。
  • 钱传范钱传范(1930年11月21日-2022年2月7日),女,浙江嘉兴人,中国农药及农用化学制剂专家,曾任北京农业大学教授、博士生导师。1930年11月21日生于沈阳。她的父亲早年在商务印书馆工作。1948年高中毕业后就读于上海沪江大学化学系,1949年转入清华大学农化系,1950年院校调整转入北京农业大学,1953年毕业后留校任教。1956年至1957年,在北京俄语学院学习1年后赴苏联列宁农业科学院植物保护研究所学习,1961年获副博士学位,返校任助教。曾任农药教研组主任、农药残留研究室主任,并兼任农化系党