Re: [閒聊] 每日LeetCode
150. Evaluate Reverse Polish Notation
利用逆波蘭表示法來模擬一個計算機的加減乘除結果，保證所有計算結果都
合法且最後一定會有解。
Example：
Input: tokens = ["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
思路：
1.用一個stack來處理運算式，如果遇到數字就push數字到stack。
2.如果遇到長度為1又不是數字的就從stack裡面pop兩個數字出來處理，並push回去。
3.返回stack裡面剩下的元素。
Java Code：
----------------------------------
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (token.length() == 1 && !Character.isDigit(token.charAt(0))) {
int n1 = stack.pop();
int n2 = stack.pop();
stack.push(helper(n2, n1, token.charAt(0)));
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
private int helper(int n1, int n2, char c) {
switch (c) {
case '-' :
return n1 - n2;
case '+' :
return n1 + n2;
case '*' :
return n1 * n2;
default:
return n1 / n2;
}
}
}
----------------------------------
--
https://i.imgur.com/tdaniED.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671265344.A.355.html
推
12/17 16:23,
3年前
, 1F
12/17 16:23, 1F
推
12/17 16:33,
3年前
, 2F
12/17 16:33, 2F
要保存一個結果 之後再回來處理的時候 遞迴就要用到stack了ㄚ
※ 編輯: Rushia (122.100.75.86 臺灣), 12/17/2022 16:35:39
討論串 (同標題文章)
完整討論串 (本文為第 140 之 719 篇)：