五分钟小知识之什么是前缀表达式

深藏阁楼爱情的钟 2022-01-26 04:03 339阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

--------------------

**算术表达式**是最常用的表达式，又称为数值表达式。它是通过算术运算符来进行运算的数学公式。

表达式计算 (expression evaluation) 是程序设计语言编译中的一个最基本问题，也是早期计算机语言研究的一项重要成果，它使得高级语言程序员可以使用与数学形式相一致的方式书写表达式。

一般我们接触比较熟悉的是 **中缀表达式** 。

**中缀表达式**是常见的运算表达式，如 ( 3 + 4 ) × 5 - 6 。中缀表达式在我们日常生活中应用最为广泛，也最符合人的计算思维。

今天来科普一下比较不常用的前缀表达式。

### 前缀表达式 ###

**前缀表达式又称波兰式**，前缀表达式的运算符位于操作数之前。[LeetCode 第 150 号问题就用到了波兰式的概念，具体可以点击了解一下。][LeetCode _ 150]

例如：中缀表达式 ( 2 + 3 ) × 4 - 5，采用前缀表达式为：- × + 2 3 4 5

**前缀表达式运算：**

•对前缀表达式进行从右至左依次扫描•当遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈•重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

例如前缀表达式 : - × + 2 3 4 5

•从右至左扫描，将5、4、3、2压入堆栈•遇到 + 运算符，因此弹出 2 和 3（ 2 为栈顶元素，3 为次顶元素，注意与后缀表达式做比较），计算出 2 + 3 的值，得 5，再将 5 入栈;•接下来是 × 运算符，因此弹出 5 和 4 ，计算出 5 × 4 = 20，将 20 入栈•最后是 - 运算符，计算出 20 - 5 的值，即 15，由此得出最终计算结果

**中缀表达式转为前缀表达式：** 转换步骤如下:

•（1）初始化两个栈:运算符栈 s1，储存中间结果的栈 s2•（2）从右至左扫描中缀表达式•（3）遇到操作数时，将其压入 s2•（4）遇到运算符时，比较其与 s1 栈顶运算符的优先级

•a：如果 s1 为空，或栈顶运算符为右括号 “ ) ”，则直接将此运算符入栈 •b：否则，若优先级比栈顶运算符的较高或相等，也将运算符压入 s1 •c：否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 ( 4 - 1 ) 与 s1 中新的栈顶运算符相比

•（5）遇到括号时

•a：如果是右括号“)”，则直接压入 s1 •b：如果是左括号“(”，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到右括号为止，此时将这一对括号丢弃

••（6）重复步骤（2）至（5），直到表达式的最左边••（7）将 s1 中剩余的运算符依次弹出并压入 s2••（8）依次弹出 s2 中的元素并输出，结果即为中缀表达式对应的前缀表达式。

例如：中缀表达式 1 + (( 2 + 3 ) × 4) - 5 转为前缀表达式具体过程，如下图

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

**END**

![640?wx\_fmt=png][640_wx_fmt_png]

**推荐阅读**：

*  [盖尔-沙普利算法告诉你，你的对象在哪里？][-]

*  [面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

*  [如何有效的写算法题][Link 1]

*  [几道 BAT 算法面试中经常问的「字符串」问题][BAT]

*  [链表算法面试问题？看我就够了！][Link 2]

![640?wx\_fmt=png][640_wx_fmt_png]

欢迎长按下图关注公众号**五分钟学算法**，一起看动画学算法。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

[640_wx_fmt_jpeg]: /images/20220126/bb17ac7d525b462b8b4e9f493a97a2a9.png
[LeetCode _ 150]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247483834&idx=1&sn=27cbff99f10dfcdb56cb37c237d7f2bb&chksm=fa0e6e3bcd79e72dc430bf81aed9dde9bd01634239dcf7820d6befa881efd323d9d58d76d90d&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220126/26302c679e94409ebbf877e70c7302c1.png
[640_wx_fmt_png]: /images/20220126/8030d2dff9034557aa2c65d17257bb2e.png
[-]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485359&idx=1&sn=c80013d51595c46a93abf0c58af7d347&chksm=fa0e682ecd79e138acfcad3357051f27a86c440031c9017be0c7c05e61963c4c5f72045b10eb&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485214&idx=1&sn=00de6e810caa7e261b8f2e19c3acd9cd&chksm=fa0e689fcd79e189282babbe3a688158b505e7b907971eede501addac9e0bec1e9d1c77ffb78&scene=21#wechat_redirect
[BAT]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485091&idx=1&sn=1503058d7c1313552f84073b495c5e76&chksm=fa0e6922cd79e034471194c636e89aa124941a13dabdf4d6197669f51d146f27098b124e5dd8&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 2]: /images/20220126/6d3fa072e26145ef84e8d8714b8af419.png