150. 逆波兰表达式求值

leetcode链接：
https://leetcode.cn/problems/evaluate-reverse-polish-notation/

题目分析

把字符串按顺序加入到栈中，遇到特殊字符的时候，按照顺序弹出栈，进行相关的算术操作。

注：注意弹出栈的顺序导致的数值运算是 减数 还是 被减数 （除数 / 被除数）

方案一

class Solution {
    public int evalRPN(String[] tokens) {

        Deque deque = new LinkedList<Integer>();
        int flag = 0;

        for (String s: tokens) {
            if ("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)) {
                Integer numSecond = (Integer) deque.pop(); // 此处注意弹出栈的顺序
                Integer numFirst = (Integer) deque.pop();
                switch (s) {
                    case "+":
                        deque.push(numFirst + numSecond);
                        break;
                    case "-":
                        deque.push(numFirst - numSecond);
                        break;
                    case "*":
                        deque.push(numFirst * numSecond);
                        break;
                    case "/":
                        deque.push(numFirst / numSecond);
                        break;
                }
            } else {
                deque.push(Integer.valueOf(s));
            }
        }
        return (int) deque.pop();
    }
}

结果

解答成功:
执行耗时:6 ms,击败了54.78% 的Java用户
内存消耗:41.6 MB,击败了59.84% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

官方题解

https://leetcode.cn/problems/evaluate-reverse-polish-notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/

官方题解中的 方法一：栈 其与上面编写的方案一相似，此处不再介绍。

下面的官方题解中的 方法二：
此方法本质：使用 数组模拟栈

class Solution {
    public int evalRPN(String[] tokens) {
        int n = tokens.length;
        int[] stack = new int[(n + 1) / 2];
        int index = -1;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            switch (token) {
                case "+":
                    index--;
                    stack[index] += stack[index + 1];
                    break;
                case "-":
                    index--;
                    stack[index] -= stack[index + 1];
                    break;
                case "*":
                    index--;
                    stack[index] *= stack[index + 1];
                    break;
                case "/":
                    index--;
                    stack[index] /= stack[index + 1];
                    break;
                default:
                    index++;
                    stack[index] = Integer.parseInt(token);
            }
        }
        return stack[index];
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。