何为波兰式?何为逆波兰式?
如何与表达式求值联系起来?
波兰式、逆波兰式是数据结构和编译原理里面提到的知识点,我们平时的运算式都是这样的 <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/