[백준/1918] 후위표기식 ( java )

www.acmicpc.net/problem/1918

 

어떤 표기식보다 후위표기식을 그나마 가장 안다고 생각했는데 알고보니 제대로 안 것이 아니였다. ;;

연산자 우선순위에 따라서 결과값이 바뀌는 것인데, 제대로 고려하지 못했다.

따라서 연산자 우선순위를 고려하여서 수정하였다.

 

먼저 괄호가 있는 경우와 없는 경우로 나누어야 한다.

괄호가 있는 경우는 쉽다. 괄호가 끝나면 연사자를 stack으로 출력하면 된다.

왜냐하면 괄호는 하나의 연산단위로 계속 묶어주기 때문이다.

 

하지만 괄호가 없는 경우를 고려해야 한다. 이때 연산자 우선순위를 따져준다.

핵심은, 연산자를 계속 stack에 저장하면서 이전 stack값과 비교하는데, 현재의 자신보다 이전 연산자 우선순위가 같거나 높으면 출력한다. 예를 들어 stack의 마지막 값이 *이나 /이면 무조건 출력해준다. 어떤 연사자가 와도 *,/연산자 우선순위보다는 같거나 낮기 때문이다. 반대로 마지막 값이 +,-일때는 +,- 등 같은 순위의 연산자가 있을 때만 출력을 해줄 수 있다. 

 

package bj;

import java.util.*;

public class Main {

	public static int val(char a, char b) {
		return 0;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String line = sc.next();
		String answer = "";
		int[] charPriority = new int[48];
		charPriority['+'] = 1;
		charPriority['-'] = 1;
		charPriority['*'] = 2;
		charPriority['/'] = 2;

		Stack<Character> BracketandSign = new Stack<Character>();
		for (int i = 0; i < line.length(); i++) {

			if (line.charAt(i) == ')') {
				while (BracketandSign.size() > 0) {
					if (BracketandSign.peek() != '(') {
						answer += BracketandSign.pop();
					} else {
						BracketandSign.pop();
						break;
					}
				}
			}

			// 알파벳일 때
			else if ((line.charAt(i) >= 'a' && line.charAt(i) <= 'z')
					|| (line.charAt(i) >= 'A' && line.charAt(i) <= 'Z')) {
				answer += line.charAt(i);
			}

			// 기호일 때
			else if (line.charAt(i) == '(')
				BracketandSign.add(line.charAt(i));

			// 연산자를 받을 때 우선순위 고려할 것
			else {
				char charNow = line.charAt(i);
				while (BracketandSign.size() > 0) {
					if (BracketandSign.peek() != '(' && charPriority[BracketandSign.peek()] >= charPriority[charNow]) {
						answer += BracketandSign.pop();
					} else break;
				}
				BracketandSign.add(charNow);
			}
		}

		while (BracketandSign.size() > 0) {
			if (BracketandSign.peek() != '(') {
				answer += BracketandSign.pop();
			} else
				BracketandSign.pop();
		}

		System.out.println(answer);
	}
}