Stack
スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
- Stackは「積み重ね」という意味です。
- データをどんどんと積み重ねていくイメージです。積み重ねることをPushと言います。
- データを取る時は積み重なっているので、一番上のデータしか取ることできません。これをPopと言います。
- 一番最後に入ったもの(Last In)が、一番最初に取り出される(First Out)でLIFOと呼ばれます。
Stackの実装
Pythonのリストを使い実装します。
Pythonのドキュメントに書いてあることをクラスにするだけです。
class Stack():
def __init__(self):
self.stack = []
# データを追加する。
def push(self, item):
self.stack.append(item)
# データを取り出す。
def pop(self):
return self.stack.pop()
# スタックの中身を確認する。
def get_stack(self):
return self.stack
Stackを使い括弧の対応関係を調べる
括弧を含む一つの文が与えられたときに、その括弧に対応する括弧があるかどうかを確認します。
from stack import Stack
# 括弧がちゃんと対応しているか確認する
def is_match(parenth1, parenth2):
if parenth1 == "(" and parenth2 == ")":
return True
elif parenth1 == "{" and parenth2 == "}":
return True
elif parenth1 == "[" and parenth2 == "]":
return True
else:
return False
def check(string):
stack = Stack()
is_balanced = True
opening = "([{"
closing = ")]}"
for char in string:
# 始まりの括弧であればスタックに積む。
if char in opening:
stack.push(char)
# 閉じ括弧の場合
elif char in closing:
# スタックが空の場合は、対応する始まりの括弧がないのでエラー。
if stack.is_empty():
is_balanced = False
break
# スタックに積んである場合は、対応関係を確認する。
else:
top = stack.pop()
if not is_match(top, char):
is_balanced = False
break
# 括弧以外の時は何もしない。
else:
pass
if stack.is_empty() and is_balanced:
return True
else:
return False
# True
print(check("((def)gx)"))
# False
print(check("(((h)"))
# True
print(check("func(a[1], **{'apple':1, 'orange':2, 'banana':3})" ))
# False
print(check("func(a[1], **{'apple':1, 'orange':2, 'banana':3])"))
Stackを使い10進数を2進数に変換する
10進数から2進数への変換の仕組みが分かりやすく説明されています。
つまり、10進数の数をどんどん2で割って余りを下のほうから足し上げれば、2進数に変換できます。
from stack import Stack
def decimal_to_binary(decimal_num):
stack = Stack()
while decimal_num > 0:
remainder = decimal_num % 2
stack.push(remainder)
decimal_num = decimal_num // 2
binary_num = ""
while not stack.is_empty():
binary_num += str(stack.pop())
return binary_num
# # 1001100
# print(decimal_to_binary(76))
# # 10010010
# print(decimal_to_binary(146))