[問題] decode url string

[Aligu1009 (=.=)]

這是我在面試某間公司時被問的問題
不過我沒有簽保密協定，所以透露題目跟大家討論一下應該okay吧 :p

URL中的"%"符號及其後面的兩個字元可以代表某些特殊符號
如："%20"代表空白" "

若給予 "%??" 與其代表的值的對應
請寫出一個程式能decode url

這個題目比較複雜的地方在於下面這種狀況：
假設"%ab"代表"2"
則"%%ab0"會先decode成"%20", 再decode成" "
所以，若輸入 "http://www.url.com/%%ab0123"
則要輸出："http://www.url.com/ 123"

我用recursive的方式寫了一個小程式
後來主考官要我用非recursive的方式再寫一次
我寫得有一點卡 XD

後來回家自己再寫一次非遞回的版本，
寫是寫出來了，但是竟然寫了一個小時，
主考官當初這題連同講解題目可是只給我10min解題 orz...

我大致上的解法(非遞迴)是用stack來解，
遇到%就inital一個stack,
然後開始判斷後面哪些字元要做push, pop
當stack為空時，就代表目前這個部份的string 已被decode

Ex:
string    cur_word      stack   說明
%%ab0123  %             [%]     push % to stack
%ab0123   %             [%%]    push % to stack
ab0123    a             [%%a]   push a to stack
b0123     b             [%%ab]  push b to stack
                        [%]     pop %, a, b, decode %ab to 2
                        [%2]    push 2 to stack
0123      0             [%20]   push 0 to stack
                        []      pop %, 2, 0, decode %20 to " "
                                stack size is zero. Finish decoding this part


拿出來跟版友們討論一下，不知道各位有沒有什麼比較好的解法呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 75.102.87.217
※ 編輯: Aligu1009       來自: 75.102.87.217        (10/15 23:13)
推 purpose:覺得用stack還是算遞迴，只不過你自己模擬而已
→ uranusjr:你舉例的網址和說明不太一樣耶
→ Aligu1009:Sorry已更正例子中的筆誤
→ Aligu1009:to purpose大,的確stack在概念上也是遞迴,有其他建議嗎?
推 purpose:想不到耶。說個題外話，你舉的例子 %%ab0 我覺得怪怪的
→ purpose:我用IE、Firefox去模仿一個類似的 %%341 其實瀏覽器也不會
→ purpose:去遞迴的把這個網址解碼 %%341 -> %41 -> A。不會解碼出A
→ purpose:ttp://liu.twbbs.org/liuzmd1/index.php?tde_string=%%341
推 Aligu1009:該例子不一定符合真實狀況,只是主考官的一個模擬題而已吧
推 BlazarArc:請問 %?? 有可能會decode出 "%" 這個字元嗎?
→ manlike:亂弄一通 你的stack版有邏輯嗎？ 完全都沒有描述演算法~
→ manlike:這題就從後面往前解碼就行了 一個pass搞定~
推 purpose:%25 解碼後會變成 %，就是依照 ASCII 編碼
→ purpose:manlike大厲害
→ firose:請問用遞迴寫比較簡單嗎?
推 meconin:不是 compiler parser 的問題嗎？
※ 編輯: Aligu1009       來自: 68.232.127.230       (10/16 23:14)