150. 逆波兰表达式求值

题目描述

给你一个字符串数组 tokens ,表示一个根据逆波兰式表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

解题思路

我们依次遍历数据,如果遇到数字我们就直接入栈,如果遇到运算符,我们就取出栈顶的元素两个,然后进行运算,这里要注意-和/这两个运算符,取栈顶元素的位置要是运算时候的顺序是相反的,最后的话我们只需要返回栈里唯一的元素就行了,就是我们最终的结果

代码


public int evalRPN(String[] tokens) {
        Map<String, Integer> map = new HashMap<>();
        map.put("+", 1);
        map.put("-", 1);
        map.put("*", 1);
        map.put("/", 1);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (stack.isEmpty()) {
                stack.push(Integer.parseInt(tokens[i]));
            } else if (map.containsKey(tokens[i])) {
                int one = stack.pop();
                int two = stack.pop();
                int sum;
                switch (tokens[i]) {
                    case "+":
                        sum = one + two;
                        stack.push(sum);
                        break;
                    case "-":
                        sum = two - one;
                        stack.push(sum);
                        break;
                    case "*":
                        sum = one * two;
                        stack.push(sum);
                        break;
                    case "/":
                        sum = two / one;
                        stack.push(sum);
                        break;
                }
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }

        return stack.pop();
    }