스택은 LIFO구조로 가장 나중에 집어넣은 데이터를 가장 먼저 뺄 수 있는 데이터 구조이다.
먼저 집어 넣은 데이터가 먼저 나오는 큐(Queue)와는 반대되는 개념이다.
아래 코드들은 스택을 활용하여 만들어 본 계산기이다.
1. infix 수식 -> postfix 수식 코드
tokens = input().split()
stack, output = [], []
op = {')': 3, '*': 2, '/': 2, '+': 1, '-': 1, '(': 0}
for t in tokens:
if t not in op:
output.append(int(t))
elif t == '(':
stack.append(t)
elif t == ')':
while stack != [] and stack[-1] != '(':
output.append(stack.pop())
stack.pop()
else:
while stack != [] and op[stack[-1]] >= op[t] :
output.append(stack.pop())
stack.append(t)
while stack:
output.append(stack.pop())
print(output)예를 들어 입력이 "( 1 + 3 ) * 2 * 4 - 1"이라면 결과는 [1, 3, '+', 2, '*', 4, '*', 1, '-']이 된다.
2. 계산 코드
nums = []
for t in output:
if t not in op:
nums.append(t)
else:
a, b = nums.pop(), nums.pop()
if t == '+':
nums.append(b+a)
elif t == '-':
nums.append(b-a)
elif t == '*':
nums.append(b*a)
elif t == '/':
nums.append(b/a)
print(nums)( 1 + 3 ) * 2 * 4 - 1 = 31
백준 알고리즘 문제 풀이)
백준 알고리즘 10828번 스택(python)
기본적인 스택 문제이다. import sys class Stack(): def __init__(self): self.li = [] def push(self, n): self.li.append(n) def pop(self): print(self.li.pop() if len(self.li) > 0 else -1) def size(self)..
jinho-study.tistory.com
백준 알고리즘 9012번 괄호(python)
기본적인 스택 문제이다. for _ in range(int(input())): s = input() stack, ok = [], 1 for c in s: if c == '(': stack.append(c) else: if stack == []: ok = 0 else: stack.pop() print("YES" if stack == []..
jinho-study.tistory.com
백준 알고리즘 1874번 스택 수열(python)
스택 문제이다. 처음에 문제를 이해를 못해서 시간이 많이 걸렸다. import sys n = int(sys.stdin.readline()) li = [] stack = [] result = [] index = 0 for i in range(n): li.append(int(sys.stdin.readline(..
jinho-study.tistory.com
백준 알고리즘 10773번 제로(python)
기본적인 스택 문제이다. 입력이 0이 아니면 스택에 추가하고 입력이 0이면 제일 마지막에 추가한 수를 스택에서 제거한다. 마지막에 스택에 들어있는 수들의 합을 출력해주면 된다. li = [] for _ i
jinho-study.tistory.com
백준 알고리즘 4949번 균형잡힌 세상(python)
문자열 & 스택 문제이다. while 1: s = input() if s == '.': break stack = [] ok = 1 for c in s: if c in '([': stack.append(c) elif c in ')': if stack == [] or stack[-1] != '(': ok = 0 break else: stac..
jinho-study.tistory.com
백준 알고리즘 3986번 좋은 단어(python)
기본적인 스택 문제이다. cnt = 0 for _ in range(int(input())): s = input() stack = [] for c in s: if c == 'A': if stack == [] or (stack != [] and stack[-1] != 'A'): stack.append(c) else: stack.pop()..
jinho-study.tistory.com
백준 알고리즘 1935번 후위 표기식2(python)
스택 문제이다. N = int(input()) li = list(input()) nums = [int(input()) for _ in range(N)] output = [] for t in li: if t in "+-*/": a = output.pop() b = output.pop() if t == '+': output.append(b+a)..
jinho-study.tistory.com
백준 알고리즘 2841번 외계인의 기타 연주(python)
스택을 활용해서 풀어야 되는 문제이다. 리스트 안에 여러 개의 스택이 들어있는 구조이다. else문 안에 있는 아래 코드를 생각하지 못해서 계속 틀렸었다. if li[i] != [] and li[i][-1] == p: continue 해답
jinho-study.tistory.com
백준 알고리즘 2812번 크게 만들기(python)
그리디 알고리즘 & 스택 문제이다. 스택을 활용하지 않으면 시간 초과가 나온다. 제일 큰 수로 만들려면 앞에 있는 작은 수부터 없애버려야 한다는 점이 핵심인 것 같다. N, K = map(int, input().split())
jinho-study.tistory.com
백준 알고리즘 6198번 옥상 정원 꾸미기(python)
스택을 활용해서 풀어야 하는 문제이다. for 문을 두 번 써서 풀면 절대 통과할 수가 없다. import sys N = int(sys.stdin.readline()) li = [int(sys.stdin.readline()) for _ in range(N)] stack, res = [], 0 f..
jinho-study.tistory.com
백준 알고리즘 2504번 괄호의 값(python)
스택 문제이다. 주의해야 될 점이 참 많은 문제다. 그래서 엄청 많이 틀렸다. 마지막 스택에 '(', '['가 들어있다면 잘못된 형태이므로 0을 출력, 그렇지 않다면 숫자들만 있는 것이기 때문에 스택
jinho-study.tistory.com
백준 알고리즘 12789번 도키도키 간식드리미(python)
스택과 큐를 둘 다 사용해야 되는 문제이다. from collections import deque N = int(input()) queue = deque(map(int, input().split())) stack = deque() i = 1 while queue: if queue and queue[0] == i: queue..
jinho-study.tistory.com
백준 알고리즘 12605번 단어순서 뒤집기(python)
기본적인 스택 문제이다. from collections import deque for case in range(int(input())): stack = deque(input().split()) print(f"Case #{case+1}: ", end='') while len(stack) > 1: print(stack.pop(), end=..
jinho-study.tistory.com
백준 알고리즘 17952번 과제는 끝나지 않아!(python)
구현 & 스택 문제이다. 스택이 비어있을 때를 주의해서 잘 처리해줘야 한다. 런타임 에러로 엄청 틀렸다ㅜ import sys from collections import deque stack = deque() score = 0 for _ in range(int(sys.stdin.re..
jinho-study.tistory.com
백준 알고리즘 20001번 고무오리 디버깅(python)
구현 & 스택 문제이다. 문제가 상당히 깜찍하다. from collections import deque _ = input() stack = deque() while 1: s = input() if s == "고무오리 디버깅 끝": break if s == "문제": stack.append(1) elif..
jinho-study.tistory.com
백준 알고리즘 17298번 오큰수(python)
스택 문제이다. 처음에 스택에 인덱스 말고 수열의 원소를 넣는 방식으로 생각해서 못 풀었다. 결국 해답을 봤는데 한 끗 차이였다ㅠ 내일 다시 풀어봐야겠다. from collections import deque N = int(input()
jinho-study.tistory.com
백준 알고리즘 10799번 쇠막대기(python)
기본적인 스택 문제이다. 딱 작년만 해도 이 문제를 못 풀었었는데 이제는 쉽게 풀 수 있게 되었다. 굿!! from collections import deque s = input() stack = deque() res = 0 for c in s: if c == '(': stack.ap..
jinho-study.tistory.com
백준 알고리즘 2493번 탑(python)
17298번 오큰수 문제와 거의 동일한 스택 문제이다. 오큰수는 앞에서부터 확인하면서 스택을 쌓아다면 이 문제는 뒤에서 부터 확인하면서 스택을 쌓으면 된다. PyPy3로 제출해야 통과된다. from colle
jinho-study.tistory.com
백준 알고리즘 1918번 후위 표기식(python)
기본적인 스택 문제이다. 내가 스택 맨 처음 공부할 때 봤던 것이 후위 표기식 구현 코드였는데 이렇게 문제로 보니 반갑다! li = list(input()) op = {'(': 0, '+':1, '-': 1, '*': 2, '/': 2, ')': 3} stack, ou..
jinho-study.tistory.com
백준 알고리즘 17608번 막대기(python)
기본적인 스택 문제이다. import sys input = sys.stdin.readline N = int(input()) li = [int(input()) for _ in range(N)] stack, cnt = [li.pop()], 1 for n in li[::-1]: if stack[-1] < n: cnt += 1 stack.ap..
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함) (0) | 2021.03.10 |
|---|---|
| 깊이 우선 탐색(depth-first search, DFS) (백준 문제 포함) (0) | 2021.03.10 |
| 큐(Queue), 덱(Deque) (백준 문제 포함) (0) | 2021.03.05 |
| 그리디(greedy) 알고리즘 (백준 문제 포함) (0) | 2021.01.29 |
| 이분 탐색(Binary Search) 백준 문제 포함 (0) | 2021.01.28 |