[問題] Stack design problem

看板C_and_CPP (C/C++)作者silufear (科技始終沒有人性)時間12年前 (2014/01/22 11:36)推噓9(9推 0噓 9→)

留言18則, 6人參與討論串1/1

問題(Question)：假設任意輸入字串"abc[[ab]111" 需要將無法匹配的中括號位置印出來以上面輸入為例就是印出3 (因為4-7匹配) 餵入的資料(Input)： string pointer int CompareFunc(char *str); 在一個memory不受限的情形下這可以用stack去歸類成基本問題如果設計要求上增加限制： 1.輸入字串長度可能是一個極大值 2.空間複雜度必須為O(1)，即指不能因為字串長度變動增加計憶體使用量從這個條件看來，我自己覺得stack只能被排除但我想不到其它algorithm可以解這個問題不知道有沒有高手可以解惑？ (pseudo code/純設計概念可) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.250.34.42

推

jackace

01/22 12:05, , 1^F

01/22 12:05, 1^F

推

jackace

01/22 12:07, , 2^F

01/22 12:07, 2^F

嗯，只記該func內使用的話說輸入字串算的話，在呼叫func時應該早就GG了 (笑簡單說，就是希望字串長度100時用量x，長度1000時也是用量x這樣可無視時間複雜度...(本來就不合理)

推

yvb

01/22 12:50, , 3^F

01/22 12:50, 3^F

推

yvb

01/22 12:54, , 4^F

01/22 12:54, 4^F

→

yvb

01/22 12:56, , 5^F

01/22 12:56, 5^F

推

yvb

01/22 13:06, , 6^F

01/22 13:06, 6^F

→

yvb

01/22 13:08, , 7^F

01/22 13:08, 7^F

→

yvb

01/22 13:13, , 8^F

01/22 13:13, 8^F

以下從0開始跳 "a[[[b]c" >>> 理論上要輸出 1 2 (3&5是一對) "a[[b]]c" >>> 理論上不輸出 (1&5一對, 2&4一對) "a[b]]]c" >>> 理論上輸出 4 5 (1&3一對) 我的煩惱點就在於，如果不記錄要做匹配檢查的工作也很麻煩乾脆直接拿*str開刀算了XD 找到匹配的就清掉最後再scan一次再沒配到的印出來，畢竟題目是沒說不能動*str... 這問題是別人問我的，沒有標準答案 ※ 編輯: silufear 來自: 1.160.236.15 (01/22 22:40)

→

Feis

01/22 22:58, , 9^F

01/22 22:58, 9^F

推

tarrytu

01/23 03:33, , 10^F

01/23 03:33, 10^F

原來簡易的鄰近比對就可以判斷是否匹配字元受教了，感謝指教 ※ 編輯: silufear 來自: 111.250.15.213 (01/23 10:28)

→

MOONRAKER

01/23 10:40, , 11^F