有效的算符包括 +
、-
、*
、/
。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
[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 内的整数
思路:
逆波兰表示法就是为了让计算机方便计算使用的,本身就是通过用栈来存储操作数,遇到运算符进行弹出操作数运算再入栈,直到结束 注意踩坑,出栈时的操作数,先出的是被操作的,注意位置顺序
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 删除。