题目
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
示例：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
代码
public class DayCode { public static void main(String[] args) { String[] s = {"3", "11", "5", "+", "-"}; int ans = new DayCode().evalRPN(s); System.out.println(ans); }
/** * 链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/ * 时间复杂度 O(n) * 空间复杂度 O(n) * @param tokens * @return */ public int evalRPN(String[] tokens) { int ans = 0; Deque<Integer> stack = new LinkedList<>(); for (String token : tokens) { int temp = 0; int num1 = 0; int num2 = 0; switch (token) { case "+": temp = stack.removeLast() + stack.removeLast(); stack.addLast(temp); break; case "-": num1 = stack.removeLast(); num2 = stack.removeLast(); stack.addLast(num2 - num1); break; case "*": temp = stack.removeLast() * stack.removeLast(); stack.addLast(temp); break; case "/": num1 = stack.removeLast(); num2 = stack.removeLast(); stack.addLast(num2 / num1); break; default: stack.addLast(Integer.parseInt(token)); break; } } if (!stack.isEmpty()) { ans = stack.pop(); } return ans; }}
复制代码
总结
评论