[백준BOJ] 1918번 후위 표기식.java

 

백준 저지에서 후위 표기식을 자바를 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

1918번 후위 표기식.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1918번 후위 표기식

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 
a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다.

중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

설명

스택을 이용하여 풀 수 있는 문제이다. 

 

중위 표기법을 후위 표기법으로 바꾸는 이유는 컴퓨터가 계산할 수 있도록 하기 위함이다. 문제와 별개로 후기 표기식을 계산할 때도 스택을 사용한다. 중위표기식 순서로 스택에 삽인된 상태라고 가정한다. peek이 기호라면 두 개의 숫자를 pop하여 기호에 맞게 계산한 후 다시 스택에 삽입한다.

 

예를 들어 "AB+"라면 peek이 +므로 A와 B를 pop하여 +기호에 맞게 계산한 후 다시 스택에 넣는다.

 

만약 "ABC+*"라면 peek이 *이므로 두 개의 숫자를 pop해야 하지만 다음 peek도 +로 기호이다. *는 pop한 상태로 보류한다. 다음 peek이 +므로 B와 C를 pop하여 덧셈 후 다시 스택에 삽입한다. 그럼 현재 스택에는 A와 B+C가 존재하고 전에 pop한 *이 보류되어있다. *기호가 있으므로 A와 B+C를 pop하고 곱한 뒤 다시 스택에 삽입한다.  

 

이와 같이 최종적으로 스택에 남은 하나의 숫자가 계산의 결과이다. 즉 중위 표기법을 후위 표기법으로 바꾸는 이유는 스택을 통해 계산식을 계산하기 위함이다.

 

 

*과 /는 +와 -보다 우선순위가 높다. 그리고 ()는 우선순위가 가장 높다. 즉 우선순위가 높은 순으로 나열하면 (), */, +-이다. 우선순위가 높다는 것은 먼저 계산된다는 것을 의미한다. 즉 문자열에서 순서상 앞에 위치해야한다. 

 

각 기호마다 우선순위를 표시하기위해 map을 사용했다.

 

숫자는 단순히 계산 대상이다. 따라서 숫자가 나오면 나온 순서대로 출력하면 된다. 중요한 것은 기호를 넣는 타이밍이다. 기호를 알맞게 넣기 위해 스택을 사용했다. 우선 순위에 따라 어떤 기호가 먼저 넣을지 결정한다.

 

스택이 비어있다면 무조건 삽입한다.

 

스택이 비어있지 않다면 스택의 top에 위치한 기호와 현재 기호를 비교한다. 만약 현재 기호의 우선 순위가 스택의 top에 위치한 기호의 우선 순위보다 같거나 낮다면 현재 스택에 있는 기호를 먼저 계산해야한다. 따라서 스택의 top에 위치한 기호를 pop하고 후위 표기식에 넣어준다. 이때 스택이 비거나 현재 기호의 우선 순위가 더 높을 때까지 반복한다. 다음 현재 기호를 스택에 삽입한다.

 

현재 기호의 우선 순위가 스택의 top에 위치한 기호의 우선 순위보다 높다면 현재 기호를 스택에 삽입한다. 후위 표기식에 들어가는 타이밍은 자신보다 낮은 우선 순위의 기호가 들어올 때, 즉 먼저 계산되어야하는 순간이다.

 

(가 들어온다면 일단 스택에 삽입하기만 한다. 다음 괄호를 다는 )기호가 들어올 때 스택의 top이 (가 될 때까지 pop하여 후위 표기식에 넣어준다. ()안에 있는 계산의 우선 순위가 가장 높기 때문이다.

 

코드

//1918번 후위 표기식.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.util.StringTokenizer;

public class 후위_표기식_1918 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static Map<String, Integer> map = new HashMap<>();
	public static void main(String[] args) throws IOException {
		map.put("(", 0);
		map.put("+", 1);
		map.put("-", 1);
		map.put("*", 2);
		map.put("/", 2);
		String cal = br.readLine();
		String answer = change(cal);
		
		System.out.println(answer);
	}
	
	static String change(String cal) {
		Stack<String> symbol = new Stack<>();
		String answer = "";
		for(int i=0;i<cal.length();i++) {
			String now = cal.substring(i,i+1);
			if(now.equals("(")) {
				symbol.add("(");
			}
			else if(now.equals(")")) {
				while(!symbol.peek().equals("(")) {
					answer += symbol.pop();
				}
				symbol.pop();
			}
			else if(now.equals("+") || now.equals("-") || now.equals("*") || now.equals("/")) {
				if(symbol.isEmpty() || map.get(symbol.peek()) < map.get(now)) {
					symbol.add(now);
				}else if(map.get(symbol.peek()) >= map.get(now)) {
					while(!symbol.isEmpty() && map.get(symbol.peek())>=map.get(now)) {
						answer += symbol.pop();
					}
					symbol.add(now);
				}
			}
			else {
				answer += now;
			}
		}
		while(!symbol.isEmpty()) {
			answer += symbol.pop();
		}
		return answer;
	}
}