BOJ - 1918 후위 표기식

1918 후위 표기식 : https://www.acmicpc.net/problem/1918

---

Problem

---

Solve

꽤 복잡한 문제였다. 어떻게 건드려야할지 모르겠어서 다른 분의 풀이에서 힌트를 얻어 풀 수 있었다.

힌트는 '피연선자는 바로바로 출력하고, 연산자는 저장해라'였다.

후위연산자는 우선순위가 높은 연산자의 연산이 있을 때 피연산자의 오른쪽에 연산자를 배치하는 식으로 구성되어있다.

그렇기 때문에 피연산자가 나왔을 때는 바로 출력해주고, 연산자는 Stack에 저장해준다.

• 연산자가 +, - 일 때
  • +, - 연산자는 우선순위가 가장 낮기 때문에 stack에 저장되어있는 연산자의 우선순위와 상관없이 모든 stack의 연산자를 피연산자에 붙여준다. 그 후 해당 연산자는 stack에 저장
• 연산자가 * , / 일 때
  • 우선순위가 높은 연산자이기 때문에 이전 연산자가 +, -처럼 낮은 우선순위 연산자이면 다음 연산자 혹은 괄호 여부를 알기 위해 아무것도 하지 않고 stack에 저장된다.
  • stack.peek()가 , /처럼 동일한 연산자일 때는 stack에 저장되어있는 연산자는 연산이 가능하므로 ,/ 연산자를 피연산자 오른쪽에 붙여준다. 그 후 해당 연산자는 stack에 저장
• 괄호 일 때
  • 괄호 인 경우 괄호 안에서 연산자를 따로 관리해 주어야하므로 새 함수에서 stack을 새로 생성하여 위와 같은 과정을 수행한다.
  • 괄호 안에서 연산자 관리를 마치게 되면 닫힌괄호 )의 index를 반환하여 닫힌 괄호 다음 위치부터 연산자 관리를 할 수 있도록 해준다.
• stack이 비어있을 때
  • stack이 비어있는 경우 어떤 연산자든 상관없이 stack에 넣기만 한다.

*, / 연산자를 우선순위가 높은데 stack에 넣는 이유는, 해당 연산자 다음에 괄호가 있을 경우 괄호 안의 연산자와 연결되서 작용할 수 있기 때문이다.

---

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class 후위표기식 {
	static StringBuilder sb = new StringBuilder();
	static String problem;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		problem = br.readLine();

		Stack<Character> op = new Stack<>();
		for (int idx = 0; idx < problem.length(); idx++) {
			idx = pushAndPop(idx, op);
		}
		while(!op.isEmpty()){
			sb.append(op.pop());
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	//연산자 관리
	static int pushAndPop(int idx, Stack<Character> op) {
		char p = problem.charAt(idx);

		//피연산자 일 경우 출력
		if (p >= 'A' && p <= 'Z') {
			sb.append(p);
		}
        //괄호 인 경우 괄호안에서 연산자 관리를 할 함수 호출
        else if(p == '('){
			idx = bucketPushAndPop(idx);
		}else{
			if(!op.isEmpty()){
            	//*, / 인 경우 stack에 저장된 *, /만 피연산자에 붙여준다.
				if(p == '*' || p=='/'){
					while(!op.isEmpty() && (op.peek() == '*' || op.peek() == '/')){
						sb.append(op.pop());
					}
					op.push(p);
				}
                //+, - 연산자는 stack에 저장된 모든 연산자를 피연산자에 붙여준다.
                else{
					while(!op.isEmpty()){
						sb.append(op.pop());
					}
					op.push(p);
				}
			}else{
				op.push(p);
			}
		}

		return idx;
	}

	//괄호가 있을때 연산자 관리
	static int bucketPushAndPop(int idx){
    	//열린괄호 다음 index
		idx++;

		//괄호 안에서 연산자를 관리할 새로운 Stack
		Stack<Character> op = new Stack<>();
        //닫힌 괄호가 생길때까지 연산관리
		while(idx < problem.length() && problem.charAt(idx) != ')'){
			char p = problem.charAt(idx);
            //괄호안에 괄호가 생성되면 새로운 괄호 연산자 함수 호출
			if(p == '('){
				idx = bucketPushAndPop(idx);
			}else if(p!=')'){
				pushAndPop(idx, op);
			}

			idx++;
		}
		while(!op.isEmpty()){
			sb.append(op.pop());
		}

		//닫힌 괄호의 index
		return idx;
	}
}

---

Result

---

Reference

https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-1918-%ED%9B%84%EC%9C%84-%ED%91%9C%EA%B8%B0%EC%8B%9D-JAVA%EC%9E%90%EB%B0%94