剑指offer36：后缀表达式

剑指offer36：后缀表达式

题目：
后缀表达式是一种算数表达式，它的 *** 作符在 *** 作数的后面。输入一个用字符串数组表示的后缀表达式，请输出该后缀表达式的计算结果。假设输入的一定是有效的后缀表达式。例如，后缀表达式[“2”,“1”,“3”,"","+"]对应的算术表达式是"2+13"，因此输出它的计算结果。
分析：
简单回顾下Java中stack的常用 *** 作：

序号函数函数功能1push(e)元素e入栈2pop位于栈顶的元素出栈，并返回该元素3peek返回位于栈顶的元素，该元素不出栈

由于后缀表达式 *** 作符都在末尾，从左开始扫描字符串数组，如果是数字就把它压入栈中，等到扫描到运算符就d栈两个数字同运算符进行运算，运算的结果再压入栈中，后面步骤同理。

步骤输入 *** 作栈注释12入栈[2]21入栈[2,1]33入栈[2,1,3]4*乘法运算[2,3]3,1出栈，结果3入栈5+加法运算[5]3,2出栈，结果5入栈

该算法时间复杂度为O（n），空间复杂度也为O（n）
代码：

import java.util.Stack;

public class evalRPN {
    public static int evalRPN(String[] tokens){
        Stack stack = new Stack<>();
        for (String token : tokens){
        //扫描数组，如果遇到一个 *** 作符，则两个 *** 作数出栈并执行相应的运算，然后计算结果压入栈中。
            switch (token){
                case "+":
                case "-":
                case "*":
                case "/":
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    stack.push(caculate(num2,num1,token));
                    break;
                default:stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    private static Integer caculate(int num2, int num1, String token) {
        switch (token){
            case "+":
                return num2+num1;
            case "-":
                return num2-num1;
            case "*":
                return num2*num1;
            case "/":
                return num2/num1;
            default:
                return 0;
        }
    }

}