主題

ZeroJudge - e924: pC. 括號配對　解題心得

Not In My Back Yard | 2020-03-23 00:11:17 | 巴幣 0 | 人氣 974

題目連結：

題目大意：

第一列給定一正整數 T （1 ≦ T ≦ 1000），代表有 T 列輸入。每列給定一個只包含「(」、「)」、「[」、「]」、「<」、「>」、「{」、「}」八種括號符號的字串。請判斷該字串裡的括號是否為合法匹配（匹配範例可參見這題）。

如果為合法匹配，則輸出「Y」；反之，輸出「N」。

範例輸入：

{()<>}[]

(){

{(})

())

範例輸出：

解題思維：

因為左括號一定會配上相應的右括號（如果是合法匹配的話），因此可以消掉該對左括號以及右括號並判斷剩下的匹配情形。

所以可以用一個堆疊（Stack）來實作。每遇到一個左括號（不管是哪一種括號），就將其放入堆疊之中；如果是右括號，就看現在堆疊頂端的括號是否為與之相對的左括號。如果是將移除該左括號；反之，則代表匹配失敗，也就代表整個字串並非合法匹配。

如果跑過一次字串之後，發現堆疊非空，則代表左括號的量大於右括號的量，其也非合法匹配。

如果能通過以上的匹配判斷，則代表字串為一組合法的括號匹配。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

ETH官方钱包