주의해야 할 점은 A + B + C의 경우에는 앞에 있는 +가 우선순위가 더 높기 때문에 ABC++가 아닌 (A + B) + C로 묶어서 AB+C+가 나와야 합니다.
그리고 추가로 괄호로 묶여서 제공되는 연산자의 경우에는 가장 우선순위가 높기 때문에 가장 먼저 처리해줘야 합니다.
알파벳에 해당하는 (A ~ Z)는 바로 문자열에 추가하고, 연산자(+, -, *, /)는 Stack에 저장해야 합니다.
2. 핵심 아이디어
Stack에는 연산자 들이 저장됩니다. 즉 먼저 들어온 연산자들은 아래쪽에 쌓이게 됩니다.
첫 번째 아이디어는 "("가 스택에 들어왔을 때입니다.
"("는 일단 스택에 넣어줍니다. 그다음 연산자를 받아주고, 닫는 괄호 ")"가 들어왔을 때, 괄호 내부에 있는 연산자를 뽑아주는 작업을 해야 합니다.
그 이유는 괄호 안에 있는 연산자가 어떤 연산자인지 상관없이 우선순위가 높기 때문입니다.
이때는 while에 조건을 넣어서 "("가 나올 때까지 pop을 해서 뽑아내서 정답 문자열 뒤에 붙여줍니다. 이때 "("는 정답에 포함되면 안 됩니다.
두 번째 아이디어는 이전에 스택에 들어온 연산자 중에서 나보다 우선순위가 높은 연산자가 있는지 확인해서 추출해야 합니다.
후위 표기식에서는 알파벳 뒤에는 우선순위가 높은 순서로 연산자가 붙습니다.
A + B * C 라면 우선순위가 높은 순서로 ABC*+ 이렇게 붙게 됩니다.
그래서 이미 스택에 들어온 연산자들 중에서 내가 현재 가지고 있는 연산자 보다 높은 우선순위가 존재하면 안 됩니다.
세 번째 아이디어는 수식의 모든 순회를 끝냈을 때, Stack에 남아있는 연산자들을 순서대로 추출해서 정답 문자열에 더해줘야 합니다.
3. 코드 작성
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String notation = br.readLine();
Stack<Character> operator = new Stack<>();
StringBuilder builder = new StringBuilder();
for (int i = 0; i < notation.length(); i++) {
char value = notation.charAt(i);
if (value >= 'A' && value <= 'Z') {
builder.append(value);
} else if (value == '(') {
operator.add(value);
} else if (value == ')') {
// 닫는 괄호가 나오면 여는 괄호가 나올 때까지 빼서 연산자만 추출한다. (괄호안에 연산자가 우선순위가 있기 떄문에)
while (!operator.isEmpty()) {
char popVal = operator.pop();
if (popVal == '(') {
break;
}
builder.append(popVal);
}
} else {
// 괄호가 아닌 경우에는 이전 연산자가 현재 연산자보다 우선순위가 높은지 확인 후 추출
while (!operator.isEmpty() && checkPriority(operator.peek(), value)) {
builder.append(operator.pop());
}
operator.add(value);
}
}
// 남아있을 수 있는 부분이 있어서 나머지 모두 추출해서 뒤에 붙여줌
while (!operator.isEmpty()) {
builder.append(operator.pop());
}
System.out.println(builder);
}
public static boolean checkPriority(char peekVal, char val) {
int peekValWeight = setWeight(peekVal);
int valWeight = setWeight(val);
// 같은 순위의 연산자라면 먼저 나온 것이 우선순위가 크기 때문에 등호가 필수
return peekValWeight >= valWeight;
}
public static int setWeight(char val) {
if (val == '(') return 0;
return val == '+' || val == '-' ? 1 : 2;
}
}
