こちらは「Valid Parentheses」のPythonによる解答例となっております。この問題は、括弧の文字列が与えられたとき、括弧が正しく対応しているかどうかを判定する問題です。
問題
括弧の文字列 s が与えられたとき、括弧が正しく対応しているかどうかを判定します。以下の括弧が存在するとします。この関数が返す値は、括弧が正しく対応している場合はTrue、そうでない場合はFalseです。
- 開き括弧：
(,{,[ - 閉じ括弧：
),},]
括弧は、次の条件を満たす必要があります。
- 開き括弧は同じ型の閉じ括弧で閉じなければなりません。
- 開き括弧は正しい順序で閉じなければなりません。
解法
この問題は、スタックを用いた1つのアプローチがあります。文字列を1文字ずつ走査し、開き括弧が出現した場合はスタックに追加し、閉じ括弧が出現した場合はスタックから開き括弧をpopし、括弧が正しく対応しているかどうかを確認します。
アルゴリズムの概要を以下に述べます。
- スタックを初期化します。
- 文字列を1文字ずつ走査します。
- 開き括弧が出現した場合、スタックに追加します。
- 閉じ括弧が出現した場合、スタックから開き括弧をpopし、括弧が正しく対応しているかどうかを確認します。
- スタックが空であれば、括弧が正しく対応しているため、
Trueを返します。それ以外の場合は、Falseを返します。
Pythonコード
以下のコードが、「Valid Parentheses」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().isValid
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.s)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
class Solution(object):
def isValid(self, s):
"""
:type s: str
1 <= s.length <= 104
s[i]: '(', ')', '[', ']', '{', '}'
:rtype: bool
"""
if len(s)%1==1: return False
mapping = {
")": "(",
"}": "{",
"]": "["
}
stack = []
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element: return False
else: stack.append(char)
return not stack
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.s = "()"
self.ans = True
elif num == 2:
self.s = "()[]{}"
self.ans = True
elif num == 3:
self.s = "(]"
self.ans = False
else:
self.input = 3
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################