[백준] 1918 후위 표기식 - Data Structure / Java

• 문제 링크

1918번: 후위 표기식

 

• 풀이 과정

후위 표현식을 저장할 StringBuilder 와 연산자의 우선 순위를 구하기 위해 Stack 자료구조를 활용한다.

 

입력받은 수식의 한 문자 단위로 탐색을 수행하고, 피연산자인 경우 StringBuilder 객체 sb 에 저장,

+, -, *, / 의 경우 연산자의 우선 순위를 스택의 상단의 연산자와 해당 연산자를 비교하는 priority 함수를 통해

스택에 저장할 지, 스택의 모든 연산자를 꺼내 sb 에 저장할 지 결정한다.

이때 +, - = 1 의 우선 순위, *, / = 2 의 우선 순위를 가진다.

 

( 의 경우 그대로 스택에 저장하고 이는 가장 낮은 우선 순위를 가진다.

) 의 경우 스택의 모든 연산자를 꺼내 sb 에 저장하되 스택 상단의 값이 ( 일 때까지만 수행하고 ( 은 pop() 하여 버린다.

 

탐색을 끝낸 뒤 스택에 남아있는 연산자들을 모두 꺼내 sb 에 저장하고 정답으로써 출력한다.

 

• 풀이 코드

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 Main {

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

		String input = br.readLine();

		StringBuilder sb = new StringBuilder();
		Stack<Character> stk = new Stack<>();
		for (int i = 0; i < input.length(); i++) {
			char now = input.charAt(i);

			if (now == '+' || now == '-' || now == '*' || now == '/') {
				while (!stk.empty() && priority(stk.peek()) >= priority(now))
					sb.append(stk.pop());

				stk.push(now);
			} else if (now == '(') {
				stk.push(now);
			} else if (now == ')') {
				while (!stk.empty() && stk.peek() != '(')
					sb.append(stk.pop());

				stk.pop();
			} else {
				sb.append(now);
			}
		}

		while (!stk.empty())
			sb.append(stk.pop());

		bw.write(sb + "\n");
		bw.flush();
	}

	private static int priority(char oper) {
		if (oper == '(')
			return 0;
		else if (oper == '+' || oper == '-')
			return 1;
		else
			return 2;
	}

}