逆波兰表达式求值
原创
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
[https://leetcode-cn.com/problems/evaluate-reverse-polish-
notation/](https://links.jianshu.com/go?to=https%3A%2F%2Fleetcode-
cn.com%2Fproblems%2Fevaluate-reverse-polish-notation%2F)
示例1：
输入：tokens = "2","1","+","3","*"?developer/article/1911025/undefined 输出：9?developer/article/1911025/undefined 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例2：
输入：tokens = "4","13","5","/","+"?developer/article/1911025/undefined 输出：6?developer/article/1911025/undefined 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例3：
输入：tokens = "10","6","9","3","+","-11"," ","/"," ","17","+","5","+"?developer/article/1911025/undefined 输出：22?developer/article/1911025/undefined 解释：?developer/article/1911025/undefined 该算式转化为常见的中缀算术表达式为：?developer/article/1911025/undefined ((10 (6 / ((9 + 3) -11))) + 17) + 5?developer/article/1911025/undefined = ((10 (6 / (12 -11))) + 17) + 5?developer/article/1911025/undefined = ((10 (6 / -132)) + 17) + 5?developer/article/1911025/undefined = ((10 0) + 17) + 5?developer/article/1911025/undefined = (0 + 17) + 5?developer/article/1911025/undefined = 17 + 5?developer/article/1911025/undefined = 22
提示：
1 <= tokens.length <= 104?developer/article/1911025/undefined tokensi 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 -200, 200 内的整数
Java解法
思路：
逆波兰表示法就是为了让计算机方便计算使用的，本身就是通过用栈来存储操作数，遇到运算符进行弹出操作数运算再入栈，直到结束 注意踩坑，出栈时的操作数，先出的是被操作的，注意位置顺序
package sj.shimmer.algorithm.m4_2021;import java.util.Stack;/** * Created by SJ on 2021/4/12.
*/class D75 { public static void main(String[] args) {// System.out.println(evalRPN(new String[]{"2","1","+","3","*"})); System.out.println(evalRPN(new String[]{"4","13","5","/","+"})); } public static int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (String token : tokens) { Integer a = 0; Integer b = 0; switch (token) { case "+": b = stack.pop(); a = stack.pop(); stack.add(a + b); break; case "-": b = stack.pop(); a = stack.pop(); stack.add(a - b); break; case "*": b = stack.pop(); a = stack.pop(); stack.add(a * b); break; case "/": b = stack.pop(); a = stack.pop(); stack.add(a / b); break; default: stack.add(Integer.parseInt(token)); break; } } return stack.pop(); }}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。