사용자 도구

사이트 도구


ps:problems:boj:1918

후위 표기식

ps
링크acmicpc.net/…
출처BOJ
문제 번호1918
문제명후위 표기식
레벨골드 4
분류

스택

시간복잡도O(n)
인풋사이즈n<=100
사용한 언어Python
제출기록29088KB / 76ms
최고기록52ms
해결날짜2020/11/24
  • 스택을 처음 배울 때 연습문제로 자주 등장하는 문제

풀이

  • 유명한 문제라서 해설이 여기저기 많다. 여기는 그냥 검색해서 나온 곳이지만 해설로는 충분.

코드

"""Solution code for "BOJ 1918. 후위 표기식".

- Problem link: https://www.acmicpc.net/problem/1918
- Solution link: http://www.teferi.net/ps/problems/boj/1918
"""


PRIORTY_BY_OPERATOR = {'(': -1, '+': 1, '-': 1, '*': 2, '/': 2}


def main():
    infix = input()
    stack = []
    postfix = []
    for ch in infix:
        if ord('A') <= ord(ch) <= ord('Z'):
            postfix.append(ch)
        elif ch == ')':
            while stack[-1] != '(':
                postfix.append(stack.pop())
            stack.pop()
        elif ch == '(':
            stack.append(ch)
        else:
            priority = PRIORTY_BY_OPERATOR[ch]
            while stack and PRIORTY_BY_OPERATOR[stack[-1]] >= priority:
                postfix.append(stack.pop())
            stack.append(ch)
    postfix.extend(reversed(stack))
    print(''.join(postfix))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
T I J N R
 
ps/problems/boj/1918.txt · 마지막으로 수정됨: 2020/11/27 13:12 저자 teferi