[Python] 백준 1918번: 후위 표기식

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

1918번: 후위 표기식

 

import sys
input = sys.stdin.readline


def getPriorty(c):
    if c >= 'A' and c <= 'Z':
        return 0
    elif c == '(' or c == ')':
        return 1
    elif c == '*' or c == '/':
        return 2
    elif c == '+' or c == '-':
        return 3
    else:
        return -1


if __name__ == '__main__':
    infixNotation = str(input().rstrip())

    postfixNotation = []
    stack = []

    for c in infixNotation:
        priority = getPriorty(c)

        # 문자열
        if priority == 0:
            postfixNotation.append(c)
        # ()
        elif priority == 1:
            if c == '(':
                stack.append(c)
            elif c == ')':
                if stack:
                    cur = stack[-1]
                    # 괄호가 끝날 때까지, 스택을 모두 꺼냄
                    while stack and cur != '(':
                        cur = stack.pop()
                        postfixNotation.append(cur)
        # */+-
        else:
            # 스택이 비었거나, 현재의 우선순위가 높을 경우
            if len(stack) == 0 or getPriorty(stack[-1]) > priority:
                stack.append(c)
            else:
                # 우선순위가 더 높은 스택들을 모두 꺼냄
                while stack and stack[-1] != '(' and getPriorty(stack[-1]) <= priority:
                    postfixNotation.append(stack.pop())
                stack.append(c)

    # 남아있는 모든 스택을 꺼냄
    while stack:
        postfixNotation.append(stack.pop())

    # 출력
    for c in postfixNotation:
        if c != '(':
            print(c, end="")

 

먼저, 우선순위는 다음과 같다.

이것을 기준으로 입력 받은 값에 대해 for문을 돌아주면서 진행한다.

stack은 후위 표기식을 위한 스택이며, postfixNotation은 출력할 후위 표기식이다.

 

우선 문자열일 경우에는 무조건 postfixNotation에 push한다.

다음으로 괄호일 경우이다. 여는 괄호일 경우에는 스택에 넣어주고, 닫는 괄호일 경우에는, 스택을 계속해서 pop하여 postfixNotation에 넣어주는데, 이것을 여는 괄호를 만날 때까지 반복한다.

마지막으로 일반적인 연산자의 경우(*, /, +, -)이다. 스택이 비었거나, 현재 문자의 우선순위가 스택의 윗부분보다 높을 경우에는, 스택에 현재 문자를 넣어준다. 그렇지 않을 경우에는, 우선순위가 더 높거나 같은 스택들을 모두 꺼낸다. 해당 연산을 수행한 뒤에 해당하는 연산자를 스택에 넣어주면 된다.

 

이렇게 문자열에 대한 반복문이 끝나면, 스택에 남아있는 연산자들을 모두 postfixNotation에 넣어준다. 마지막으로 postfixNotation를 괄호만 제외하고, 출력해주면 된다.