题意整理

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

方法一(栈)

1.解题思路

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

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

图解展示: alt

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)/2(n+1)/2个数压入栈中,所以至多需要额外大小为(n+1)/2(n+1)/2的栈,所以空间复杂度为O(n)O(n)

方法二(数组模拟栈)

1.解题思路

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

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

我们初始化arr数组的容量为(n+1)/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)/2(n+1)/2的arr数组,所以空间复杂度为O(n)O(n)