문제 출저
https://www.acmicpc.net/problem/1918
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
문제 풀이
중위 표기식을 후위 표기식으로 바꾸는 문제입니다.
Stack을 사용하여 문제를 풀었습니다. Stack operation을 선언하여 기호들을 저장했습니다.
StringBuilder sb를 선언하여 후위 표기식을 저장했습니다.
1. 알파밧이 나오면 그대로 sb에 저장합니다.
2. ( 연산자가 나오면 operation에 저장합니다.
3. ) 연산자가 나오면 operation에서 ( 가 나올 때까지 꺼내 sb에 저장합니다. ( 은 저장하지 않습니다.
4. +, -, *, / 연산자가 나오면 operation에서 자신보다 우선 수위가 같거나 낮은 것을 전부 꺼내 sb에 저장합니다.
우선 순위 : * = / > + = -
예시 : A+B+C -> AB+C+
이 문제는 차량기지 알고리즘을 이해하시면 문제 풀이에 도움이 됩니다.
차량기지 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 차량기지 알고리즘은 중위 표기법으로 표현된 수식을 분석할 때 사용할 수 있는 알고리즘이다. 알고리즘의 결과물은 역폴란드 표기법이나 파스 트리가 될 수
ko.wikipedia.org
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String order = br.readLine();
StringBuilder sb = new StringBuilder();
Stack<Character> operation = new Stack<>();
for(int i = 0; i < order.length(); i++) {
char c = order.charAt(i);
if(Character.isAlphabetic(c)) {
sb.append(order.charAt(i));
}
else {
if(c == '(') {
operation.add(c);
}
else if(c == ')') {
while(!operation.isEmpty()) {
if(operation.peek() == '(') {
operation.pop();
break;
}
sb.append(operation.pop());
}
}
else if(c == '*' || c == '/') {
while(!operation.isEmpty()) {
if(operation.peek() == '(' || operation.peek() == ')') break;
if(operation.peek() == '+' || operation.peek() == '-') break;
if(operation.peek() == '*' || operation.peek() == '/') sb.append(operation.pop());
}
operation.add(c);
}
else if(c == '+' || c == '-') {
while(!operation.isEmpty()) {
if(operation.peek() == '(' || operation.peek() == ')') break;
sb.append(operation.pop());
}
operation.add(c);
}
}
}
while (!operation.isEmpty()) {
sb.append(operation.pop());
}
System.out.println(sb);
}
}
