天天看点

逆波兰式与表达式求值

何为波兰式?何为逆波兰式?

如何与表达式求值联系起来?

波兰式、逆波兰式是数据结构和编译原理里面提到的知识点,我们平时的运算式都是这样的 <code>2 + 3 * (5 - 1)-10(中缀表达式),这样表达式易于阅读和计算,但是对于计算机这样就有点懵逼了。</code>

前缀表达式: 比如<code>2 + 3 * (5 - 1)</code>这个表达式的前缀表达式为<code>+ 2 * 3 - 5 1</code>来表示  波兰表达式

中缀序表达式:比如 2 + 3 * (5 - 1)-10

后缀表达式:比如<code>2 + 3 * (5 - 1)</code>用逆波兰式来表示则是:<code>2 3 5 1 - * +  逆波兰表达式</code>

求表达式值:

  

问题可以转换为遍历表达式用一个堆来存数字,当遇见操作符的时候,弹出两个数字执行相应的运算,再压入堆里面,最后返回出来的就是运算表达式的结果。

逆波兰式与表达式求值

参考:http://www.programcreek.com/2012/12/leetcode-evaluate-reverse-polish-notation/