#40 Coding 面試 - LeetCode #150 Evaluate Reverse Polish Notation

原文題目網址 : https://leetcode.com/problems/evaluate-reverse-polish-notation/

這題蠻有趣的.剛看到這題時,老實說並不知道什麼是 Reverse Polish Notation.如果你在被考到這題時也不知道的話,其實也沒關係,因為你可以直接問主考官,主考官一定會告訴你什麼是 Reverse Polish Notation.因為你要懂了這是什麼表示法,你才能做這個題目.

簡單的說,一般的數學,我們習慣寫成像我們從小到大看到的式子,例如 3+4.而 Reverse Polish Notation 就會寫成 34+ ,很簡單吧! 所以你看到題目上給你的例子, 2,1,+,3,* 就是 (2+1) * 3 ,因此答案就是 9.所以,這一題就是要考你寫一個 function,輸入是 Reverse Polish Notation,而輸出是數字答案.因此,我們假設輸入是一個 string array,而輸出是 int.

不知道你看到這種題目時,你會不會馬上聯想到 stack 或是 queue 之類的資料結構,因為可以依序地把數字儲存下來,又可以正向或反向地把數字取出來.如果你能想到這個,解題的方向也算是對的了.

除此之外,一開始還要為輸入字串做檢查,檢查是不是合格可運算的.例如,如果輸入字串都是運算符號而沒有數字,那這是不能算的,需要回傳錯誤.或者是輸入字串只有數字而沒有運算符號,這也是不能計算的.另外,輸入字串的第一個和第二個元素一定不會是運算符號,一定會是數字.所以這幾個條件就當做是程式裡的 throw exception 的條件.

接著,只需要一個 for loop ,把符合所有條件的數字用 stack 記錄下來,然後遇到運算符號時,把從 stack 把之前的數字拿出來運算,算完後再寫回去 stack.所以,用這樣的邏輯就可以把這題的答案寫出來了.

程式碼參考如下:


Share:

#39 物件導向 - Interface 的基本應用範例

記得以前在學習物件導向語言的時候, 學到了 Class 定義,也學到的物件跟物件之間的關係, 後面也學到繼承關係. 在學習這些物件導向內容的時候也有看到 interface, 不過當時對 interface 並沒有太深刻的了解. 所以在這一篇文章裡面就來談一談 interface.

如果你做過一些小專案或者只是個人在用的一些小程式, 基本上來說 interface 用到的機會應該是不多. 相反的, 如果你曾參與大型專案, 那麼 interface 應該是到處可見的. 為什麼呢? 那是因為大型的專案通常是由多個開發者所共同進行, 所以不同的開發者會負責不同的項目, 你也可以把看成不同的開發者會負責不同的元件. 而在一個大型的專案裡, 元件跟元件之間的溝通是件基本的事情. 然而,元件跟元件之間的溝通不一定只是單純的資料傳遞, 傳遞的內容中有可能是物件本身. 所以, 元件和元件之間就必須要遵守特定的規則, 這樣子我們才能夠成功的將資料或者是物件傳送給對方. 除此之外, interface 的好處也可以應用在軟體測試上. 接下來用一些簡單的例子來說明.


這個例子是微軟開發工具產品裡面的某一個視窗, 而在視窗裡面有一些控制項, 它的長相大概就如下圖所示:


可以看到在這個視窗中有一塊大的空白, 裡面顯示這個不同的專案範本. 假設製作視窗元件的團隊和製作專案範本的團隊是不一樣的, 也就是說他們的程式碼是來自兩個不同的專案, 他們要怎麼做才能夠達成協同運作的目的. 其中的關鍵技巧就是使用 interface. 例如說有一個 interface 的定義如下,

public interface ITemplate {
    List<Template> GetTemplate(TemplateKind kind);
    List<TemplateKind> GetTemplateKind();
}

製作視窗的團隊中, 他們一定會去採用這個 interface 定義, 因為在這一個 interface 定義裡面提供了兩個方法. 第一個方法是取得有多少範本, 第二個方法是去取得有多少範本種類. 在他們顯示這一個空白區域的內容時, 他們就可以將這個介面定義作為參數,

public void ShowTemplates(ITemplate templates)

ShowTemplates 方法本身是可以由外部程式來呼叫的, 所以只要能夠準備好所需要的參數, 就可以將物件參數傳進去, 然後這一個方法就可以依照 interface 提供的方法把範本的種類和範本顯示在空白地域上.

所以透過這種方法, 開發範本的團隊就可以很清楚的知道需要傳過去的參數內容長相是什麼樣子.這樣看起來就像是兩個團隊之間有著共同的合約, 合約裡面的內容就是定義這會有哪些屬性或方法.


Share: