一文搞懂波兰表达式

伴随2024-04-052024-04-05

1.什么式波兰表达式

波兰表达式（又称逆波兰表达式）是一种数学和逻辑表达式的表示方法。在波兰表达式中，操作符放在它们所操作的数之前，而不是在它们之间，这样可以消除括号的需求。波兰表达式通过一种前缀或后缀的方式来表示，分别称为前缀波兰表达式和后缀波兰表达式。

2.为什么会有这种表达式

在计算机中，要本着能简化就简化的原则来设计，对于一个正常的数学运算表达式，除了有加减乘除之外，还有一些括号来标识运算的优先级，那么对于计算机而言，能不能不写括号就能正常运算这个表达式呢，那么波兰表达式就产生了。

3.直接上🌰

下面的表达式就是一个比较简单的例子，我们也叫它中缀表达式

a + b * (c - d) + e/f

有了中缀表达式，那肯定也有前缀表达式和后缀表达式

中缀表达式转换

首先根据中缀表达式构造一个二叉树

       +                                      +    
      / \                                    / \   
     a   +                                  +   /  
        / \                                / \ / \ 
       *   /              或者             a  * e  f
      / \ / \                               / \    
     b  - e  f                             b   -   
       / \                                    / \  
      c   d                                  c   d

前缀表达式 = 前序遍历（波兰式）
中缀表达式 = 中序遍历
后缀表达式 = 后序遍历（逆波兰式）

所以根据上面的二叉树我们可以知道
前缀表达式 = + a + * b - c d / e f 或 + + a * b - c d / e f
后缀表达式 = a b c d - * e f / + + 或 a b c d - * + e f / +

通过树基础知识我们知道，树的三种遍历方式中，如果告诉我们任意一种遍历，我们式无法确切的推出另外两种遍历方式的，也就是说我们无法确定这一棵树的形态，所以波兰式也是一样的，一个表达式可能对应多个波兰式