LeetCode 之 JavaScript 解答第150題 —— 逆波蘭表達式求值

104828720 發布于2019-08-23 16:56 / 3198人閱讀

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

Time：2019/4/14
Title: Evaluate Reverse Polish Notation
Difficulty: Medium
Author:小鹿

題目：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.

Note:

Division between two integers should truncate toward zero.

The given RPN expression is always valid. That means the expression would always evaluate to a result and there won"t be any divide by zero operation.

根據逆波蘭表示法，求表達式的值。

有效的運算符包括 +, -, *, / 。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。

說明：

整數除法只保留整數部分。

給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數值且不存在除數為 0 的情況。

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Solve:

▉ 算法思路

仔細觀察上述的逆波蘭表達式，可以發現一個規律就是每遇到一個操作符，就將操作符前的兩個操作數進行運算，將結果保存到原位置。

1）我們可以將這個過程用棧來進行操作。

2）所有的操作數都執行近棧操作，當遇到操作符時，在棧中取出兩個操作數進行計算，然后再將其壓入棧內，繼續遍歷數組元素，直到遍歷完整個數組為止。

3）到最后，棧內只剩下一個數，那就是最后的結果。

▉ 注意事項

雖然過程很好理解，代碼寫起來很簡單，但是想把算法寫的全面還是需要考慮到很多方面的。

1）數組中的是字符串類型，要進行數據類型轉換 parseInt() 。

2）兩個操作數進行運算時，第二個出棧的操作數在前，第一個出棧的操作數在后（注意除法）。

3）對于浮點型數據，只取小數點之前的整數。

4）關于負的浮點型（尤其是 0 點幾），要取 0 絕對值 0 ，或直接轉化為整數。

▉ 代碼實現

var evalRPN = function(tokens) {
   // 聲明棧
    let stack = [];
    for(let item of tokens){
        switch(item){
            case "+":
                let a1 = stack.pop();
                let b1 = stack.pop();
                stack.push(b1 + a1);
                break;
            case "-":
                let a2 = stack.pop();
                let b2 = stack.pop();
                stack.push(b2 - a2);
                break;
            case "*":
                let a3 = stack.pop();
                let b3 = stack.pop();
                stack.push(b3 * a3);
                break;
            case "/":
                let a4 = stack.pop();
                let b4 = stack.pop();
                stack.push(parseInt(b4 / a4));
                break;
            default: 
                stack.push(parseInt(item));
        }
    }
    return parseInt(stack.pop());
};

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...

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

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

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

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

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

Turbo 2019-08-19 10:19 評論0 收藏0
表達式類算法題小結

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

Heier 2019-08-16 10:32 評論0 收藏0
堆棧的應用——用JavaScript描述數據結構

摘要：一實現一個棧類基于堆棧的特性，可以用數組做線性表進行存儲。出棧出棧同樣是利用數組的方法，在數組尾部推出數據。聚合最后，將所有功能聚合后，如下所示，一個堆棧的數據結構就搞定了。堆棧的經典算法應用，首推就是漢諾塔。棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。一、實現一個棧類Stack 基于堆...

Hydrogen 2019-08-23 10:54 評論0 收藏0
[Leetcode] Evaluate Reverse Polish Notation 計算逆波蘭表

摘要：棧法復雜度時間空間思路逆波蘭表達式的計算十分方便，對于運算符，其運算的兩個數就是這個運算符前面的兩個數。注意對于減法，先彈出的是減號后面的數。 Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operato...

ephererid 2019-08-14 12:40 評論0 收藏0