💡 문제
![](https://velog.velcdn.com/images/longbright_choi/post/f2cc88c4-b4e8-4b49-8143-016217eeeec7/image.png)
![](https://velog.velcdn.com/images/longbright_choi/post/1eaf8b4a-7eec-4f0d-bb8b-0dbe74b5e857/image.png)
💬 입출력 예시
![](https://velog.velcdn.com/images/longbright_choi/post/fc62eea9-fc7c-4411-9eed-406d433556ae/image.png)
📌 풀이(소스코드)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String s = br.readLine();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (!stack.isEmpty()) {
if (stack.peek() == '(') {
stack.pop();
break;
}
sb.append(stack.pop());
}
} else if (c == '*' || c == '/' || c == '+' || c == '-') {
while (!stack.isEmpty()) {
if (getPriority(stack.peek()) > getPriority(c)) {
break;
}
sb.append(stack.pop());
}
stack.push(c);
} else {
sb.append(c);
}
}
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
System.out.println(sb);
}
private static int getPriority(char op) {
if (op == '(' || op == ')') {
return 3;
} else if (op == '*' || op == '/') {
return 1;
} else if (op == '+' || op == '-') {
return 2;
}
return -1;
}
}
📄 해설
접근
Character
타입의 스택을 사용하여 해결하는 문제이다.
- 피연산자는 바로 출력하고, 여는 괄호는 스택에 넣고 닫는 괄호를 만나면 여는 괄호를 찾을 때까지 모든 원소를 출력한다.
- 연산자의 경우도 스택에 추가한다. 이때, 스택의 탑이 현재 연산자보다 높은 우선순위를 가진다면 스택이 빌때까지 전부 다 출력한다.
- 문자열 순회 끝나고 난 다음에 마지막에 추가된 연산자가 있을 수 있으니 한번 더 스택이 빌때까지 전부 다 출력한다.
과정
Character
타입의 스택을 하나 선언하고, 입력 받은 문자열을 순회한다.
- 여는 괄호를 만난 경우, 스택에 추가한다.
- 닫는 괄호를 만난 경우, 스택이 빌때까지 스택의 모든 원소를 출력한다. 이때, 여는 괄호를 만나면 반복을 종료한다ㅏ.
- 연산자의 경우, 스택의 탑이 현재 연산자보다 높은 우선순위를 가진다면 스택이 빌 때까지 출력한다. 낮은 우선순위라면 반복을 종료한다. 현재 연산자를 스택에 넣는다.
- 피연산자의 경우는 그냥 바로 출력한다.
- 문자열 순회가 끝난 후에 남아있는 연산자가 존재할 수 있다. 그러므로 스택이 빌 때까지 스택 내의 원소들을 다 출력한다.