#150. Evaluate Reverse Polish Notation

題目描述

給你一個以逆波蘭表示法呈現的算術運算的字串陣列tokens。

計算這個字串陣列，回傳計算後的整數值。

註記：

符合運算的運算子只有'+'、'-'、'*'、'/'。
每個運算數可能是整數或其他的表示。
整數相除後的值會進行無條件捨去。
不會有除以0的情況發生。
輸入皆為可以運算逆波蘭表示法的運算陣列。
計算的結果與中的計算值都可以已32-bit整數表示。

限制條件

1 <= tokens.length <= 10⁴
tokens[i]只會存在'+'、'-'、'*'、'/'或[-200,200]之間的整數。

解題思路

逆波蘭表示法的原則是數字在前，運算子在後，例如[1,2,+]會等於1+2也就是3，並且不理會先加減後乘除的順序，遇到運算子就要將前兩個數子用該運算子進行計算，例如[1,2,+,3,/]會等於(1+2)/3。題目保證測試案例一定符合逆波蘭表示法且可以運算的完，所以我們只要處理運算的部分就好，這部分可以使用Stack來處理。

Stack

public class Solution { 
	public int EvalRPN(string[] tokens) {
        Stack<int> st = new Stack<int>();
        foreach(string i in tokens){
            if(i=="+"){
                int b = st.Pop();
                int a = st.Pop();
                st.Push(a+b);
            }else if(i=="-"){
                int b = st.Pop();
                int a = st.Pop();
                st.Push(a-b);
            }else if(i=="*"){
                int b = st.Pop();
                int a = st.Pop();
                st.Push(a*b);
            }else if(i=="/"){
                int b = st.Pop();
                int a = st.Pop();
                st.Push(a/b);
            }else{
                st.Push(Int32.Parse(i));
            }
        }
        return st.Peek();
    }
}

複雜度分析：

時間複雜度：要處裡所有陣列元素，因此時間複雜度為O(n)。
空間複雜度：最差情況stack存入一半以上的元素，因此空間複雜度為O(n)。

學習重點

Stack