evaluate reverse polish notation

快来打我* 2022-02-25 17:14 141阅读 0赞

【题目】  
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  
【译】  
用反波兰符号计算算术表达式的值。  
有效的运算符有+、-、*、/。每个操作数可以是整数或其他表达式。  
例子  
\[“2”, “1”, “+”, “3”, "*"\] -> ((2 + 1) \* 3) -> 9  
\[“4”, “13”, “5”, “/”, “+”\] -> (4 + (13 / 5)) -> 6  
【思路】  
遍历字符串，如果不是加减乘除符号，就进栈。如果遇到加减乘除，符号前的两个数就出栈，并进行运算再压栈。  
【实现】

import java.util.Stack;
    public class Solution {
        public int evalRPN(String[] tokens) {
            Stack<Integer> intStack = new Stack<Integer>();
            for(int i = 0;i<tokens.length;i++){
                if(tokens[i].equals("+") ||tokens[i].equals("-")
                  ||tokens[i].equals("*") || tokens[i].equals("/")){
                    int b = intStack.pop();
                    int a = intStack.pop();
                    intStack.push(cal(tokens[i],a,b));
                }else{
                    intStack.push(Integer.parseInt(tokens[i]));
                }
            }
            return intStack.pop();
        }
        public int cal(String s,int a,int b){
            if(s.equals("+")) return a+b;
            else if(s.equals("-")) return a-b;
            else if(s.equals("*")) return a*b;
            else{
                return a/b;
            }
        }
    }