후위-표기식
후위 표기식
백준 1918번 문제
https://www.acmicpc.net/problem/1918
1. 문제
2. 문제 풀이
2.1 아이디어
중위 표기식을 후위 표기식으로 변경하기 위해서는 먼저 연산에 따라 괄호를 묶어주어야 한다.
예를 들어 다음과 같은 수식이 있다고 하자.
A+Bx(C-D)/E
이 수식을 연산의 우선순위에 따라 괄호로 묶어주면 다음과 같은 형태가 된다.
(A+((Bx(C-D))/E))
왼쪽부터 시작해서 연산의 우선순위를 기준으로 괄호로 묶어주었다.
이제 이 식을 괄호에 따라서 후위표기식으로 변경하면 다음과 같다.
ABCD-xE/+
중위 표기식을 후위 표기식으로 바꾸는 과정에는 규칙이 있다.
1. 피연산자는 왼쪽부터 순차적으로 출력된다.
- 피연산자의 순서는 바뀌지 않는다 연산자의 위치만 바뀔 뿐이다.
2. 연산자는 괄호가 닫히는 곳에서 역순으로 출력된다.
- 괄호를 기준으로 연산자를 피연산자의 뒤에 표기하기 때문에 닫힌 괄호에 따라 연산자가 출력된다.
따라서 우리는 수식을 괄호로 묶었을 때 괄호가 닫히는 곳을 판단하고 연산자를 역순으로 출력해 주면 된다.
괄호를 묶는 기준은 연산자의 우선순위이다.
따라서 괄호가 닫히는 지점은 다음 연산자의 우선순위가 전 연산자의 우선순위보다 같거나 낮을 때이다.
간단한 예를들어 다음과 같은 수식이 있다고 하자.
A+BxC-D
연산의 우선순위에 따라 ((A+(BxC))-D)와 같은 식으로 괄호가 형성된다.
괄호는 - 연산 전에 닫혀있다.
왜냐하면 전 연산인 x 보다 - 연산의 우선도가 낮기 때문에 앞의 연산이 우선되어 괄호가 닫히기 때문이다.
따라서 다음과 같은 방식으로 이 문제를 풀 수 있다.
1. 피연산자는 순서대로 출력한다.
2. 연산자는 stack에 저장하고 우선순위에 따라 출력한다.
- 다음 연산자의 우선순위가 stack에 저장된 연산자의 우선순위보다 커질 때까지
stack에서 연산자를 빼서 출력한다.
- 수식에 괄호가 명시된 경우 괄호의 우선순위는 가장 높다.
2.2 핵심 코드
2.2.1 priority
문자를 받아서 연산자면 우선순위를 반환하고 연산자가 아니라면 0을 반환하는 메서드이다.
[priority]
public static int priority(Character character) {
switch (character) {
case '+' :
case '-' : return 1;
case '*' :
case '/' : return 2;
default : return 0;
}
}
2.2.2 convertToPostfix
중위 표기식을 후위 표기식으로 변경해서 StringBuilder에 담는 메서드
[convertToPostfix]
private static void convertToPostfix(String formula, Deque<Character> stack, StringBuilder sb) {
for (int i = 0; i < formula.length(); i++) {
char character = formula.charAt(i);
switch (character) {
case '+' :
case '-' :
case '*' :
case '/' :
while (!stack.isEmpty() && priority(stack.peek()) >= priority(character)) {
sb.append(stack.pop());
}
stack.push(character);
break;
case ')' :
while (!stack.isEmpty() && stack.peek() != '(') {
sb.append(stack.pop());
}
stack.pop();
break;
case '(' :
stack.push(character);
break;
default:
sb.append(character);
}
}
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
}
문자가 연산자이면 Stack에 가장 위에있는 연산자와 비교해서 우선순위가 커질 때까지 Stack에서 연산자를 빼서 출력한다.
괄호가 나오면 반대 괄호가 나올때까지 Stack에서 연산자를 출력한다.
피연산자의 경우 바로 출력해준다.
3. 전체 코드
[전체 코드]
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
public class 후위_표기식_1918 {
public static int priority(Character character) {
switch (character) {
case '+' :
case '-' : return 1;
case '*' :
case '/' : return 2;
default : return 0;
}
}
private static void convertToPostfix(String formula, Deque<Character> stack, StringBuilder sb) {
for (int i = 0; i < formula.length(); i++) {
char character = formula.charAt(i);
switch (character) {
case '+' :
case '-' :
case '*' :
case '/' :
while (!stack.isEmpty() && priority(stack.peek()) >= priority(character)) {
sb.append(stack.pop());
}
stack.push(character);
break;
case ')' :
while (!stack.isEmpty() && stack.peek() != '(') {
sb.append(stack.pop());
}
stack.pop();
break;
case '(' :
stack.push(character);
break;
default:
sb.append(character);
}
}
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
Deque<Character> stack = new ArrayDeque<>();
String formula = br.readLine();
convertToPostfix(formula, stack, sb);
bw.write(sb.toString());
bw.flush();
}
}