๐ŸŸฐ ํ›„์œ„ ํ‘œ๊ธฐ์‹

๋ฐฑ์ค€ Gold2

ํ›„์œ„ ํ‘œ๊ธฐ์‹

๋ฌธ์ œ


์ˆ˜์‹์€ ์ผ๋ฐ˜์ ์œผ๋กœ 3๊ฐ€์ง€ ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ์—ฐ์‚ฐ์ž๊ฐ€ ํ”ผ์—ฐ์‚ฐ์ž ๊ฐ€์šด๋ฐ ์œ„์น˜ํ•˜๋Š” ์ค‘์œ„ ํ‘œ๊ธฐ๋ฒ•(์ผ๋ฐ˜์ ์œผ๋กœ ์šฐ๋ฆฌ๊ฐ€ ์“ฐ๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค), ์—ฐ์‚ฐ์ž๊ฐ€ ํ”ผ์—ฐ์‚ฐ์ž ์•ž์— ์œ„์น˜ํ•˜๋Š” ์ „์œ„ ํ‘œ๊ธฐ๋ฒ•(prefix notation), ์—ฐ์‚ฐ์ž๊ฐ€ ํ”ผ์—ฐ์‚ฐ์ž ๋’ค์— ์œ„์น˜ํ•˜๋Š” ํ›„์œ„ ํ‘œ๊ธฐ๋ฒ•(postfix notation)์ด ๊ทธ๊ฒƒ์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์ค‘์œ„ ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ํ‘œํ˜„๋œ a+b๋Š” ์ „์œ„ ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ๋Š” +ab์ด๊ณ , ํ›„์œ„ ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ๋Š” ab+๊ฐ€ ๋œ๋‹ค.

์ด ๋ฌธ์ œ์—์„œ ์šฐ๋ฆฌ๊ฐ€ ๋‹ค๋ฃฐ ํ‘œ๊ธฐ๋ฒ•์€ ํ›„์œ„ ํ‘œ๊ธฐ๋ฒ•์ด๋‹ค. ํ›„์œ„ ํ‘œ๊ธฐ๋ฒ•์€ ์œ„์—์„œ ๋งํ•œ ๋ฒ•๊ณผ ๊ฐ™์ด ์—ฐ์‚ฐ์ž๊ฐ€ ํ”ผ์—ฐ์‚ฐ์ž ๋’ค์— ์œ„์น˜ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ์ด ๋ฐฉ๋ฒ•์˜ ์žฅ์ ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ์šฐ๋ฆฌ๊ฐ€ ํ”ํžˆ ์“ฐ๋Š” ์ค‘์œ„ ํ‘œ๊ธฐ์‹ ๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š” ๋ง์…ˆ๊ณผ ๊ณฑ์…ˆ์˜ ์šฐ์„ ์ˆœ์œ„์— ์ฐจ์ด๊ฐ€ ์žˆ์–ด ์™ผ์ชฝ๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ ๊ณ„์‚ฐํ•  ์ˆ˜ ์—†์ง€๋งŒ ํ›„์œ„ ํ‘œ๊ธฐ์‹์„ ์‚ฌ์šฉํ•˜๋ฉด ์ˆœ์„œ๋ฅผ ์ ์ ˆํžˆ ์กฐ์ ˆํ•˜์—ฌ ์ˆœ์„œ๋ฅผ ์ •ํ•ด์ค„ ์ˆ˜ ์žˆ๋‹ค. ๋˜ํ•œ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ด„ํ˜ธ ๋“ฑ๋„ ํ•„์š” ์—†๊ฒŒ ๋œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด a+bc๋ฅผ ํ›„์œ„ ํ‘œ๊ธฐ์‹์œผ๋กœ ๋ฐ”๊พธ๋ฉด abc+๊ฐ€ ๋œ๋‹ค.

์ค‘์œ„ ํ‘œ๊ธฐ์‹์„ ํ›„์œ„ ํ‘œ๊ธฐ์‹์œผ๋กœ ๋ฐ”๊พธ๋Š” ๋ฐฉ๋ฒ•์„ ๊ฐ„๋‹จํžˆ ์„ค๋ช…ํ•˜๋ฉด ์ด๋ ‡๋‹ค. ์šฐ์„  ์ฃผ์–ด์ง„ ์ค‘์œ„ ํ‘œ๊ธฐ์‹์„ ์—ฐ์‚ฐ์ž์˜ ์šฐ์„ ์ˆœ์œ„์— ๋”ฐ๋ผ ๊ด„ํ˜ธ๋กœ ๋ฌถ์–ด์ค€๋‹ค. ๊ทธ๋Ÿฐ ๋‹ค์Œ์— ๊ด„ํ˜ธ ์•ˆ์˜ ์—ฐ์‚ฐ์ž๋ฅผ ๊ด„ํ˜ธ์˜ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์˜ฎ๊ฒจ์ฃผ๋ฉด ๋œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด a+bc๋Š” (a+(bc))์˜ ์‹๊ณผ ๊ฐ™๊ฒŒ ๋œ๋‹ค. ๊ทธ ๋‹ค์Œ์— ์•ˆ์— ์žˆ๋Š” ๊ด„ํ˜ธ์˜ ์—ฐ์‚ฐ์ž ๋ฅผ ๊ด„ํ˜ธ ๋ฐ–์œผ๋กœ ๊บผ๋‚ด๊ฒŒ ๋˜๋ฉด (a+bc)๊ฐ€ ๋œ๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ ๋˜ +๋ฅผ ๊ด„ํ˜ธ์˜ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๊ณ ์น˜๋ฉด abc*+๊ฐ€ ๋˜๊ฒŒ ๋œ๋‹ค.

๋‹ค๋ฅธ ์˜ˆ๋ฅผ ๋“ค์–ด ๊ทธ๋ฆผ์œผ๋กœ ํ‘œํ˜„ํ•˜๋ฉด A+B*C-D/E๋ฅผ ์™„์ „ํ•˜๊ฒŒ ๊ด„ํ˜ธ๋กœ ๋ฌถ๊ณ  ์—ฐ์‚ฐ์ž๋ฅผ ์ด๋™์‹œํ‚ฌ ์žฅ์†Œ๋ฅผ ํ‘œ์‹œํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋œ๋‹ค.

image

์ด๋Ÿฌํ•œ ์‚ฌ์‹ค์„ ์•Œ๊ณ  ์ค‘์œ„ ํ‘œ๊ธฐ์‹์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ํ›„์œ„ ํ‘œ๊ธฐ์‹์œผ๋กœ ๊ณ ์น˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค

์ž…๋ ฅ


์ฒซ์งธ ์ค„์— ์ค‘์œ„ ํ‘œ๊ธฐ์‹์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹จ ์ด ์ˆ˜์‹์˜ ํ”ผ์—ฐ์‚ฐ์ž๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ง€๋ฉฐ ์ˆ˜์‹์—์„œ ํ•œ ๋ฒˆ์”ฉ๋งŒ ๋“ฑ์žฅํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  -A+B์™€ ๊ฐ™์ด -๊ฐ€ ๊ฐ€์žฅ ์•ž์— ์˜ค๊ฑฐ๋‚˜ AB์™€ ๊ฐ™์ด *๊ฐ€ ์ƒ๋žต๋˜๋Š” ๋“ฑ์˜ ์ˆ˜์‹์€ ์ฃผ์–ด์ง€์ง€ ์•Š๋Š”๋‹ค. ํ‘œ๊ธฐ์‹์€ ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž์™€ +, -, *, /, (, )๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ๊ธธ์ด๋Š” 100์„ ๋„˜์ง€ ์•Š๋Š”๋‹ค.

์ถœ๋ ฅ


์ฒซ์งธ ์ค„์— ํ›„์œ„ ํ‘œ๊ธฐ์‹์œผ๋กœ ๋ฐ”๋€ ์‹์„ ์ถœ๋ ฅํ•˜์‹œ์˜ค

์˜ˆ์ œ ์ž…๋ ฅ 1

A*(B+C)

์˜ˆ์ œ ์ถœ๋ ฅ 1

ABC+*

์˜ˆ์ œ ์ž…๋ ฅ 2

A+B

์˜ˆ์ œ ์ถœ๋ ฅ 2

AB+

์˜ˆ์ œ ์ž…๋ ฅ 3

A+B*C

์˜ˆ์ œ ์ถœ๋ ฅ 3

ABC*+

์˜ˆ์ œ ์ž…๋ ฅ 4

A+B*C-D/E

์˜ˆ์ œ ์ถœ๋ ฅ 4

ABC*+DE/-

๐Ÿ“– ๊ฐ€์ ธ๋‹ค ์“ฐ๊ธฐ

์Šคํƒ

๐Ÿ“ ๊ณผ์ • ์„ค๊ณ„/๊ด€๋ฆฌ

๋…ธํŠธ๋ถ-27 ๋…ธํŠธ๋ถ-28

๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป CODE

import sys
input = sys.stdin.readline

def solution(s):
    answer = ""
    stack = []

    for letter in s:
        # ์šฐ์„ ์ˆœ์œ„ 0. ์•ŒํŒŒ๋ฒณ
        if letter.isalpha():
            answer += letter
        
        # ์šฐ์„ ์ˆœ์œ„ 1. ์—ฌ๋Š” ์†Œ๊ด„ํ˜ธ
        if letter == '(':
            stack.append(letter)
        
        # ์šฐ์„ ์ˆœ์œ„ 2. ๊ณฑ์…ˆ ๋‚˜๋ˆ—์…ˆ
        if letter == '*' or letter == '/':
            while stack and stack[-1] != '(' and (stack[-1] == '*' or stack[-1] == '/'):
                answer += stack.pop()
            stack.append(letter)
        
        # ์šฐ์„ ์ˆœ์œ„ 3. ๋ง์…ˆ ๋บ„์…ˆ
        if letter == '+' or letter == '-':
            while stack and stack[-1] != '(':
                answer += stack.pop()
            stack.append(letter)
        
        # ์šฐ์„ ์ˆœ์œ„ 4. ๋‹ซ๋Š” ์†Œ๊ด„ํ˜ธ
        if letter == ')':
            while stack and stack[-1] != '(':
                answer += stack.pop()
            stack.pop()
    
    # ๋‚จ๋Š” ์Šคํƒ ํ„ธ์–ด๋‚ด๊ธฐ
    while stack:
        answer += stack.pop()

    return answer


s = input()
print(solution(s))

ยฉ 2022. All rights reserved.

Powered by Hydejack v9.1.6