후위표기식 백준 문제를 푸는데, 스택으로 하는건 학교에서 배운게 기억이 나는데 너무 가물가물했다. 이건 너무 유형적인 문제라고 생각해서 20분 고민하고 그냥 답지를 보기로 했다.
나중에 시험에서 어떤게 나올지 모르니, 스택을 언제 어떤 상황에 적용해야하는지에 대한 이유만 이 문제에서 취해가면 될 것 같다.
중위 표기식은 연산자가 피연산자 중간에 있도록 식을 표현하는 방식 => 사람이 이해하기 쉽다
후위 표기식은 연산자가 피연산자들 뒤에 나오도록 식을 표현하는 방식 => 컴퓨터가 이해하기 쉽다
우선, 후위 표기식이 어떻게 연산되길래 컴퓨터에게 유리하다는걸까? 를 이해해보자.
후위 표기법 연산 처리 방법
중위 표기식 예시: (A+(B*C))-(D/E)
=> 후위표기식 결과: ABC*+DE/-
일단은 후위표기식을 결과를 먼저 보고 연산처리방법을 보자.
우선, 연산자가 나오기 전까지 모든 피연산자들을 스택에 넣는다. 첫 연산자인 * 가 나오면 스택에 top쪽에 쌓인 피연산자 두 개를 뽑아서 연산자로 처리하고 다시 스택에 넣는다.
이 과정을 계속반복하면 끝임.
컴퓨터입장에서는 스택에 넣고 빼고 연산하고 이게 끝이다.
그러면 잘 생각해보자. 위의 후위표기식 연산 순서를 동그라미치면서 묶어보면 다음과 같다.
즉, 후위표기식에서 먼저 나오는 연산자가 먼저 스택에 있는 값들을 꺼내서 연산을 바로 수행한다. 먼저 연산이 수행된다는 것은 우선순위가 높다는 것을 의미한다.
또한, 피연산자들의 등장 순서는 중위표기식과 후위표기식이 똑같다.
=> 즉, 중위표기식에서 후위표기식으로 (앞에서부터) 바꿀때, 피연산자는 바로 출력하고, 연산자는 낮은 우선순위가 뒤에 가야한다. 따라서, 연산자가 후위표기식으로 변환될 순서가 왔을때, 그동안 나왔던 연산자들 중 아직 출력되지 않은 것들을 되짚어보며 자기 자신보다 우선순위가 높거나 그 이상(우선순위가 같은 연산자면 좌측부터 처리할거임)인 연산자들은 먼저 연산될 수 있도록 출력해야한다.
=> 여기서, 되짚어보며라는 단어를 보고 스택이라는 자료구조를 떠올려야 한다.
즉, 연산자가 나오면 일단 스택에 넣고 볼거다. 그리고 기존 스택에 있는 연산자들(아직 출력되지 않은) 중 이번에 스택에 넣어야하는 연산자보다 우선순위가 높거나 그 이상인 녀석들을 모두 스택에서 차례로 뽑아 출력해야한다. 그리고 스택에 이번 연산자를 넣어야 한다.
이때, 우리는 괄호도 신경써야 하는데, 괄호 같은 경우는 심플하다. 일단 ( 이 나오면 스택에 넣고(구분지점을 위해 넣는것임), ( 바로 다음 나오는(현재 스택 톱이 (인 경우를 말하는거임) 연산자는 스택에 일단 넣는다
=> 어떻게보면 ( 를 기점으로 가상의 스택을 다시 시작한거라고 봐도 무방하다.
그리고 ) 연산자가 나왔을때 (가 나오기 전까지 스택에서 모두 빼서 출력하면 된다. 그리고 (도 같이 빼서 얘는 출력하지마라.
=> 여기서, (를 하나의 스택바닥으로써 생각해야 한다고 했다. 이는 곧 )를 제외한 어떤 연산자가 나와도 스택에 있는 (를 제거할 수 있으면 안된다는 것을 의미하는데, 이는 곧 (가 가장 낮은 우선순위의 연산자라는 것을 의미한다.
이걸 코드화하면 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String exp = br.readLine();
System.out.println(solution(exp));
}
static HashMap<Character, Integer> opPriority = new HashMap<>();
static String solution(String exp) {
opPriority.put('(', 0);
opPriority.put('+', 1);
opPriority.put('-', 1);
opPriority.put('*', 2);
opPriority.put('/', 2);
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < exp.length(); i++) {
char ch = exp.charAt(i);
if (ch >= 'A' && ch <= 'Z') {
sb.append(ch);
} else if (ch == '(') {
stack.add('(');
} else if (ch == ')') {
while (!stack.isEmpty()) {
char curPop = stack.pop();
if (curPop == '(') break;
sb.append(curPop);
}
} else {
// 이미 그 이상인게 있으면 스택에서 지워라(= 출력해라). 이 특징 때문에 (의 우선순위를 매우 낮게 책정하는 것임.
while (!stack.isEmpty() && opPriority.get(stack.peek()) >= opPriority.get(ch)) {
sb.append(stack.pop());
}
stack.add(ch);
}
}
// 남은 연산자 다 출력. 스택은 항상 바닥부터해서 오름차순의 연산자만 남아야 함.
while (!stack.isEmpty()) {
char curPop = stack.pop();
sb.append(curPop);
}
return sb.toString();
}
}
=> 이 문제에서는 뒤로 되짚어가야 하는 상황이 발생할때 스택을 적용한다는 것을 기억하고 넘어가기로 했다. 후위표기식 변환 알고리즘을 이해하면 쉬운데 이 알고리즘을 내가 직접 찾아내는 것은 너무 어려운 것 같다. 그래도 풀었으니 한동안은 안잊을듯 싶다.
