[Leetcode] Evaluate Reverse Polish Notation 計算逆波蘭表

ephererid 發布于2019-08-14 12:40 / 1764人閱讀

摘要：棧法復雜度時間空間思路逆波蘭表達式的計算十分方便，對于運算符，其運算的兩個數就是這個運算符前面的兩個數。注意對于減法，先彈出的是減號后面的數。

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

棧法 復雜度

時間 O(N) 空間 O(N)

思路

逆波蘭表達式的計算十分方便，對于運算符，其運算的兩個數就是這個運算符前面的兩個數。所以我們只要用一個棧，每次遇到數字就壓入棧內，每次遇到運算符就彈出兩個數，計算后再壓回棧內，最后棧內剩下的那個數就是計算結果了。

注意

對于減法，先彈出的是減號后面的數。對于除法，先彈出的是除號后面的數。

代碼

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack stk = new Stack();
        for(String token : tokens){
            switch(token){
                case "+":
                    stk.push(stk.pop() + stk.pop());
                    break;
                case "-":
                    stk.push(-stk.pop() + stk.pop());
                    break;
                case "/":
                    int num1 = stk.pop();
                    int num2 = stk.pop();
                    stk.push(num2 / num1);
                    break;
                case "*":
                    stk.push(stk.pop() * stk.pop());
                    break;
                default:
                    stk.push(Integer.parseInt(token));
            }
        }
        return stk.pop();
    }
}

云服務器 GPU云服務器逆波蘭式逆波蘭表示法逆波蘭式算法c語言 Polish

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64626.html

LeetCode 150：逆波蘭表達式求值 Evaluate Reverse Polish Nota

摘要：題目根據逆波蘭表示法，求表達式的值。給定逆波蘭表達式總是有效的。逆波蘭表達式又叫做后綴表達式。解題思路可以看出逆波蘭表達式中的每一個運算符屬于該運算符前的兩個數字間的運算。如如波蘭表達式則加號前兩個數字為。題目：根據逆波蘭表示法，求表達式的值。有效的運算符包括 +, -, *, / 。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。 Evaluate the value of...

Turbo 2019-08-19 10:19 評論0 收藏0
LeetCode 之 JavaScript 解答第150題 —— 逆波蘭表達式求值

摘要：小鹿題目根據逆波蘭表示法，求表達式的值。給定逆波蘭表達式總是有效的。算法思路仔細觀察上述的逆波蘭表達式，可以發現一個規律就是每遇到一個操作符，就將操作符前的兩個操作數進行運算，將結果保存到原位置。 Time：2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿題目：Evaluate ...

104828720 2019-08-23 16:56 評論0 收藏0
表達式類算法題小結

摘要：將表達式轉換為逆波蘭式，然后求值轉換中綴表達式為逆波蘭式魯棒性檢測，表達式中沒有操作數計算逆波蘭式值參考表達式類算法題小結 [TOC] 聲明文章均為本人技術筆記，轉載請注明出處：[1] https://segmentfault.com/u/yzwall[2] blog.csdn.net/j_dark/ 表達式分類根據運算符與相關操作操作數的位置不同，將表達式分為前綴，中綴和后綴表...

Heier 2019-08-16 10:32 評論0 收藏0
leetcode150. Evaluate Reverse Polish Notation

摘要：我們一般看到的數學表達式就是中綴表達式，也就是將符號放在兩個數字之間。后綴表達式也就是將運算符放在相應數字的后面。后綴表達式相當于樹中的后序遍歷。通過獲得對應位置的操作符。如果對應的還是操作符，則繼續遞歸往前計算。題目要求 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid...

bitkylin 2019-08-16 10:40 評論0 收藏0
[LeetCode] 150. Evaluate Reverse Polish Notation

Problem Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two inte...

KoreyLee 2019-08-16 13:59 評論0 收藏0