링크
https://www.acmicpc.net/problem/1918
문제 설명
(정답률 36.707%)
수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.
이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+bc를 후위 표기식으로 바꾸면 abc+가 된다.
중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.
예를 들어 a+bc는 (a+(bc))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 를 괄호 밖으로 꺼내게 되면 (a+bc)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.
다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.
결과: ABC*+DE/-
이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오
입력 예제
G(A-B(C/D+E)/F)
출력 예제
GABCD/E+F/-
정답 코드
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 input = br.readLine();
Stack<Character> operator = new Stack<>();
StringBuilder sb = new StringBuilder();
for (char c : input.toCharArray()) {
//c가 피연산자라면 그대로 문자열에 추가
if (Character.isAlphabetic(c)) {
sb.append(c);
}
//c가 '('라면 스택에 추가
else if (c == '(') {
operator.push(c);
}
//c가 ')'라면
else if (c == ')') {
//스택이 비어있지 않다면
//스택의 최상단 데이터가 '('라면 꺼내고
//문자열에 추가한 뒤 pop
while (!operator.isEmpty()) {
if (operator.peek() == '(') {
operator.pop();
break;
}
sb.append(operator.pop());
}
}
//c가 나머지 연산자일 경우
else {
//스택이 비어있지 않고 c가 스택의 최상단 데이터보다 우선순위가 낮거나 같은 경우
//문자열에 추가한 뒤 pop
while (!operator.isEmpty() &&
priority(operator.peek()) >= priority(c)) {
sb.append(operator.pop());
}
operator.push(c);
}
}
//스택에 남아있는 연산을 모두 꺼낸다
while (!operator.isEmpty()) {
sb.append(operator.pop());
}
System.out.println(sb);
}
//우선 순위 결정 메소드
static int priority(char temp) {
if (temp == '*' || temp == '/')
return 2;
else if (temp == '+' || temp == '-')
return 1;
else
return 0;
}
}정리
두번째로 시도한 골드 문제인데..
거의 4시간 가까이 시간을 투자했는데
거의 풀어가는가 싶다가도 예제의 간단한 연산이나 반례들은 답이 나왔으나
괄호가 여러개 있거나 괄호안에 연산이 여러개 있을 경우는 도저히 답이 나오지 않았다.
하.. 골드 3, 4도 못 풀었었는데 뭔 골드 2를 푼다고 그 시간을 날렸을까
현재 알고리즘 기초 1/2를 풀고 있었는데
앞으로 골드 문제는 패스하면서 풀어야겠다..
1~2시간 걸려도 못풀면 그냥 구글링을 해보고 풀이를 보고 공부를 하거나 하면 되는데
이놈의 성격상 내 손으로 못풀면 화딱지가 너무 나서..
구글링을 해보니 풀이들이 거의 동일한 것을 보니 정형화된 풀이가 있었다.
차량기지 알고리즘이라고 하는거 같다.
