evaluate-reverse-polish-notation

题目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,,/. Each operand may be an integer or another expression.
Some examples:
[“2”, “1”, “+”, “3”, “
“] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

思路

使用一个操作栈,遇到数字,就入栈,遇到操作符从栈中弹出两个操作数,进行操作完以后把结果压回栈中,最后理论上栈中会剩一个元素,这元素就是表达式的最终结果。

代码

import java.util.Stack;
public class Solution {
    //["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
    public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.length==0){
            return 0;
        }
        Stack<String> s = new Stack<>();
        int index=0;
        while (index<tokens.length){
            if(isNumber(tokens[index])){
                s.push(tokens[index]);
                index++;
            }else {
                //是操作符

                int right = Integer.parseInt(s.pop());
                int left = Integer.parseInt(s.pop());

                switch (tokens[index++]){
                    case "+":
                        s.push(String.valueOf(right+left));
                        break;
                    case "-":
                        s.push(String.valueOf(left-right));
                        break;
                    case "*":
                        s.push(String.valueOf(left*right));
                        break;
                    case "/":
                        s.push(String.valueOf(left/right));
                        break;
                    default:break;
                }
            }
        }
        return Integer.parseInt(s.peek());
    }
    private boolean isNumber(String str){
        try {
            Integer integer = Integer.parseInt(str);
            return true;
        }catch (Exception e){
            return false;
        }
    }
}