Skip to content

Latest commit

 

History

History
29 lines (17 loc) · 1.13 KB

计算逆波兰式的值.md

File metadata and controls

29 lines (17 loc) · 1.13 KB

计算逆波兰式的值(evaluate-reverse-polish-notation)

知识点:栈

题目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are+,-,*,/. Each operand may be an integer or another expression.

Some examples:

计算逆波兰式的值,给定式子中合法的操作符有+、-、*、/,操作数可能是整型或者另一个表达式,比如:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

解题思路

从头遍历元素,如果当前元素不是+、0、*、/之一,即为数字,则将该字符串转化为数字后入栈,如果当前元素时运算符,则从栈中弹出连续的两个元素作为操作数,然后结合当前元素(操作符)计算当前式子的结果,然后将结果再次入栈,直至遍历完成。

需要注意的一个细节是弹出的两个元素作为二元操作符两边时的顺序,举例: ["2", "1", "/", "3", "*"] 入栈后:[2,1] 出栈时op1=1,op2=2,所以结果应该是op2/op1而不是op1/op2.

代码

这里