[알고리즘] 후위 표기식 (백준 1918번)

1918번: 후위 표기식

 설마 이 문제 푼다고 한나절이 꼬박 걸릴지 몰랐다. 이전에 스택 활용에서 중위 표기식 → 후위 표기식 변환하는 메서드를 작성한 적이 있는지라 바로 할 수 있을 줄 알았는데 조건이 하나 더 있었다.

 연산자 간의 우선순위를 고려해야한다.

 

 즉 a+b*c 는 abc*+ 가 되어야한다. (오답 : ab+c*)

 

 처음엔 무식하게 괄호를 직접 수식에 때려박을까 했는데 결국 안되었고 온전히 스택의 순수 기능을 활용하기로 했다. 

 

Solution

1. 각 연산자의 우선순위를 저장하는 해쉬맵 order 변수 생성
   
   1. '+', '-' 의 우선순위는 0 (우선순위 낮음)
   2. '*', '/' 의 우선순위는 1 (우선순위 높음)
2. str 길이만큼 반복문
   1. c 가 알파벳이면 바로 result에 연결
   2. c 가 '(' 인 경우, stack에 push
   3. c 가 ')' 인 경우, stack에서 '('를 만날 때까지 연산자들을 pop하여서 result에 붙인다.
   4. c 가 연산자인 경우
      1. stack의 top이 '(' 아니라는 가정하에 c 보다 우선순위가 낮은 연산자를 만날 때까지 연산자들을 pop하여서 result에 붙인다.
      2. 우선순위가 낮은 연산자는 pop하면 안됨
      3. stack에 c를 push 한다.
3. 반복문 종료 후 stack에 남아있는 연산자가 없을 때까지 pop하여서 result에 붙인다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


	static void solution() throws  Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String str = br.readLine();

		Stack<Character> stack = new Stack<>();

		HashMap<Character, Integer> order = new HashMap<>();
		order.put('+',0);
		order.put('-',0);
		order.put('*',1);
		order.put('/',1);

		String result = "";

		for(int i = 0;i < str.length();i++)
		{
			char c = str.charAt(i);

			//문자(피연산자)는 바로 붙임
			if(Character.isAlphabetic(c))
				result += c;
			else if (c == ')')
			{
				char popped_c = ' ';

				while((popped_c = stack.pop()) != '(')
					result += popped_c;
			}
			else if(c =='(')
				stack.push('(');
			//연산자 만난 경우
			else
			{
				if(!stack.isEmpty() && stack.peek() != '(')
				{
					char op = ' ';

					//c보다 우선순위가 낮은 연산자가 나올 때까지 result에 붙임
					while(!stack.isEmpty() && (op = stack.peek()) != '(' && order.get(op) >= order.get(c))
						result += stack.pop();
				}

				stack.push(c);
			}
		}

		while (!stack.isEmpty())
			result+= stack.pop();

		bw.write(result);
		bw.close();
	}

	public static void main(String[] args) {

		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}


}