国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

Turbo / 2669人閱讀

摘要:題目根據(jù)逆波蘭表示法,求表達(dá)式的值。給定逆波蘭表達(dá)式總是有效的。逆波蘭表達(dá)式又叫做后綴表達(dá)式。解題思路可以看出逆波蘭表達(dá)式中的每一個運算符屬于該運算符前的兩個數(shù)字間的運算。如如波蘭表達(dá)式則加號前兩個數(shù)字為。

題目:

根據(jù)逆波蘭表示法,求表達(dá)式的值。

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

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

說明:

整數(shù)除法只保留整數(shù)部分。

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

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.

示例 1:

輸入: ["2", "1", "+", "3", "*"]
輸出: 9
解釋: ((2 + 1) * 3) = 9

示例 2:

輸入: ["4", "13", "5", "/", "+"]
輸出: 6
解釋: (4 + (13 / 5)) = 6

示例 3:

輸入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
輸出: 22
解釋: 
  ((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
擴(kuò)展:

逆波蘭表達(dá)式,它的語法規(guī)定,表達(dá)式必須以逆波蘭表達(dá)式的方式給出。逆波蘭表達(dá)式又叫做后綴表達(dá)式。這個知識點在數(shù)據(jù)結(jié)構(gòu)和編譯原理這兩門課程中都有介紹,下面是一些例子:

a+b ---> a,b,+
a+(b-c) ---> a,b,c,-,+
a+(b-c)*d ---> a,b,c,-,d,*,+
a+d*(b-c)--->a,d,b,c,-,*,+
a=1+3 ---> a,1,3,+,=

從上面的例子可以看出:
(1) 在兩種表示中,運算對象出現(xiàn)的順序相同;
(2) 在后綴表示中,運算符按實際計算順序從左到右排列,且每一運算符總是跟在其運算對象之后。

這種表達(dá)式很反人類,但是對計算機(jī)很友好,因為計算機(jī)運算是利用棧數(shù)據(jù)結(jié)構(gòu)。

解題思路:

可以看出逆波蘭表達(dá)式中的每一個運算符屬于該運算符前的兩個數(shù)字間的運算。如:

如波蘭表達(dá)式:1,2,+
則加號前兩個數(shù)字為1,2。其運算符就是加號:1+2
得出結(jié)果:1+2=3

如波蘭表達(dá)式:1,2,3,+,-
則加號前兩個數(shù)字為2,3。其運算符就是加號:2+3
得出結(jié)果2+3=5,則波蘭表達(dá)式變?yōu)?1,5,-
減號前兩個數(shù)字為1,5,其運算符就是減號:1-5
得出結(jié)果1-5=-4

由上面的的例子思路就很清晰了,直接用指針遍歷表達(dá)式,遇到數(shù)字就入棧,遇到運算符就彈出兩個數(shù)字,把他們運算之后得出結(jié)果,再作為獨立數(shù)字入棧。最后棧內(nèi)只剩一個元素 即表達(dá)式運算結(jié)果。也可以用遞歸

Java:
class Solution {
    public int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for (String t : tokens) {
            if (t.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (t.equals("-")) {
                int tmp = stack.pop();
                stack.push(stack.pop() - tmp);
            } else if (t.equals("*")) {
                int tmp = stack.pop();
                stack.push(stack.pop() * tmp);
            } else if (t.equals("/")) {
                int tmp = stack.pop();
                stack.push(stack.pop() / tmp);
            } else {
                stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}
Python:

python也可以用數(shù)組代替棧完成上述方法解答本題。這里用另一個函數(shù) eval() 代替上述四個 if 判斷:

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for t in tokens:
            if t in "+-*/":
                tmp = stack.pop()
                stack.append(int(eval("stack.pop()" + t + "tmp")))
            else:
                stack.append(int(t))
        return stack.pop()

eval() 函數(shù)可以執(zhí)行傳入?yún)?shù) 字符串語句。

eval("print("hhhhh")") 會執(zhí)行參數(shù)字符串打印出hhhhh

歡迎大家關(guān)注微.信公.眾號:愛寫B(tài)ug

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

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/75814.html

相關(guān)文章

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

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

    104828720 評論0 收藏0
  • [Leetcode] Evaluate Reverse Polish Notation 計算波蘭

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

    ephererid 評論0 收藏0
  • 達(dá)式類算法題小結(jié)

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

    Heier 評論0 收藏0
  • leetcode150. Evaluate Reverse Polish Notation

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

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

發(fā)表評論

0條評論

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