[알고리즘] 백준 1918 - 후위표기식

분류 : 자료구조

1. 문제

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

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

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+bc는 (a+(bc))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 를 괄호 밖으로 꺼내게 되면 (a+bc)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

결과: ABC*+DE/-

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

2. 입력

첫째 줄에 중위 표기식
피연산자-> 알파벳 대문자, 수식에서 한번만 등장
-가 앞에 오거나 * 생략 수식 존재 X
길이는 100을 넘지 않음

3. 풀이

1. 사직연산 간 우선순위 정하기

• = / > + = - > (
  )는 우선순위 없음

ex) *,/ 는 우선순위 2
+,-는 우선순위 1
(는 우선순위 0

2. 문자(피연산자)는 정답 문자열에 바로 붙여준다.

3. 연산자는 상황에 따라 스택에 넣어준다.
   1) 첫번째 연산자는 스택에 넣는다.
   2) 현재 연산자가 스택 top 연산자보다 우선순위가 높으면 스택에 넣는다.
   3) 현재 연산자가 스택 top 연산자보다 우선순위가 낮거나 같으면, 현재 연산자보다 top이 우선순위가 높거나 같은 연산자를 스택에서 꺼내 문자열에 붙인다.
   4) '('가 나오면 스택에 (를 넣는다.
   5) ')'가 나오면 '('가 나올 때 까지 스택에서 꺼내 문자열에 붙인다.

4. 코드

Scanner in = new Scanner(System.in);

        //입력받은 중위 식
        char[] input = in.nextLine().toCharArray();

        //연산자를 담을 스택
        Stack<Character> operation = new Stack<>();
        //후위표기식
        StringBuilder answer = new StringBuilder();

        for(int i=0; i<input.length;i++){
            //알파벳이면 문자열에 바로 붙임
            if(input[i] >= 'A' && input[i]<='Z'){
                answer.append(input[i]+"");
            }

            //연산자일 때
            else{
                //스택이 비어있을 때
                if(operation.empty()){
                    operation.push(input[i]);
                }
                else{

                    switch (input[i]){
                        //우선순위가 제일 높으므로 같은 기호들 pop
                        case '*':
                        case '/':
                            while(!operation.empty() && (operation.peek() == '*' || operation.peek() == '/')){
                                answer.append(operation.pop());
                            }
                            operation.push(input[i]);
                            break;

                            //우선순위 같거나 높은 기호들 pop
                        case '+':
                        case '-':
                            while(!operation.empty() && operation.peek()!='('){
                                answer.append(operation.pop());
                            }
                            operation.push(input[i]);
                            break;

                        case '(':
                            operation.push(input[i]);
                            break;

                            //'('가 나올 때 까지 pop
                        case ')':
                            while(!operation.empty() && operation.peek()!='('){
                                answer.append(operation.pop());
                            }
                            // (를 pop하기
                            operation.pop();
                            break;

                    }
                }

            }
        }

        while(!operation.empty()){
            answer.append(operation.pop());
        }

        System.out.println(answer);