摘要:栈法复杂度时间空间思路逆波兰表达式的计算十分方便,对于运算符,其运算的两个数就是这个运算符前面的两个数。注意对于减法,先弹出的是减号后面的数。
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
时间 O(N) 空间 O(N)
思路逆波兰表达式的计算十分方便,对于运算符,其运算的两个数就是这个运算符前面的两个数。所以我们只要用一个栈,每次遇到数字就压入栈内,每次遇到运算符就弹出两个数,计算后再压回栈内,最后栈内剩下的那个数就是计算结果了。
注意对于减法,先弹出的是减号后面的数。对于除法,先弹出的是除号后面的数。
代码public class Solution { public int evalRPN(String[] tokens) { Stackstk = new Stack (); for(String token : tokens){ switch(token){ case "+": stk.push(stk.pop() + stk.pop()); break; case "-": stk.push(-stk.pop() + stk.pop()); break; case "/": int num1 = stk.pop(); int num2 = stk.pop(); stk.push(num2 / num1); break; case "*": stk.push(stk.pop() * stk.pop()); break; default: stk.push(Integer.parseInt(token)); } } return stk.pop(); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64626.html
摘要:题目根据逆波兰表示法,求表达式的值。给定逆波兰表达式总是有效的。逆波兰表达式又叫做后缀表达式。解题思路可以看出逆波兰表达式中的每一个运算符属于该运算符前的两个数字间的运算。如如波兰表达式则加号前两个数字为。 题目: 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 Evaluate the value of...
摘要:小鹿题目根据逆波兰表示法,求表达式的值。给定逆波兰表达式总是有效的。算法思路仔细观察上述的逆波兰表达式,可以发现一个规律就是每遇到一个操作符,就将操作符前的两个操作数进行运算,将结果保存到原位置。 Time:2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 题目:Evaluate ...
摘要:我们一般看到的数学表达式就是中缀表达式,也就是将符号放在两个数字之间。后缀表达式也就是将运算符放在相应数字的后面。后缀表达式相当于树中的后序遍历。通过获得对应位置的操作符。如果对应的还是操作符,则继续递归往前计算。 题目要求 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid...
Problem Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two inte...
阅读 3684·2021-11-25 09:43
阅读 2600·2021-11-18 13:11
阅读 2193·2019-08-30 15:55
阅读 3271·2019-08-26 11:58
阅读 2823·2019-08-26 10:47
阅读 2230·2019-08-26 10:20
阅读 1270·2019-08-23 17:59
阅读 2999·2019-08-23 15:54