백준 1918: 후위 표기식
https://www.acmicpc.net/problem/1918
문제 설명
중위 표기식(예: A+B*C)을 후위 표기식(예: ABC*+)으로 바꾸는 문제다.
연산자의 우선순위와 괄호 구조를 고려해 후위표기식으로 만들어야 한다.
처음 접근 방식
처음엔 “연산자 스택”과 “괄호 처리를 위한 임시 스택” 두 개를 만들어서
닫는 괄호가 나올 때마다 여는 괄호가 나올 때까지 임시 저장 후 한꺼번에 출력하는 방식으로 접근했다.
- 연산자 스택: +, -, *, / 저장
- 임시 스택: 괄호 내부의 피연산자와 연산자 임시 보관
- 여는 괄호 개수를 세기 위해 cnt 사용
이 방식으로 구현했을 때,
괄호 내부를 처리할 때는 정상적으로 작동했지만
괄호 밖의 우선순위 계산(예: A+B*C)에서 엉뚱한 답이 나왔다.
즉, 연산자 우선순위를 코드 내에서 직접 비교하지 않으면
단순히 괄호 단위로만 구분되는 구조였다.
개선 ver.
문제를 다시 살펴보면, 사실 이 문제는
“연산자 우선순위”만 잘 처리하면 괄호 두 개가 필요 없다.
핵심 규칙은 아래와 같다.
1. 피연산자는 바로 출력
2. 여는 괄호(`(`):는 바로 스택에 push
3. 닫는 괄호(`)`)는 여는 괄호가 나올 때까지 스택에서 pop → 출력
4. 연산자(+,-,*,/): 이게 중요하다.
- 스택의 맨 위 값이 우선순위가 자기보다 높거나 같으면 pop → 출력
- 자기 자신을 스택에 push
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 연산자를 담을 스택
Stack<Character> st = new Stack<>();
// 괄호 처리를 위한 임시 스택
StringBuilder ans = new StringBuilder();
char[] inputs = br.readLine().toCharArray();
for (char c : inputs) {
// 연산자일 때
// 후순위 연산자면 여는괄호 나올때까지 모두 pop
if (c == '+' || c == '-') {
while (!st.isEmpty() && st.peek() != '(') {
ans.append(st.pop());
}
st.push(c);
}
// 우선순위 연산자도 동일 우선순위일 경우 모두 pop
else if (c == '*' || c == '/') {
while (!st.isEmpty() && (st.peek() == '*' || st.peek() == '/')) {
ans.append(st.pop());
}
st.push(c);
} else if (c == '(') {
st.push(c);
}
// 닫는 괄호일 때
else if (c == ')') {
// 여는 괄호가 나올 때까지 pop
while (st.peek() != '(') {
ans.append(st.pop());
}
// 여는 괄호 제거
st.pop();
}
// 피연산자일 땐 바로 ans 저장
else {
ans.append(c);
}
}
// 남은것 비우기
while (!st.isEmpty()) {
ans.append(st.pop());
}
System.out.println(ans);
}
}
개선 과정
1. 스택 2개 → 1개
처음엔 답을 출력할 때 편리함을 위해 피연산자, 연산자를 각각 담아 관리하려 했다. 피연산자는 아예 스택에 담을 필요 없이 바로 출력하면 되는 문제였다.
2. pop 조건
처음엔 우선순위보다 높을 때만 고려해 pop했다. 하지만 A/B*C 와 같은 상황에서 AB/C* 가 나와야 하는데 ABC*/ 로 곱하기를 먼저 해버리는 상황이 발생한다. 우선순위가 같아도 앞에 있는 연산자가 우선순위를 가지므로, 같은 경우도 고려해야 한다.
회고
- 괄호 처리에 집중하다 보니 연산자 우선순위 처리를 생각하지 못해 시간이 많이 지체됐다.
- 후위표기 방식 자체에 대해 친숙하지 못해 더 오래 걸렸던 것 같다.
- 처음의 방식은 복잡하지만, 이런 시행착오 덕분에 후위표기식에 대한 알고리즘을 확실히 이해했다.