電腦科學 ^ IT人生 ^ 公益課程

#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:

0 意見:

張貼留言