후위표기식 만들기

중위표기식이 입력되면 후위표기식으로 변환하는 프로그램을 작성

후위표기식은 35+ 와 같이 연산자가 피연산자 뒤에 있는 표기식

중위표기식인 3+5*2 를 후위표기식으로 표현하면 352*+

중위표기식인 (3+5)*2 를 후위표기식으로 표현하면 35+2* 

 

입력예시)

3+5*2/(7-2)

 

출력예시)

352*72-/+

---

내가 쓴 코드

import sys
#sys.stdin = open("input.txt", 'rt')

s = input()

result_stack = []
operator_stack = []
operator_dict = {'+': 0, '-': 0, '*': 1, '/': 1, '(': -1, ')': -1}

for i in range(len(s)):
    #숫자면 result_stack에 일단 넣기
    if s[i].isnumeric():
        result_stack.append(s[i])
    #연산자면 일단 넣기
    #peek한것보다 같거나 덜 중요한거면(숫자 작은거) peek한거 pop해서 result에 넣기
    elif s[i] in '+-*/(':
        #여는괄호 나오면 그냥 일단 넣어야됨
        #여는괄호 아닌 연산자 나오면 peek한거랑 계속 비교
        if operator_stack and s[i] != '(':
            while operator_dict[operator_stack[-1]]>= operator_dict[s[i]]:
                result_stack.append(operator_stack.pop())
                if not operator_stack:
                    break
        operator_stack.append(s[i])
    # ) 나오면 ( 나올때까지 연산자들 pop해서 result에 넣고 (이거는 그냥pop만
    else:
        while True:
            #여는괄호 나오면 연산자 그만 넣기
            if operator_stack[-1] == '(':
                operator_stack.pop()
                break
            else:
                result_stack.append(operator_stack.pop())




#끝나면 operator_stack에 있는거 다 pop
while operator_stack:
    result_stack.append(operator_stack.pop())

result = ''.join(result_stack)
print(result)

 

모범답안

#모범답안
import sys
sys.stdin = open("input.txt", 'rt')

a = input()
stack = []
res = ''

for x in a:
    #숫자 나오면 결과에 넣기
    if x.isdecimal():
        res+=x
    #숫자 아닌 경우
    else:
        #여는 괄호 나오면 일단 스택에 넣기
        if x =='(':
            stack.append(x)
        #우선순위 높은 연산자 나오면
        elif x == '*' or x == '/':
            #스택에 이미 연산자 있고 peek값이 같은 우선순위일때
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                #peek값 pop해서 결과에 넣기 (같은 우선순위여도 먼저 나왔다는거니까 먼저 처리)
                res += stack.pop()
            #연산자 넣기
            stack.append(x)
        #우선순위 낮은 연산자 나오면
        elif x=='+' or x == '-':
            #stack에 연산자 있고 peek값이 여는괄호가 아니면
            #무조건 자기보다 우선순위 높은것들 (같아도 먼저 나온것들)
            while stack and stack[-1] != '(':
                #높은 애들 pop해서 결과에 넣고
                #여는 괄호는 결과에 넣으면 안되니까 여는괄호 나오기 전까지
                res += stack.pop()
            #연산자 넣기
            stack.append(x)
        elif x ==')':
            #닫는괄호 나오면
            while stack and stack[-1] != '(':
                #여는 괄호 나올때까지 연산자 pop해서 결과에 넣기
                res += stack.pop()

            #여는 괄호 없애기
            stack.pop()

#stack에 남아있는 연산자 다 pop해서 결과에 넣기
while stack:
    res += stack.pop()
print(res)

 

느낀점

1. 전반적인 흐름은 비슷하나..뭔가 내가 장황하게 정리한 상황들을 깔끔하게 뽑아낸것과 같은 답안이다.
2. 그래도 점점 실력 향상이 이루어지고있는듯.!
3. 꼭 리스트를 만들어서 마지막에 join을 하거나 for문으로 출력하지말고,
문자열 result를 만들어서 +하는 방식으로 푸는것도 간단할 것 같다!

 

---

다시 풀어보기

#다시

import sys
sys.stdin = open("input.txt",'rt')
s = input()
stack = []
res = ''

for x in s:
    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)