백준 1918 java - 후위 표기식(자료구조-스택)

문제, 입출력, 테스트케이스

해당 문제는 예~전에 SWEA에서 풀었던 건데 오랜만에 푸니까 시간이 좀 걸렸다... 알고리즘은 꾸준히! 뭐든지 꾸준히 ㅎ는 게 생명이다!

<문제 풀이/접근과정>
1. 연산자 우선순위 할당
2. 연산자 stack 생성 
3. 숫자는 바로 출력
4. 연산자 우선순위 비교 후 낮은 걸 만나거나 더이상 쌓을 연산자가 없으면 pop 
5. 괄호 처리 - ( 일때는 stack에 push해 두고 )를 만나면 ( 전까지의 모든 연산자를 pop

<소스코드>

package 자료구조;

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

public class boj_1918_후위표기식 {
	public static void main(String[] args) throws IOException {
		// (, )
		// *, /
		// +, - 
//		1. 연산자 우선순위 할당
//		2. 연산자 stack 생성 
//		3. 숫자는 바로 출력
//		4. 연산자 우선순위 비교 후 낮은 걸 만나거나 더이상 쌓을 연산자가 없으면 pop 
//		5. 괄호 처리 - ( 일때는 stack에 push해 두고 )를 만나면 ( 전까지의 모든 연산자를 pop

		Stack<String> op = new Stack<>();
		String answer = "";
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String tmp[] = br.readLine().split("");
		
		for (int i = 0; i < tmp.length; i++) {
			String value = tmp[i];
			if('A' <= value.charAt(0) && value.charAt(0) <= 'Z' ) {
				answer += value;
			}else {
				if(value.equals("-") || value.equals("+") || value.equals("*") || value.equals("/")) {
					if(!op.isEmpty()) { // 연산자가 존재한다면
						if(priorityOfOperator(op.peek()) < priorityOfOperator(value)){ // 들어온 연산자가 기존의 연산자 보다 우선순위가 높다면 
							op.push(value);
						}else { // 들어온 연산자가 기존의 연산자 보다 우선순위가 같거나 낮다면
							while(!op.isEmpty() && !op.peek().equals("(") && priorityOfOperator(op.peek()) >= priorityOfOperator(value)) {
								answer += op.pop();
							}
							op.push(value);
						}
					}else { // 존재하지 않는다면
						op.push(value);
					}
				}else if(value.equals("(")) {
					op.push(value);
				}else if(value.equals(")")){
					while(!op.peek().equals("(")) {
						answer += op.pop();
					}
					op.pop(); // ( 없애 주기
				}
			}
		}
		
		while(!op.isEmpty()) { // 다 끝난 후 남은 연산자 붙여주기
			answer += op.pop();
		}
		
		System.out.println(answer);
		
	}
	
	private static int priorityOfOperator(String op) {
		if(op.equals("(") || op.equals(")")) {
			return 2;
		}else if(op.equals("/") || op.equals("*")) {
			return 1;
		}else if(op.equals("+") || op.equals("-")) {
			return 0;
		}
		return 3;
	}
}