2026.10.15 · 11분 읽기 · 조회 0
Top에서만 일어나는 선형구조다


push(e)는 맨 위에 추가, pop()은 맨 위 항목을 꺼내 반환한다.peek()는 맨 위의 값을 반환한다배열을 통해 스택을 구현할 때 삽입/삭제 위치는 리스트의 맨 뒤가 유리하다

O(n) -> 비효율적O(1)top = []
def isEmpty():
return len(top) == 0
def push(item):
top.append(item)
def pop():
if not isEmpty():
return top.pop(-1)
def peek():
if not isEmpty():
return top[-1]
def size(): return len(top)
def clear():
global top
top = []top 하나와 함수들로 스택을 만든다. clear()는 global 선언이 필요하다.class Stack:
def __init__(self):
self.top = []
def isEmpty(self): return len(self.top) == 0
def size(self): return len(self.top)
def clear(self): return self.top = []
def push(self, item):
self.top.append(item)
def pop(self):
if not self.isEmpty():
self.top.pop(-1)
def peek(self):
if not self.isEmpty():
return self.top[-1]
def __str__(self):
return str(self.top[::-1])
올바른 괄호 문자열이 되려면 3가지 조건을 모두 만족해야 한다. 어기는 조건에 따라 오류 종류가 갈린다.
왼쪽 괄호 -> 스택에 push
오른쪽 괄호 -> pop()으로 가장 최근 괄호를 꺼낸다
스택이 비었을 때 pop -> 조건 2 위반
꺼낸 괄호가 짝이 안 맞다 -> 조건 3 위반
완수했는데 스택에 괄호가 남는다 -> 조건 1 위반
def checkBrackets(statement):
stack = Stack()
for ch in statement:
if ch in ( '{', '[', '(' ):
stack.push(ch)
elif ch in ( '}', ']', ')' ):
if stack.isEmpty():
return False # 조건 2 위반
else:
left = stack.pop()
if (ch == "}" and left != "{") or \
(ch == "]" and left != "[")
(ch == ")" and left != "(")
return False # 조건 3 위반
return stack.isEmpty() # False면 조건 1 위반str = ( "{A[(i+1)]=0;}", "if((i==0) && (j==0))", "A[(i+1]) = 0;")
for s in str:
m = checkBrackets(s)
print(s," ---> ", m)튜플에 넣고 돌리면 True, False, False 가 나온다.
def checkBracketsV2(lines):
for line in lines:
res = checkBrackets(line)
if not res:
return False
return True
filename = "ArrayStack.h" # 괄호를 검사할 소스 파일
infile = open(filename , "r") # 파일 열기
lines = infile.readlines(); # 파일 전체를 라인별로 읽은 리스트
infile.close() # 파일 닫기
result = checkBracketsV2(lines) # 검사 함수 호출 (약간 수정 필요)
print(filename, " ---> ", result) # 결과 출력수식의 표기 방법
| 전위(prefix) | 중위(infix) | 후위(postfix) |
|---|---|---|
연산자 피연산자1 피연산자2 | 피연산자1 연산자 피연산자2 | 피연산자1 피연산자2 연산자 |
| + A B | A + B | A B + |
| + 5 * A B | 5 + A * B | 5 A B * + |
수식 표현 방식은 크게 3가지로 나뉜다.
사람은 중위 표기로 쓰지만, 계산기는 이를 후위표기로 바꾼 뒤 스택으로 계산한다.
컴퓨터가 후위표기를 사용하는 이유
- 괄호가 필요없다.
연산자의 위치 자체가 실행 순서를 결정한다.
((A + B) * C) => A B + C *- 연산자 우선순위를 고려할 필요가 없다.
마찬가지로 곱셈/나눗셈/덧셈/뺄셈 등 우선순위 규칙을 고려할 필요가 없어진다.- 스택 자료구조를 이용해 간결하고 빠른 처리가 가능하다.
- 피연산자: 만나면 그대로 Push
- 연산자: pop 두 번 후 계산하고 결과를 push
- 결과: 스택에 하나만 남고, 그 값이 최종 결과
def evalPostfix(expr):
s = Stack()
for token in expor:
if token in "+-*/":
val2 = s.pop()
val1 = s.pop()
if (token == '+'): s.push(val1 + val2)
elif (token == '-'): s.push(val1 - val2)
elif (token == '*'): s.push(val1 * val2)
elif (token == '/'): s.push(val1 / val2)
else: # 항목이 피연산자이면
s.push(float(token)) # 실수로 변경해서 스택에 저장
return s.pop() # 결과 반환['8', '2', '/', '3', '-', '3', '2', '*', '+']테스트 프로그램
expr1 = [ '8', '2', '/', '3', '-', '3', '2', '*', '+' ]
expr2 = [ '1', '2', '/', '4', '*', '1', '4', '/', '*' ]
print(expr1, ' --> ', evalPostfix(expr1))
print(expr2, ' --> ', evalPostfix(expr2))
# ['8', '2', '/', '3', '-', '3', '2', '*', '+'] --> 7.0
# ['1', '2', '/', '4', '*', '1', '4', '/', '*'] --> 0.5결과물이 잘 나온다.
2 + 3 * 4 -> 2 3 4 * +
2 : 숫자이므로 바로 출력 -> 출력: 2
+ : 연산자이므로 스택에 넣음 -> 스택: [+]
3 : 숫자이므로 바로 출력 -> 출력: 2 3
* : +보다 우선순위가 높으므로 스택에 얹음 -> 스택: [+, *]
4 : 숫자이므로 바로 출력 -> 출력: 2 3 4
수식 끝 : 스택에 남은 것들을 위에서부터 꺼냄 (* 후 +) -> 최종 출력: 2 3 4 * +A * B + C -> A B * C +
초기 상태 : 스택: [] -> 출력: 없음
A : 피연산자이므로 바로 출력 -> 스택: [] -> 출력: A
* : 연산자이므로 스택에 넣음 -> 스택: ['*'] -> 출력: A
B : 피연산자이므로 바로 출력 -> 스택: ['*'] -> 출력: A B
+ : *를 꺼내 출력 후 +를 스택에 넣음 -> 스택: ['+'] -> 출력: A B *
C : 피연산자이므로 바로 출력 -> 스택: ['+'] -> 출력: A B * C
수식 끝 : 스택에 남은 연산자(+)를 꺼냄 -> 스택: [] -> 최종 출력: A B * C +(A + B) * C -> A B + C *
( : 여는 괄호이므로 스택에 넣음 -> 스택: ['('] -> 출력: 없음
A : 피연산자이므로 바로 출력 -> 스택: ['('] -> 출력: A
+ : 연산자이므로 스택에 넣음 -> 스택: ['(', '+'] -> 출력: A
B : 피연산자이므로 바로 출력 -> 스택: ['(', '+'] -> 출력: A B
) : '('를 만날 때까지 출력 -> 스택: [] -> 출력: A B +
* : 연산자이므로 스택에 넣음 -> 스택: ['*'] -> 출력: A B +
C : 피연산자이므로 바로 출력 -> 스택: ['*'] -> 출력: A B + C
수식 끝 : 스택에 남은 연산자(*)를 꺼냄 -> 스택: [] -> 최종 출력: A B + C *연산자들의 우선순위를 결정하는 함수가 먼저 필요하다.
def precedence (op):
if op == '(' or op == ')' : return 0
elif op == '+' or op == '-' : return 1
elif op == '* or op == '/' : return 2
else : return -1각 연산다마다 숫자를 매겨 두면 우선순위 비교가 간단해진다.
def Infix2Postfix(expr): # expr: 입력 리스트(중위 표기식)
s = Stack()
output = []
for term in expr:
if term in '(':
s.push('(') # 왼쪽 괄호는 바로 삽입
elif term in ')':
while not s.isEmpty():
op = s.pop() # 왼쪽 괄호가 나올때 까지 출력
if op == '(' : break;
else:
output.append(op)
elif term in "+-*/": # 연산자일때
while not s.isEmpty():
op = s.peek() # top 값을 op에 반환
if (precedence(term) <= precedence(op)):
output.append(op) # 우선순위가 더 낮으면 top을 출력
s.pop()
else: break # 우선순위가 높으면 멈추고 push
s.push(term)
else: # 피연산자일때
output.append(term)
while not s.isEmpty(): # 처리 긑 -> 스택의 모든 항목 출력
output.append(s.pop())
return output # 후위식 리스트 반환 결과테스트 프로그램
infix1 = [ '8', '/', '2', '-', '3', '+', '(', '3', '*', '2', ')' ]
infix2 = [ '1', '/', '2', '*', '4', '*', '(', '1', '/', '4', ')' ]
postfix1 = Infix2Postfix(infix1)
postfix2 = Infix2Postfix(infix2)
result1 = evalPostfix(postfix1)
result2 = evalPostfix(postfix2)
print(' 중위표기: ', infix1)
print(' 후위표기: ', postfix1)
print(' 계산결과: ', result1, end='\n\n')
print(' 중위표기: ', infix2)
print(' 후위표기: ', postfix2)
print(' 계산결과: ', result2)
# 실행 결과:
# 중위표기: ['8', '/', '2', '-', '3', '+', '(', '3', '*', '2', ')']
# 후위표기: ['8', '2', '/', '3', '-', '3', '2', '*', '+']
# 계산결과: 7.0
# 중위표기: ['1', '/', '2', '*', '4', '*', '(', '1', '/', '4', ')']
# 후위표기: ['1', '2', '/', '4', '*', '1', '4', '/', '*']
# 계산결과: 0.5문제 상황
map = [ [ '1', '1', '1', '1', '1', '1' ],
[ 'e', '0', '0', '0', '0', '1' ],
[ '1', '0', '1', '0', '1', '1' ],
[ '1', '1', '1', '0', '0', 'x' ],
[ '1', '1', '1', '0', '1', '1' ],
[ '1', '1', '1', '1', '1', '1' ] ]
MAZE_SIZE = 6다음과 같이 주어진다. 해당 문제를 풀기 위해선 DFS에 대해 알아야 한다.
1. 인근 노드를 큰 번호부터 push 한다.단계 pop push 스택(왼쪽이 바닥)
시작 - 1 [1]
1 1 3, 2 [3, 2]
2 2 5, 4 [3, 5, 4]
3 4 8 [3, 5, 8]
4 8 7, 6, 5 [3, 5, 7, 6, 5]
5 5 (없음) [3, 5, 7, 6]
6 6 3 [3, 5, 7, 3]
7 3 7 [3, 5, 7, 7]
8 7 (없음) [3, 5, 7]-> 3, 5, 7이 중복으로 스택에 쌓이는 구간이 있다.
-> 이미 ""방문했는지" 를 확인하는 로직이 따로 필요하다.
(행, 열) 로 표시한다.Step 1. 시작 위치를 스택에 쌓는다.
Step 2. 스택이 비어있지 않으면 하나 꺼내 현재 위치로 삼고 방문 표시를 한다. 비어 있으면 출구가 없으니 종료
Step 3. 현재 위치가 출구이면 성공. 종료
Step 4. 아니면 이웃을 상,하,좌,우 순서로 보고 방문 안 했고 갈 수 있으면 push 한 뒤 Step 2로 이동.
스택 변화

갈 수 있는 길인지 체크하는 함수
def isValidPos(x, y):
if x < 0 or y < 0 or x >= MAX_SIZE or y >= MAX_SIZE:
return False
else:
return map[x][y] == '0' or map[x][y] == 'x'0(길) or x(출구)1(벽) 과 마침표(지나온 길)DFS 함수
def DFS():
stack = Stack()
stack.push((1, 0)) # 시작 위치 (1, 0)
print('DFS: ')
while not stack.isEmpty():
here = stack.pop()
print(here, end = "->")
(x, y) = here
if map[x][y] == 'x': # 현재 위치가 출구면 종료
return True
else:
map[x][y] = '.' # 현재 위치를 지나왔다고 표시
if isValidPos(x-1, y): stack.push((x-1, y)) # 상
if isValidPos(x+1, y): stack.push((x+1, y)) # 하
if isValidPos(x, y-1): stack.push((x, y-1)) # 좌
if isValidPos(x, y+1): stack.push((x, y+1)) # 우
print("현재 스택:", stack) # 결과(후위표기식 리스트) 반환stack을 queue로 바꾸고 pop을 deque로 바꾸면 BFS가 된다map = [ [ '1','1','1','1','1','1' ],
[ '0','0','0','0','0','1' ],
[ '1','0','1','0','1','1' ],
[ '1','1','1','0','0','x' ],
[ '1','1','1','0','1','1' ],
[ '1','1','1','1','1','1' ] ]
MAX_SIZE = 6
result = DFS()
if result : print(' --> 미로탐색 성공')
else : print(' --> 미로탐색 실패')
# DFS :
# (1, 0)->현재 스택 : [(1, 1)]
# (1, 1)->현재 스택 : [(1, 2), (2, 1)]
# (1, 2)->현재 스택 : [(1, 3), (2, 1)]
# (1, 3)->현재 스택 : [(1, 4), (2, 3), (2, 1)]
# (1, 4)->현재 스택 : [(2, 3), (2, 1)]
# (2, 3)->현재 스택 : [(3, 3), (2, 1)]
# (3, 3)->현재 스택 : [(3, 4), (4, 3), (2, 1)]
# (3, 4)->현재 스택 : [(3, 5), (4, 3), (2, 1)]
# (3, 5)->-->미로탐색 성공!앱과 웹을 만들고, 직접 운영하며 기록합니다.
giscus로 동작하며 GitHub Discussions에 저장됩니다.