강의
중위 표기법 (infix notation) : 연산자가 피연산자들의 사이에 위치
후위 표기법 (postfix notation) : 연산자가 피연산자들의 뒤에 위치
알고리즘 설계
1. 연산자의 우선순위 설정
2. 왼쪽부터 한 글자씩 읽기
3. 열린 괄호는 push, 닫힌 괄호는 열린 괄호가 나올 때까지 pop
4. 수식을 끝까지 확인한 후 스택에 남은 연산자 모두 pop
12강 실습: 중위표현 수식 --> 후위표현 수식
⭐ 힌트 : 스택에서 꺼내지 않고 peek()를 이용해 우선순위 비교하고 isEmpty() 이용하여 모두 pop!
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
opstack = ArrayStack()
ans = ""
for s in S:
if s == "(":
opstack.push(s)
elif s in prec:
while not opstack.isEmpty() and prec[s] <= prec[opstack.peek()]:
ans += opstack.pop()
opstack.push(s)
elif s == ")":
while opstack.peek() != "(":
ans += opstack.pop()
opstack.pop()
else:
ans += s
while not opstack.isEmpty():
ans += opstack.pop()
return ans
'데브코스 TIL > 자료구조, 알고리즘' 카테고리의 다른 글
14강: 큐(Queues) (0) | 2023.10.18 |
---|---|
13강: 후위 표기 수식 계산 (0) | 2023.10.17 |
11강: 스택(Stacks) (0) | 2023.10.17 |
10강: 양방향 연결 리스트(Doubly Linked Lists) (0) | 2023.10.17 |
9강: 연결 리스트(Linked Lists) (3) (0) | 2023.10.17 |