题目主要信息

给定一个逆波兰表达式，求表达式的值。

方法一：使用栈

具体方法

逆波兰表达式求值的过程可以借助栈来求解，在遍历数组的时候，判断当前是否是数字，如果是就压入栈中，不是说明遇到了运算符，从栈中弹出两个数字进行运算即可。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串一维数组 
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        // 栈
        Stack<Integer> stack = new Stack<Integer>();
        // 长度
        int n = tokens.length;
        // 遍历
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            // 说明是数字，则押入栈
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            }
            // 说明遇到运算符
            else {
                // 弹出两个元素
                int num2 = stack.pop();
                int 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;
                    default:
                }
            }
        }
        return stack.pop();
    }
    // 用于判断token是数字还是运算符
    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中$nn$是数组 的长度。
• 空间复杂度：$O(n)O(n)$，其中$nn$ 是数组 。使用栈存储计算过程中的数，栈内元素个数不会超过逆波兰表达式的长度。

方法二：数组模拟栈

具体方法

栈可以使用数组来模拟。遇到符号前运算的都是其前两个数字，可以使用数组来模拟栈，只需要一个指针指向数字结尾即可。

遇到数字字符串，将其转换成int数字后加入数组，同时指针后移，遇到运算符号就指针前移两位获取最近的两个数字，然后将其运算后的结果再存入数组。运算结束后，根据指针所指的第一个数字就是结果，与上述栈原理一致，甚至也可以参考方法一的图示。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串一维数组 
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        // write code here
        // 求出数组的长度
        int len = tokens.length;
        // 数组模拟栈 
        int[] stack = new int[(len + 1) / 2];
        int index = -1;
        for (int i = 0; i < len; i++) {
            String token = tokens[i];
            // 判断token 是运算符还是数字
            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];
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，一次遍历。
• 空间复杂度：$O(n)O(n)$，临时数组长度