波兰式

更新部分

2022-08-10 万万没有想到居然在数据结构学习中，遇到了编译原理的内容，故翻新。

表达式：

算数表达式一般由操作数，运算符和界限符（括号）构成。

平时我们习惯将表达式写成 (1 + 2) * (3 + 4)，加减乘除等运算符写在中间，因此称呼为中缀表达式。

中缀表达式的括号是不能省略的，于是波兰数学家考虑“是否能不用界限符（去掉括号）也能无歧义的表达运算顺序”

于是设计后，分为两种表达式：

• 前缀/波兰表达式：写法为 $(* (+ 1 2) (+ 3 4))$，将运算符写在前面

• 后缀/逆波兰表达式：写法为 $((1 2 +) (3 4 +) *)$，将运算符写在后面，因而也称为后缀表达式。

中缀转后缀表达式方法

运算顺序不唯一时，对应的后缀表达式也不唯一。

题目：**逆波兰式 $ab+c+ d*e-$ 所表达的表达式为？

如何转换逆波兰式为普通式？：**

按照栈的方式进行

上题：

$ab+ =>a + b$ (作为一个整体)

$[a + b] c+ =>[(a + b + c)]$ (继续作为整体)

$[(a + b + c)]d*e- =>(a+b+c) * d =>(a+b + c) * d - e$

中缀表达式转逆波兰式(反过来即可)