[Leetcode] Evaluate Reverse Polish Notation 計(jì)算逆波蘭表

ephererid 發(fā)布于2019-08-14 12:40 / 1772人閱讀

摘要：棧法復(fù)雜度時(shí)間空間思路逆波蘭表達(dá)式的計(jì)算十分方便，對(duì)于運(yùn)算符，其運(yùn)算的兩個(gè)數(shù)就是這個(gè)運(yùn)算符前面的兩個(gè)數(shù)。注意對(duì)于減法，先彈出的是減號(hào)后面的數(shù)。

Evaluate Reverse Polish Notation

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

棧法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

逆波蘭表達(dá)式的計(jì)算十分方便，對(duì)于運(yùn)算符，其運(yùn)算的兩個(gè)數(shù)就是這個(gè)運(yùn)算符前面的兩個(gè)數(shù)。所以我們只要用一個(gè)棧，每次遇到數(shù)字就壓入棧內(nèi)，每次遇到運(yùn)算符就彈出兩個(gè)數(shù)，計(jì)算后再壓回棧內(nèi)，最后棧內(nèi)剩下的那個(gè)數(shù)就是計(jì)算結(jié)果了。

注意

對(duì)于減法，先彈出的是減號(hào)后面的數(shù)。對(duì)于除法，先彈出的是除號(hào)后面的數(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();
    }
}