脚本宝典收集整理的这篇文章主要介绍了LeetCode 0150 Evaluate Reverse Polish Notation，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

原题传送门

1. 题目描述

2. Solution 1

1、思路分析 遍历tokens中的字符，设工作变量是token，若token是数字则直接入栈，若是运算符，则弹出两个操作数，并根据运算符进行运算，之后将计算结果入栈。直到遍历完成，最后返回栈顶元素。

2、代码实现

package Q0199.Q0150EvaluatereversePolishNotation;

import java.util.Deque;
import java.util.LinkedList;

/*
   method 1: 栈
 */
public class Solution1 {

    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            if (isNumber(token)) stack.push(Integer.parseint(token));
            else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                swITch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }

        }
        return stack.pop();
    }

    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}

3、复杂度分析 @R_828_1304@: O(n) 空间复杂度: O(n)

3. Solution 2

1、思路分析 使用数组代替栈

2、代码实现

package Q0199.Q0150EvaluateReversePolishNotation;

/*
   用数组代替栈
 */
class Solution2 {

    boolean isOp(String str) {
        if (str.length() != 1) return false;
        char ch = str.charAt(0);
        return ch == '+' || ch == '*' || ch == '-' || ch == '/';
    }

    int calc(String op, int v2, int v1) {
        switch(op.charAt(0)) {
            case '+' : return v1 + v2;
            case '-' : return v1 - v2;
            case '*' : return v1 * v2;
            case '/' : return v1 / v2;
        }
        return 0;
    }

    public int evalRPN(String[] tokens) {
        int[] s = new int[tokens.length];
        int i = 0;
        for (String token : tokens) {
            if (isOp(token)) {
                int v2 = s[--i];
                int v1 = s[--i];
                s[i++] = calc(token, v2, v1);
            } else {
                s[i++] = Integer.parseInt(token);
            }
        }
        return s[0];
    }
}

3、复杂度分析 时间复杂度: O(n) 空间复杂度: O(1)

脚本宝典总结

以上是脚本宝典为你收集整理的LeetCode 0150 Evaluate Reverse Polish Notation全部内容，希望文章能够帮你解决LeetCode 0150 Evaluate Reverse Polish Notation所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。