成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode150. Evaluate Reverse Polish Notation

bitkylin / 3385人閱讀

摘要：我們一般看到的數(shù)學(xué)表達(dá)式就是中綴表達(dá)式，也就是將符號放在兩個數(shù)字之間。后綴表達(dá)式也就是將運(yùn)算符放在相應(yīng)數(shù)字的后面。后綴表達(dá)式相當(dāng)于樹中的后序遍歷。通過獲得對應(yīng)位置的操作符。如果對應(yīng)的還是操作符，則繼續(xù)遞歸往前計算。

題目要求 
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

計算后綴表達(dá)式。我們一般看到的數(shù)學(xué)表達(dá)式就是中綴表達(dá)式，也就是將符號放在兩個數(shù)字之間。后綴表達(dá)式也就是將運(yùn)算符放在相應(yīng)數(shù)字的后面。后綴表達(dá)式相當(dāng)于樹中的后序遍歷。

思路一：棧

當(dāng)我們遇到數(shù)字時就將數(shù)字壓入棧中，如果遇到操作符就將棧頂?shù)膬蓚€數(shù)字彈出，并將其根據(jù)操作符計算結(jié)構(gòu)并重新壓入棧中。棧中剩下的最后的值就是我們的結(jié)果。

    public int evalRPN(String[] tokens) {
        LinkedList stack = new LinkedList();
        for(String token : tokens){
            if(token.equals("+")){
                int operand1 = stack.pop();
                int operand2 = stack.pop();
                stack.push(operand2 + operand1);
            }else if(token.equals("-")){
                int operand1 = stack.pop();
                int operand2 = stack.pop();
                stack.push(operand2 - operand1);
            }else if(token.equals("*")){
                int operand1 = stack.pop();
                int operand2 = stack.pop();
                stack.push(operand2 * operand1);
            }else if(token.equals("/")){
                int operand1 = stack.pop();
                int operand2 = stack.pop();
                stack.push(operand2 / operand1);
            }else{
                stack.push(Integer.valueOf(token));
            }
        }
        return stack.pop();
    }
思路二：遞歸

從后綴表達(dá)式的末尾開始遞歸獲取操作符對應(yīng)的兩個操作符。通過index獲得對應(yīng)位置的操作符。如果對應(yīng)的還是操作符，則繼續(xù)遞歸往前計算。

    int index;
    public int evalRPN2(String[] tokens){
        index = tokens.length-1;
        return recursive(tokens);
    } 
    public int recursive(String[] tokens){
        String current = tokens[index--];
        int operand1, operand2;
        switch(current){
        case "+" : 
            operand1 = recursive(tokens);
            operand2 = recursive(tokens);
            return operand1 + operand2;
        case "-" :
            operand1 = recursive(tokens);
            operand2 = recursive(tokens);
            return operand2 - operand1;
        case "*" :
            operand1 = recursive(tokens);
            operand2 = recursive(tokens);
            return operand2 * operand1;
        case "/" :
            operand1 = recursive(tokens);
            operand2 = recursive(tokens);
            return operand2 / operand1;
        default:
            return Integer.valueOf(current);
        }
    }


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/70232.html

相關(guān)文章

  • [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 評論0 收藏0

  • 150. Evaluate Reverse Polish Notation

    摘要：題目鏈接來做，保存數(shù)字，碰到符號的時候就彈出兩個數(shù)字計算算完后再放入，最后里面的就是結(jié)果。 150. Evaluate Reverse Polish Notation 題目鏈接：https://leetcode.com/problems... stack來做，保存數(shù)字，碰到符號的時候就彈出兩個數(shù)字計算算完后再放入stack，最后stack里面的就是結(jié)果。 public class So...

    yanbingyun1990 評論0 收藏0

  • LeetCode 150：逆波蘭表達(dá)式求值 Evaluate Reverse Polish Nota

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

    Turbo 評論0 收藏0

  • LeetCode 之 JavaScript 解答第150題 —— 逆波蘭表達(dá)式求值

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

    104828720 評論0 收藏0

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

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

    ephererid 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<