資訊專欄INFORMATION COLUMN
摘要：棧法復(fù)雜度時間空間思路逆波蘭表達(dá)式的計算十分方便，對于運算符，其運算的兩個數(shù)就是這個運算符前面的兩個數(shù)。注意對于減法，先彈出的是減號后面的數(shù)。
Evaluate Reverse Polish Notation
棧法 復(fù)雜度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)
思路逆波蘭表達(dá)式的計算十分方便，對于運算符，其運算的兩個數(shù)就是這個運算符前面的兩個數(shù)。所以我們只要用一個棧，每次遇到數(shù)字就壓入棧內(nèi)，每次遇到運算符就彈出兩個數(shù)，計算后再壓回棧內(nèi)，最后棧內(nèi)剩下的那個數(shù)就是計算結(jié)果了。
注意對于減法，先彈出的是減號后面的數(shù)。對于除法，先彈出的是除號后面的數(shù)。
代碼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();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64626.html
摘要：題目根據(jù)逆波蘭表示法，求表達(dá)式的值。給定逆波蘭表達(dá)式總是有效的。逆波蘭表達(dá)式又叫做后綴表達(dá)式。解題思路可以看出逆波蘭表達(dá)式中的每一個運算符屬于該運算符前的兩個數(shù)字間的運算。如如波蘭表達(dá)式則加號前兩個數(shù)字為。 題目： 根據(jù)逆波蘭表示法，求表達(dá)式的值。 有效的運算符包括 +, -, *, / 。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達(dá)式。 Evaluate the value of...
摘要：小鹿題目根據(jù)逆波蘭表示法，求表達(dá)式的值。給定逆波蘭表達(dá)式總是有效的。算法思路仔細(xì)觀察上述的逆波蘭表達(dá)式，可以發(fā)現(xiàn)一個規(guī)律就是每遇到一個操作符，就將操作符前的兩個操作數(shù)進(jìn)行運算，將結(jié)果保存到原位置。 Time：2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 題目：Evaluate ...
摘要：將表達(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á)式分為前綴，中綴和后綴表...
摘要：我們一般看到的數(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...
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...
閱讀 3729·2021-11-25 09:43
閱讀 2609·2021-11-18 13:11
閱讀 2229·2019-08-30 15:55
閱讀 3279·2019-08-26 11:58
閱讀 2835·2019-08-26 10:47
閱讀 2237·2019-08-26 10:20
閱讀 1279·2019-08-23 17:59
閱讀 3014·2019-08-23 15:54
