후위 표기식 만들기(스택)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/k3z6

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

 

#강의 풀이
a = input()
stack = []
res = ''
for x in a:
    if x.isdecimal():
        res += x
    else:
        if x == '(':
            stack.append(x)
        elif x == '*' or x == '/':
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                res += stack.pop()
            stack.append(x)
        elif x == '+' or x == '-':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.append(x)
        elif x == ')':
            while stack and stack[-1] != '(':
                res += stack.pop()
            stack.pop()
while stack:
    res += stack.pop()
print(res)

1. 피연산자는 그대로 출력

2. 여는 괄호이면 stack에 추가

3. 연산자가 * / 이면 stack안에 * / 를 pop하고 본인 추가

4. 연산자가 + - 이면 stack안에 여는 괄호가 아닐때까지 pop 하고 본인 추가

5. 닫힌 괄호이면 여는 괄호가 아닐때까지 pop하고 여는 괄호도 pop

6. stack에 남은 연산자 모두 출력

 

어렵구만.

똑같은 문제 (골드3 ㄷ)

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식