栈evaluate-reverse-polish-notation-leetcode练习题-蒲公英云

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

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
/**
 * 根据逆波兰表示法，求表达式的值。
 * <p>
 * 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
 * <p>
 * 说明：
 * <p>
 * 整数除法只保留整数部分。
 * 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 * <p>
 * 示例 1：
 * <p>
 * 输入: ["2", "1", "+", "3", "*"]
 * 输出: 9
 * 解释: ((2 + 1) * 3) = 9
 * <p>
 * 示例 2：
 * <p>
 * 输入: ["4", "13", "5", "/", "+"]
 * 输出: 6
 * 解释: (4 + (13 / 5)) = 6
 * <p>
 * 示例 3：
 * <p>
 * 输入: ["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
 * <p>
 * 来源：力扣（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));
    }
}