【Leetcode】2 逆波兰式的值

题目:计算逆波兰式(后缀表达式)的值

运算符仅包含"+","-","*"和"/",被操作数可能是整数或其他表达式

例如:

 ["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> stack = new Stack<>();
        for(int i=0; i < tokens.length; i++){

            if(tokens[i].equals("+")){
                int op1 = stack.pop();
                int op2 = stack.pop();
                stack.push(op1+op2);
                continue;
            }
            if(tokens[i].equals("-")){
                int op1 = stack.pop();
                int op2 = stack.pop();
                stack.push(op2-op1);
                 continue;
            }
            if(tokens[i].equals("*")){
                int op1 = stack.pop();
                int op2 = stack.pop();
                stack.push(op1*op2);
                 continue;
            }
            if(tokens[i].equals("/")){
                int op1 = stack.pop();
                int op2 = stack.pop();
                stack.push(op2/op1);
                 continue;
            }
            stack.push(Integer.parseInt(tokens[i]));
        }
        return stack.peek();
    }
}

需要注意的点:
import里stack的S是大写
stack初始化语句要记得
减和除记得是2-1 2/1
最后stack.push 那句很关键

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×