题目
题目地址:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
根据逆波兰表示法
,求表达式的值。
有效的运算符包括+, -, *, /
。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例:
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
答案
package com.jarome.leetcode;
import java.util.Stack;
public class SolutionEvalRPN {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
// 根据题目,tokens里只能是整数或者运算符
String token = tokens[i];
if (isOperator(token)) {
// 做一个容错判断
if (stack.size() >= 2) {
// 第一次出栈获取的是第二个数
Integer num2 = stack.pop();
Integer num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
}
}
} else {
stack.push(Integer.valueOf(token));
}
}
int res = 0;
if (!stack.isEmpty()) {
res = stack.pop();
}
return res;
}
private boolean isOperator(String str) {
return "+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str);
}
public static void main(String[] args) {
String[] tokens = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
SolutionEvalRPN sr = new SolutionEvalRPN();
int i = sr.evalRPN(tokens);
System.out.println(i);
}
}