LeetCodeのJavaScriptは第150問の解答を行います.逆ポーランド式の求値(Everate Reverse Polish Notation)

3138 ワード

Time:2019/4/14 Title:Everalate Reverse Polish Notation Difficulty:Medium Author:小鹿
テーマ:Everalute Reverse Polish Notation
Evaalute the value of an arthmetic expression in Reverse Polish Notation.
Valid operators are+-*/・・Each operand may be an integer or another exprestion.
ノート:
  • Division between two integers shound truncate toward zero
  • The given RPN expression is always valid.That means the expression would always evaluate to a reult and there won't be any divide by zeration
  • 逆ポーランド表現法によって、表現の値を求めます.
    有効な演算子は、+-*/を含みます.各演算対象は整数でも良いし、別の逆ポーランド式でも良いです.
    説明:
  • 整数除算は整数部分だけ残します.
  • 逆ポーランド表現は常に有効です.つまり、表式は有効な値を導出し、除数が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)すべての操作数は、近くのスタックの操作を行い、オペレータに遭遇した場合、2つの操作数をスタックから取り出して計算し、それをスタックに押し込んで、完全な配列を遍歴するまで配列要素を遍歴し続ける.
    3)最後まで、スタックには一つの数しか残っていません.それは最後の結果です.
    π注意事項
    過程はよく分かりますが、コードを書くのは簡単ですが、アルゴリズムを全面的に書くにはいろいろなことを考えなければなりません.
    1)配列は文字列タイプで、データタイプ変換parseInt().
    2)2つの操作数を演算する場合、2番目の出庫の操作数は前、1番目の出庫の操作数は後(除算に注意)となります.
    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倉庫に一緒に参加することを歓迎します.他の言語のコードを私に提出してもいいです.倉庫の上で堅持して子供達と一緒にカードを打って、共に私達の開源小倉庫を改善します!Github:https://github.com/luxiangqiang/JS-LeetCode