[Java] BOJ 1918번 후위 표기식

1918번: 후위 표기식

---

풀이

우선 연산자별 우선순위를 정하고 스택을 사용하여 해결했습니다.

---

코드

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

public class Main {
	public static Map<Character, Integer> opPriority, innerOpPriority;
	public static Stack<Character> stk;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		
		String input = br.readLine();
		stk = new Stack<>();
		
		// 연산자 우선순위를 설정
		opPriority = new HashMap<>();
        opPriority.put('(', 3);
		opPriority.put('*', 2);
		opPriority.put('/', 2);
		opPriority.put('+', 1);
		opPriority.put('-', 1);
		
		innerOpPriority = new HashMap<>();
		innerOpPriority.put('*', 2);
		innerOpPriority.put('/', 2);
		innerOpPriority.put('+', 1);
		innerOpPriority.put('-', 1);
		innerOpPriority.put('(', 0);
		
		for (int i = 0; i < input.length(); ++i) {
			char cur = input.charAt(i);
			
			if (cur >= 'A' && cur <= 'Z') {
				sb.append(cur);
				continue;
			}
			
			if (cur == ')') {
				while (stk.peek() != '(') {
					sb.append(stk.pop());
				}
				if (!stk.isEmpty()) {
					stk.pop();					
				}
				continue;
			}
			
			while (!stk.isEmpty() && innerOpPriority.get(stk.peek()) >= opPriority.get(cur)) {
				sb.append(stk.pop());
			}
			stk.push(cur);
		}
		
		while (!stk.isEmpty()) {
			sb.append(stk.pop());
		}
		
		System.out.println(sb);
	}
}

---

GitHub - pyo7410/Algorithm: 1일 1커밋을 목표로!