[백준 1918] 후위 표기식 (Python) (중위 표기식 -> 후위 표기식 변환 문제)

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

1918번: 후위 표기식

 

문제풀이

 

cmd : 입력값

stack : 괄호와 연산자를 저장할 stack list

ans : 결과 list

 

스택을 이용해서 연산자의 우선순위를 결정해 결과 list에 넣는 방식으로 해결하였다.

 

1. A~Z 알파벳일 경우 ans에 바로 추가한다.

 

2. '(', '+', '-'. '*', '/' 연산자일 경우 stack에 추가한다.

- '*' 나 '/' 일 경우, 연산자 우선순위에 의해서 현재 stack에 추가로 '*', '/' 가 있는지 탐색 후 stack에 추가한다.

- '+' 나 '-' 일 경우, 연산자 우선순위에 의해서 현재 stack에 '(' 가 있는지 탐색 후 stack에 추가한다.

- ')' 의 경우, stack에서 '(' 탐색 후 stack 에서 '('를 빼준다.

 

3. stack에 남아있는 값을 ans에 추가한다.

 

코드

if __name__ == '__main__':
    cmd = input()
    stack, ans = [], []
    for ch in cmd:
        if 'A' <= ch <= 'Z':
            ans.append(ch)
        else:
            if ch == '(':
                stack.append(ch)
            elif ch == '*' or ch == '/':
                while stack and (stack[-1] == '*' or stack[-1] == '/'):
                    ans.append(stack.pop())
                stack.append(ch)
            elif ch == '+' or ch == '-' or ch == ')':
                while stack and stack[-1] != '(':
                    ans.append(stack.pop())
                if ch != ')':
                    stack.append(ch)
                else:
                    stack.pop()
    while stack:
        ans.append(stack.pop())
    print(''.join(map(str, ans)))

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!