[백준] 1918: 후위 표기식

안녕하세요.

이번 문제는 백준의 1918번 후위 표기식 문제입니다.

골드 2 단계의 문제입니다.

 

이 문제는 너무 어려워서 약 3일정도 해당 문제만 풀었습니다. 아직 고수가 되려면 한참 멀었습니다.

 

이전 포스팅의 후위 표기식 2 문제와 비슷한 개념을 공유합니다. 

하지만 차이점은 후위 표기식 2 문제와 다르게 중위 표기식을 후위 표기식으로 만든다는 점에서 차이가 있습니다.

 

너무 많은 메모를 해가면서 풀어서, 조금 정리해서 필요한 부분만 포스팅 하고 있습니다.

코드를 작성한 시간보다, 문제의 규칙을 찾기 위해서 쓴 시간과 테스트 케이스를 직접 작성하는 시간이 훨씬 길었습니다.

제가 푼 버전은 크게 두가지가 있는데..

 

초기 버전은 40ms 로 합격했지만 가독성이 좋지 않고, 스택을 사용하는 코드지만 복잡해서 개선이 필요했습니다.

그래서 이후 검색과 다른 분들의 답을 참고해 일반적인 방식으로 풀이를 변경했고, 이게 두번째 버전이라고 할 수 있겠네요.

 

최종 코드

import sys
text=sys.stdin.readline().rstrip()
stack=[]
result=[]
priority={"+": 1, "-": 1, "*": 2, "/": 2, "(": 0}

for i in range(len(text)):
	if text[i].isalpha():
		result.append(text[i])
	elif text[i] == "(":
		stack.append("(")
	elif text[i] == ")":
		while stack and stack[-1] != "(":
			result.append(stack.pop())
			
		stack.pop()
	else:
		while stack and priority[stack[-1]] >= priority[text[i]]:
			result.append(stack.pop())
		
		stack.append(text[i])
		
while stack:
	result.append(stack.pop())
		
print(*result,sep="")

테스트 케이스 (기본 제공 테스트케이스 제외)

입력	출력
A+B+C+D+E+F	AB+C+D+E+F+
A+B*C+D/E-F	ABC*+ DE/+F-
A+B*(C+D)/E-F	ABCD+*E/+F-
(((A+(B*C))+(D/E))-F)	ABC*+DE/+F-
A+(B*C+D)/E-F	ABC*D+E/+F-
(A+B*C+D/E-F)	ABC*+ DE/+ F-
A*B*C*D	AB*C*D*
(A+B+C)	AB+C+
A*B*(C*D)	AB*CD**
A+B-C+D	AB+C-D+
A+H/R*Z/Q*S	AHR/Z*Q/S*+
A+H*R+Z	AHR*+Z+
A+H/R*Z-Q	AHR/ Z*+Q-
A*H/R*Z/Q+S	AH*R/Z*Q/S+

초반 코드

import sys

formula=sys.stdin.readline().rstrip()
operators=[]
result=[]

for i in range(len(formula)):
    if formula[i] == "(":
        operators.append([])
    elif formula[i] == ")":
        while operators[-1]:
            result.append(operators[-1].pop())

        operators.pop()
    elif formula[i].isalpha():
        result.append(formula[i])
    else:
        if len(operators) == 0:
            operators.append([])

        if formula[i] == "+" or formula[i] == "-":
            while operators[-1]:
                result.append(operators[-1].pop())

            operators[-1].append(formula[i])
        else:
            if len(operators[-1]) >= 2 or (operators[-1] and (operators[-1][-1] == "*" or operators[-1][-1] == "/")):
                result.append(operators[-1].pop())

            operators[-1].append(formula[i])

if operators:
    result.extend(reversed(operators[-1]))

print(*result,sep="")

초반 코드의 아이디어 정리

• 문자열을 만나면
  • 결과 문자열에 현재 요소를 추가한다.
• ( 를 만나면
  • 빈 배열을 괄호 스택에 추가한다
• ) 를 만나면
  • 연산자 배열의 마지막 요소를 전부 빼준다
• 연산자를 만나면
  • 여기서 우선순위 처리 필요함.
  • +-라면
    • 연산자 배열의 마지막 요소가 이미 1개 이상 들어있다면
      • 모든 요소를 빼서 결과물에 붙여주고, 현재 요소를 마지막 요소의 배열에 붙여준다.
    • 없다면
      • 마지막 연산자에 붙여준다. (append)
  • */라면
    • 연산자 배열의 마지막 요소가 2개 이상이거나, 1개인데 */ 이라면
      • 마지막 요소를 빼서 결과물에 붙여주고, 현재 요소를 마지막 요소의 배열에 붙여준다.
    • 아니라면
      • 현재 요소를 마지막 오퍼레이터 배열에 붙여준다.
• for문이 전부 끝나면 마지막 요소를 전부 빼서 붙여준다

여담

알고리즘의 아이디어 항목은 제가 편하게 쓴 내용들을 딱히 수정을 거치지 않고 올리기 때문에 보기 깔끔하지 않습니다.

사실상 정답 코드와 테스트 케이스, 놓치기 쉬운 부분 등을 공유하기 위해 쓰는게 1차 목적이고, 아이디어 부분은 부가적으로 올려두는 느낌이기 때문에 그렇네요.

이것마저 깔끔하게 정리해서 올릴 의향은 아직 없는데.. 나중에 더 고민해봐야 할 것 같습니다.

 

이번 문제에서 느낀 개인적인 교훈은..

- 일반적으로 이해하기 쉬운 방식으로 풀자. 

- 문제의 풀이 조건에 대해서 잘 정리해보자

- 문제를 차근차근 손으로 풀어보자

- 데이터 조건에 맞게 테스트 케이스를 여러개 넣어보자