题解 | #逆波兰表达式求值#

题意整理

• 给定一个逆波兰表达式，表达式中仅包含加减乘除和数字。
• 求表达式的值。

方法一（栈）

1.解题思路

逆波兰表达式求值的过程总是先列出运算符前面两个数字，然后将这两个数字进行相应运算，得到一个新的数字，这个数又与后面的数进行相应运算，直到结束。

所以，可以先新建一个栈，当遇到数字时，直接压入栈中，遇到运算符时，先取出栈顶的两个数字，进行相应运算，再压回栈中。最后栈中剩下的那个元素即是表达式的值。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串一维数组 
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        //新建一个栈
        LinkedList<String> stack=new LinkedList<>();
        //遍历tokens数组
        for(String token:tokens){
            //如果是数字，直接压入栈中
            if(!token.equals("+")&&!token.equals("-")&&!token.equals("*")&&!token.equals("/")){
                stack.push(token);
            }
            else{
                //如果是加减乘除，均需要两次弹出栈顶元素，再进行相应计算
                int val1=Integer.parseInt(stack.pop());
                int val2=Integer.parseInt(stack.pop());
                //如果是加号，将两个弹出的数相加，再压入栈中
                if(token.equals("+")){
                    stack.push(String.valueOf(val2+val1));
                }
                //如果是减号，将两个弹出的数相减，再压入栈中
                else if(token.equals("-")){
                    stack.push(String.valueOf(val2-val1));
                }
                //如果是乘号，将两个弹出的数相乘，再压入栈中
                else if(token.equals("*")){
                    stack.push(String.valueOf(val2*val1));
                }
                //如果是除号，将两个弹出的数相除，再压入栈中
                else{
                    stack.push(String.valueOf(val2/val1));
                }
            }

        }
        return Integer.parseInt(stack.peek());
    }
}

3.复杂度分析

• 时间复杂度：需要遍历整个字符串数组，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：最坏情况下，总共有$(n+1)\mathrm{/}2(n+1)/2$个数压入栈中，所以至多需要额外大小为$(n+1)\mathrm{/}2(n+1)/2$的栈，所以空间复杂度为$O(n)O(n)$。

方法二（数组模拟栈）

1.解题思路

与方法一的思路差不多，不过可以考虑使用数组来模拟栈。

假设逆波兰表达式中总共有n个元素，则n必定是奇数，并且数字的个数恰好比运算符个数多1。因为起初只有1个数字时，每加一个运算符，必定会加1个数字，依次类推，数字恰好比运算符多1。所以数字个数有$(n+1)\mathrm{/}2(n+1)/2$个，运算符个数有$(n-1)\mathrm{/}2(n-1)/2$个。用栈模拟的过程中，每次遇到数字，直接压入栈中，栈的容量会加1，遇到运算符时，先弹出两个元素，做运算后再压入栈中，栈的容量会减1。最坏情况下，数字全在前面，运算符全在后面，栈的容量最多达到$(n+1)\mathrm{/}2(n+1)/2$。

我们初始化arr数组的容量为$(n+1)\mathrm{/}2(n+1)/2$。用一个变量index指向栈顶的位置，index为-1表示栈容量为0。当压栈时，index加1，再将元素赋给当前位置，弹栈时，index减1即可。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param tokens string字符串一维数组 
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        int n=tokens.length;
        //定义数组arr，用于模拟栈
        int[] arr=new int[(n+1)/2];
        //指向栈顶位置
        int index=-1;
        for(String token:tokens){
            //如果是数字，直接index加1，并将数字赋值到当前位置
            if(!token.equals("+")&&!token.equals("-")&&!token.equals("*")&&!token.equals("/")){
                arr[++index]=Integer.parseInt(token);
            }
            else{
                //如果是加号，index减1，并将当前位置数字加上后一位的数字
                if(token.equals("+")){
                    index--;
                    arr[index]+=arr[index+1];
                }
                //如果是减号，index减1，并将当前位置数字减去后一位的数字
                else if(token.equals("-")){
                    index--;
                    arr[index]-=arr[index+1];
                }
                //如果是乘号，index减1，并将当前位置数字乘以后一位的数字
                else if(token.equals("*")){
                    index--;
                    arr[index]*=arr[index+1];
                }
                //如果是除号，index减1，并将当前位置数字除以后一位的数字
                else{
                    index--;
                    arr[index]/=arr[index+1];
                }
            }

        }
        return arr[0];
    }
}

3.复杂度分析

• 时间复杂度：需要遍历整个字符串数组，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外大小为$(n+1)\mathrm{/}2(n+1)/2$的arr数组，所以空间复杂度为$O(n)O(n)$。