[알고리즘] 백준 - 1919번 : 후위 표기식

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

관련 알고리즘 : 차량기지 알고리즘 https://ko.wikipedia.org/wiki/%EC%B0%A8%EB%9F%89%EA%B8%B0%EC%A7%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

정답 비율 30.790%를 자랑하는 문제.

 

생각지도 못한 반례에서 계속 부딪혀서 9번만에 정답을 맞혔다...

 

 

후위표기식 문제에서 나올 수 있는 반례는 다음과 같다.

A*(B+C) = ABC+* A*B+C = AB*C+ A*B*C*D = AB*C*D* (A*B)*(C*D) = AB*CD** A*(B*C)*D = ABC**D* A+B*C-(Z/X) = ABC*+ZX/- A*((B*C)*D)*E = ABC*D**E* A*(B/C+D)-F = ABC/D+*F- D-A/B*C = D-A/B*C

 

 

문제 풀이 과정은 다음과 같다.

* 필요한 주요 자료구조 1) Stack -> 연산자를 쌓아간다. 2) StringBuilder -> 출력할 정답을 붙여간다. 3) HashMap -> 연산자(+,-,*,/)의 우선순위 값 저장.

 

* 알고리즘 과정

1) 우선 문자열을 입력받고 char형 배열로 만든다.

2) char형 배열을 반복문으로 돌린다.   2-1) 알파벳일 경우      - StringBuilder에 붙인다   2-2) '('일 경우     - Stack에 넣는다   2-3) ')'일 경우     - Stack에 있는 연산자들을 하나씩 꺼내서 StringBuilder에 붙인다.      - 이 때 '('를 만났을 경우 괄호 연산이 끝난 것이므로 중지한다.   2-4) 연산자(+,-,*,/)일 경우     2-4-1) Stack이 비어있거나 Stack의 최상단이 '('이면        - Stack에 넣는다     2-4-2) 현재 연산자가 Stack에 있는 연산자보다 우선순위일 때        - Stack에 넣는다     2-4-3) 현재 연산자가 Stack에 있는 연산자보다 같은 순위이거나 후순위일 때       - Stack이 빌 때까지 Stack에서 꺼내서 StringBuilder에 붙인다.       - 반복문에서의 스택 최상단 연산자가 '('라면 반복문을 종료한다.          (단 이 때, '('를 삭제하면 안 된다. 2-3)에서 삭제할 것이므로 '('를 남겨둔다.)          ( 관련 반례 : A*(B/C+D)-F )       - 현재 연산자가 반복문에서의 스택 최상단의 연산자보다 우선순위라면 반복문을 종료한다.          ( 관련 반례 : D-A/B*C )

3) 아직 Stack에 남아있는 연산자를 꺼내서 StringBuilder에 붙이고 String형으로 변환하여 출력한다.

 

 

 

내가 작성한 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
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));
		Stack<Character> calc = new Stack<>(); //연산자를 저장할 스택
		StringBuilder sb = new StringBuilder(); //정답 저장 문자열
		HashMap<Character, Integer> map = new HashMap<>(); //연산자 우선순위 값
		map.put('*', 2);
		map.put('/', 2);
		map.put('+', 1);
		map.put('-', 1);
		char[] inputVal = br.readLine().toCharArray(); //입력한 문자열
		for(int i=0; i<inputVal.length; i++) {
			if(Character.isAlphabetic(inputVal[i])){ //알파벳일 때
				sb.append(inputVal[i]);
			}
			else if(inputVal[i]=='(') { //여는 괄호일 때
				calc.push('(');
			}
			else if(inputVal[i]==')') { //닫는 괄호일 때
				while(!calc.isEmpty()) {
					char top = calc.pop();
					if(top=='(') {//여는 괄호를 만나면 중지
						break;
					}
					sb.append(top);
				}
			}
			else { //연산자일 때
				if(calc.isEmpty() || calc.peek()=='(') {
					//스택이 비어있거나 스택의 최상단이 여는괄호일 때
					calc.push(inputVal[i]);
				}
				else if(map.get(inputVal[i])>map.get(calc.peek())) {
					//현재 연산자가 스택에 있는 연산자보다 우선순위일 때
					calc.push(inputVal[i]);
				}
				else if(map.get(inputVal[i])<=map.get(calc.peek())) {
					//현재 연산자가 스택에 있는 연산자보다 같은 순위이거나 후순위일 때
					while(!calc.isEmpty()) {
						//그동안 쌓여온, 스택에 있는 연산자들을 비울 것임
						char top = calc.peek();
						if(top=='(') {
							//여는괄호를 만난다면 중지
							break;
						}
						else if(map.get(inputVal[i])>map.get(top)) {
							//현재 연산자가 스택 최상단의 연산자보다 우선순위일 때
							break;
						}
						sb.append(calc.pop());
					}
					calc.push(inputVal[i]); //스택에 연산자를 넣음
				}
			}
		}
		while(!calc.isEmpty()) { //아직 스택에 남아있는 연산자를 꺼냄
			sb.append(calc.pop());
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}