[BOJ 1918] 후위 표기식 (Java)

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
/* 우선순위가 높거나 같은게 항상 왼쪽에 나와야 */
public class Main_BOJ_1918 {

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String exp=br.readLine();
		StringBuilder sb=new StringBuilder("");
		Stack<Character> op=new Stack<>();
		for (int i=0; i<exp.length(); i++) {
			char c=exp.charAt(i);
			if (c>='A' && c<='Z') {
				sb.append(c);
			}
			else if (c=='(') op.push(c);
			else if (c==')') {
				while (!op.isEmpty()) {
					char temp=op.pop();
					if (temp=='(') break;
					sb.append(temp);
				}
			}
			else {	
				while (!op.isEmpty()) {
					char temp=op.peek();
					if (temp=='(' || getPriority(temp)<getPriority(c)) break;	//여는 괄호 만나거나 우선순위 낮은거
					else {
						sb.append(op.pop());
					}
				}
				op.push(c);
			}
		}
		while (!op.isEmpty()) {
			sb.append(op.pop());
		}
		System.out.println(sb.toString());

	}
	
	public static int getPriority(char c) {
		if (c=='+' || c=='-') return 1;
		else return 2;
	}
	
}

처음엔 고민 많이 했다..

후위표기식과 스택에 관한 지식이 없어서 아이디어를 떠올리기 힘들었다.

 

이 문제의 포인트는

1) 숫자는 그냥 쭉 붙여주고

2) 연산자 우선순위가 높거나 같은 연산자가 스택에 들어있을 경우 그렇지 않을 때까지 계속 pop해서 답안에 붙여주고, 그 다음 스택에 연산자를 넣는다

3) 괄호의 경우, 여는 괄호는 스택에 넣어주고 닫는 괄호는 여는 괄호가 나올 때까지 쭉 pop 해주면서 답안에 붙여준다.

 

역시 자료구조를 적재적소에 잘 활용하는게 어려운 것 중 하나다..