알고리즘
백준 1918번 후위 표기식 (JAVA)
박카스마시며코딩
2022. 4. 15. 16:47
https://www.acmicpc.net/problem/1918
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
대략적인 개념은 가지고 있었는데 막상 구현하려하니 힘들었습니다.
저는 스택을 이용해 후위 표기법을 표현하였습니다.
먼저 우선순위는 (+ , -) < (* , /)입니다.
저는 다음과 같은 과정을 가지고 수행하였습니다.
1. 알파벳의 경우 StringBuilder에 바로 넣어주었습니다.
2. Stack의 top이 현재 연산자보다 우선순위가 낮은 연산자를 만날 때까지 pop하고 StringBuilder에 넣어주었습니다.
그리고 현재 연산자를 Stack에 넣어주었습니다. ( 만약 중간에 '(' 연산자가 나온다면 멈춥니다. )
3. '('를 만나면 바로 Stack에 넣어주었습니다.
4. ')'를 만나게 되면 ')'까지 꺼내주었습니다.
5. 마지막으로 남아있는 연산자를 모두 StringBuilder에 넣어주었습니다.
시간복잡도 : O(n)
package BOJ.ETC;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
public class BOJ_1918 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String command = br.readLine();
StringBuilder result = new StringBuilder();
Deque<Character> operation = new ArrayDeque<>();
for (int i = 0; i < command.length(); i++) {
char now = command.charAt(i);
if (isAlpha(now)) {
result.append(now);
continue;
}
if(operation.isEmpty() || now == '('){
operation.offerLast(now);
continue;
}
if(now == '+' || now == '-'){
while(!operation.isEmpty() && operation.peekLast() != '('){
result.append(operation.pollLast());
}
operation.offerLast(now);
}
if(now == ')'){
while(!operation.isEmpty() && operation.peekLast() != '('){
result.append(operation.pollLast());
}
operation.pollLast();
continue;
}
if(now == '*' || now == '/'){
while(!operation.isEmpty() && (operation.peekLast() == '*' || operation.peekLast() == '/') && operation.peekLast() != '('){
result.append(operation.pollLast());
}
operation.offerLast(now);
}
}
while (!operation.isEmpty()) {
result.append(operation.pollLast());
}
System.out.println(result.toString());
}
private static boolean isAlpha(char ch) {
if (ch >= 'A' && ch <= 'Z') {
return true;
}
return false;
}
}
참조