栈evaluate-reverse-polish-notation-leetcode练习题

╰半夏微凉° 2023-07-23 03:45 35阅读 0赞

import java.util.HashSet;
 import java.util.Set;
 import java.util.Stack;
 
 /**
 * 根据逆波兰表示法，求表达式的值。
 * 
 * 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
 * 
 * 说明：
 * 
 * 整数除法只保留整数部分。
 * 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 * 
 * 示例 1：
 * 
 * 输入: ["2", "1", "+", "3", "*"]
 * 输出: 9
 * 解释: ((2 + 1) * 3) = 9
 * 
 * 示例 2：
 * 
 * 输入: ["4", "13", "5", "/", "+"]
 * 输出: 6
 * 解释: (4 + (13 / 5)) = 6
 * 
 * 示例 3：
 * 
 * 输入: ["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
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
 public class Solution {
 
 private static Set<String> OPERATERS = new HashSet<>();
 
 static {
 OPERATERS.add("+");
 OPERATERS.add("-");
 OPERATERS.add("*");
 OPERATERS.add("/");
 }
 
 public int evalRPN(String[] tokens) {
 Stack<Integer> datas = new Stack();
 for (String character : tokens) {
 if (isNumber(character)) {
 datas.push(Integer.parseInt(character));
 } else {
 if (datas.size() >= 2) {
 // 取出两个值和现在的符号处理后将新的值放入栈中
 int num1 = datas.pop();
 int num2 = datas.pop();
 int temp = 0;
 if ("+".equals(character)) {
 temp = num2 + num1;
 } else if ("-".equals(character)) {
 temp = num2 - num1;
 } else if ("*".equals(character)) {
 temp = num2 * num1;
 } else {
 temp = num2 / num1;
 }
 datas.push(temp);
 } else {
 throw new IllegalArgumentException();
 }
 }
 }
 return datas.pop();
 }
 
 private boolean isNumber(String token) {
 if (OPERATERS.contains(token)) {
 return false;
 }
 return true;
 }
 
 public static void main(String[] args) {
 Solution solution = new Solution();
 String[] tokens = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", 
 "17", "+", "5", "+"};
 System.out.println(solution.evalRPN(tokens));
 }
 }

核心思想：

每次取两个数字和符号处理后再次将数字压栈