逆波兰问题

Question

波波老师，关于逆波兰问题我只能想到当遍历到运算符时，连续取出栈中栈顶元素，可实现不了，没什么思路，望再指点一下 多谢

Answer 1

liuyubobobo 2020-02-10 02:33:22

我的建议是看一下这个问题：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

基于这个问题，研究一下别人的实现。我不确定你使用什么语言，以C++ 语言为例，可以看我的这个实现：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0150-Evaluate-Reverse-Polish-Notation/cpp-0150/main.cpp

整体逻辑很简单，就是对于数字，入栈；对于符号，取出两个数字，做运算，将结果入栈。

如果想不清楚这个逻辑是什么意思，我强烈建议你针对一个正确的程序，实际使用一个测试用例调试跟踪一下。跟踪的过程注意：栈中都存储了什么数据，每一步运算，栈中的数字发生了怎样的改变，取出了什么元素，做了怎样的运算，又压入了什么元素。

当然，这个问题其实是逆波兰表达式解析的一个简单版本，不涉及运算符的优先级，括号的嵌套等问题。更复杂的逆波兰表达式的求解，一般面试遇不到，同时深入进去，也进入到编译这个特定的领域，而非基础算法面试考察的范畴了。如果是对这些更进阶的内容感兴趣，已经不在这个课程的范畴了，可以在互联网上找更多资料自学一下，

加油！：）

• 提问者 慕容9054781 #1

  谢谢波波老师，这个问题已经解决了，连续取两次栈顶元素就好了，我可能是刚接触算法，好多简单的逻辑都没有，感觉算法好难啊！！