[김태원 알고리즘] 후위표기식 만들기 (스택)

사용 언어: Python3

문제

풀이

내 풀이

prior = {'+':1, '-':1, '*':2, '/':2, '(':0, ')':0} # ✅ 연산자 우선순위
lst = list(input())

stack = [] # +-*/()만 담을 스택, 숫자는 바로 출력
ans = '' # 답

for x in lst:
    if not x in '+-*/()': # ✅ 표현 알아두기!
        ans += x
    elif x == '(':
        stack.append(x)
    elif  x == ')': # 닫는 괄호라면 스택에서 여는 괄호 만날때까지 처리
        while stack and stack[-1] != '(':
            ans += stack.pop()
        stack.pop() # 여는 괄호까지 pop
    else:
        while stack and prior[stack[-1]] >= prior[x]: # 나보다 우선순위가 높다면 처리
            ans += stack.pop()
        stack.append(x)

# 스택에 남은 것들 붙여주기
while stack:
    ans += stack.pop()

print(ans)

• 딕셔너리로 연산자 우선순위 정의
  • 원래 괄호는 우선순위가 가장 높지만, 여기에서 열린 괄호가 스택에 담겼을 때 모든 문자를 처리하면 안되기 때문에 우선순위 가장 낮게 설정
• 풀이
  • lst를 순회하며 숫자는 ans에 바로바로 누적한다.
  • 문자(+,-,*,/)라면 스택에 담아야하는데,
    담기 전에 스택 안에 나보다 우선순위가 높은 문자가 들어있다면, 그 문자들을 처리한다.(=pop해서 ans에 누적한다.)
    더이상 나보다 우선순위가 높은 문자가 없다면 스택에 append 한다. (우선순위: *, / »> +, -)
  • 열린 괄호(()는 아무 문자도 pop하지 않고 바로 append 한다.
  • 닫힌 괄호())는 열린 괄호가 나올때까지 스택의 문자들을 처리한다.(=pop해서 ans에 누적한다.)

다른 풀이

로직은 위와 같다.

lst = list(input())

stack = []
ans = ''

for x in lst:
    if x.isdecimal(): # ✅ x가 십진수 숫자라면 참
        ans += x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/': # 나보다 우선순위가 높다면 처리
            while stack and (stack[-1]=='*' or stack[-1] == '/'):
                ans += stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and stack[-1] != '(': # 여는 괄호가 있다면 그 전까지만 끄집어내기
                ans += stack.pop()
            stack.append(x)
        elif x == ')':
            while stack and stack[-1] != '(': # 여는 괄호를 만날 때까지
                ans += stack.pop()
            stack.pop() # 여는 괄호 pop

# 스택에 남은 것들 붙여주기
while stack:
    ans += stack.pop()

print(ans)

내 풀이

prior = {'+':1, '-':1, '*':2, '/':2, '(':0, ')':0} # ✅ 연산자 우선순위
lst = list(input())

ans = ''
stack = []
for x in lst:
    if x.isdecimal(): # ✅ x가 십진수 숫자라면 참
        ans += x
    elif x == '(':
        stack.append(x)
    elif x == ')':
        while stack and stack[-1] != '(':
            ans += stack.pop()
        stack.pop() # 열린괄호 pop
    else: # +,-,*,/ 일 때
        # 스택 안에 있는 나보다 우선순위 높은 연산들 먼저 처리하고
        while stack and prior[stack[-1]] >= prior[x]:
            ans += stack.pop()
        stack.append(x) # 나 들어가기

# 스택에 남은 것들 붙여주기
ans += ''.join(stack)
print(ans)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기