알고리즘 - 표기식(전위 / 중위 / 후위)

 

1. 개요

 

수식은 일반적으로 3가지로 표현한다.

① 중위 표기식(In-fix) : 우리가 평상 시 사용하는 표기방식으로 연산자가 중간에 위치한다. 예) a+b
② 전위 표기식(Pre-fix) : 연산자가 앞 쪽에 위치한다. 예) +ab
③ 후위 표기식(Post-fix) : 연산자가 뒤 쪽에 위치한다. 예) ab+

중위 표기식 개념은 우리가 편리하게 이해할 수 있기 때문에 자주 사용되는 것을 이해할 수 있다. 그러나 다른 방식은 왜 사용될까?

전위, 후위 표기식은 중위 표기식 대비 이점이 있다. 연산자의 우선 순위에 대한 고려를 추가로 하지 않고 전체 방정식을 즉시 해석할 수 있다.

예를 들어, 특정 @, # 이라는 연산자를 정의했다고 하자. 그러면 중위 표기식에서는 이들의 우선 순위를 파악하지 않으면 연산이 잘못될 수 있다.

하지만 다른 방식에서는 연산자의 위치만으로도 우선 순위를 파악할 수 있고 연산 순서를 바로 이해할 수 있다.

예를 들어, 2 $ 3 @ 5라는 연산을 하고자 한다면, $이 @보다 우선 순위에 있는 경우 전위 / 후위 표기식은 다음과 같다.

전위 표기식 : @ $ 2 3 5
후위 표기식 : 2 3 $ 5 @

이를 다시 중위 표기식으로 변경하면 ((2 $ 3) @ 5) 와 같다. 어떻게 저렇게 변환되는지는 아래에서 알아보자.

또한, 후위 표기식은 Stack(스택) 기반의 프로그램으로 바로 연산 수행이 가능하게 구조화할 수 있다는 이점이 있다.
Stack(스택)의 설명은 여기를 참조

 

 

2. 중위 표기식을 후위 표기식으로 변환하는 원리

 

변환 원리는 다음과 같다.

① 피연산자(예 : 숫자)는 바로 출력
② 연산자(+, -, /, *)는 자신보다 우선 순위가 높거나 같은 것을 Stack에서 빼고 자신을 담는다.
③ 여는 괄호 '('는 무조건 Stack에 넣는다.
④ 닫는 괄호 ')'는 '('를 찾을 때까지 스택에서 출력한다.( 여는 괄호, 닫는 괄호는 출력하지 않는다. )

 

예를 들어, 중위 표기식 ((a + b) * c) / d - e 를 가지고 테스트해보자. 

1) (a + b) 부분만 우선 살펴 보자.  a, b는 바로 출력되고 (, +는 스택에 넣은 뒤, )를 만나 ( 를 만날 때까지 연산자를 빼서 출력한다.
스택에는 여는 괄호 '('가 2개 있었으므로 하나는 남는다.

스택 : (
결과 : a b +

2) * c ) 부분 까지 살펴보자. *는 스택에 넣고 c를 출력한 뒤 )를 만났으니 *를 빼고 출력한 뒤 (를 뺀다.

스택 : 비어있음
결과 : a b + c *

3) / d - e 까지 살펴보자. /는 스택에 넣고 d는 출력, -는 기존 스택의 자신 보다 우선 순위가 높은 /를 빼고 스택에 넣고, e를 출력

스택 : -
결과 : a b + c * d / e

4) 모두 순회하였으니 스택에서 모두 빼서 출력한다.

스택 : 비어있음
결과 : a b + c * d / e -

 

 

3. 코드로 구현하기

 

package com.test;

import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();

        String infix = "( ( a + b ) * c ) / d - e";
        StringTokenizer st = new StringTokenizer(infix);

        StringBuilder sb = new StringBuilder();
        while(st.hasMoreTokens()){
            String s = st.nextToken();

            // 여는 괄호는 무조건 넣는다.
            if(s.equals("(")){
                stack.push(s);
            // 연산자라면
            } else if(s.equals("*") || s.equals("/") || s.equals("+") || s.equals("-")){

                // 스택이 비었다면 무조건 넣는다.
                if(stack.isEmpty()){
                    stack.push(s);
                // 스택이 비어있지 않는 다면
                } else {
                    // stack의 가장 최근 연산자가 우선 순위가 더 낮다면 바로 넣는다.
                    if(getPriority(stack.peek()) < getPriority(s)){
                        stack.push(s);
                    } else {
                        // 우선 순위가 더 높은게 없을 때까지 뺀다.(빼는 도중 비어버릴 수 있으니 그 예외 처리)
                        while(!stack.isEmpty() && getPriority(stack.peek()) >= getPriority(s)){
                            sb.append(stack.pop() + " ");
                        }

                        // 다 뺏으면 이제 넣는다.
                        stack.push(s);
                    }
                }
            // 닫는 괄호라면
            } else if(s.equals(")")){
                while(!stack.peek().equals("(")){
                    sb.append(stack.pop() + " ");
                }
                // 여는 괄호 제거
                stack.pop();
            // 숫자 라면
            } else {
                sb.append(s + " ");
            }
        }

        // Stack이 아직 비어있지 않을 수 있으니 모두 비운다.
        while(!stack.isEmpty()){
            sb.append(stack.pop() + " ");
        }
        System.out.println(sb);
    }

    // 연산자와 여는 괄호 우선 순위 설정
    private static int getPriority(String s){
        int ret_val = 0;
        if(s.equals("(")){
            ret_val = -1;
        } else if(s.equals("*") || s.equals("/")){
            ret_val = 1;
        }
        return ret_val;
    }
}

 

 

4. 후위 표기식을 입력하여 연산하기

 

후위 표기식이 주어졌을 때, 어떻게 다시 연산을 수행할 수 있을까?

아까 예시로 든 후위 표기식 결과를 살펴보자. 결과 : a b + c * d / e -

연산의 원리는 다음과 같다.

① 피연산자(예 : 숫자)는 스택에 넣는다.
② 연산자가 나오면 스택에서 가장 최근 피연산자 2개를 빼서 연산 후 다시 스택에 넣는다.
③ 위 과정을 반복 후, 최종 연산 마무리된 것을 스택에서 뺀다.

 

여기서 a = 10, b는 7, c는 13, d는 5, e는 1이라고 가정하고 연산을 수행한 코드를 아래와 같이 확인할 수 있다.

후위 표기식 변환 과정 코드와 함께 전체 코드는 다음과 같다.

package com.test;

import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args){
        Stack<String> stack = new Stack<>();

        String infix = "( ( a + b ) * c ) / d - e";
        StringTokenizer st = new StringTokenizer(infix);

        StringBuilder sb = new StringBuilder();
        while(st.hasMoreTokens()){
            String s = st.nextToken();

            // 여는 괄호는 무조건 넣는다.
            if(s.equals("(")){
                stack.push(s);
            // 연산자라면
            } else if(s.equals("*") || s.equals("/") || s.equals("+") || s.equals("-")){

                // 스택이 비었다면 무조건 넣는다.
                if(stack.isEmpty()){
                    stack.push(s);
                // 스택이 비어있지 않는 다면
                } else {
                    // stack의 가장 최근 연산자가 우선 순위가 더 낮다면 바로 넣는다.
                    if(getPriority(stack.peek()) < getPriority(s)){
                        stack.push(s);
                    } else {
                        // 우선 순위가 더 높은게 없을 때까지 뺀다.(빼는 도중 비어버릴 수 있으니 그 예외 처리)
                        while(!stack.isEmpty() && getPriority(stack.peek()) >= getPriority(s)){
                            sb.append(stack.pop() + " ");
                        }

                        // 다 뺏으면 이제 넣는다.
                        stack.push(s);
                    }
                }
            // 닫는 괄호라면
            } else if(s.equals(")")){
                while(!stack.peek().equals("(")){
                    sb.append(stack.pop() + " ");
                }
                // 여는 괄호 제거
                stack.pop();
            // 숫자 라면
            } else {
                sb.append(s + " ");
            }
        }

        // Stack이 아직 비어있지 않을 수 있으니 모두 비운다.
        while(!stack.isEmpty()){
            sb.append(stack.pop() + " ");
        }
        System.out.println(sb);

        // 결과 값을 다시 저장해두고 연산해보자
        // a는 10, b는 7, c는 13, d는 5, e는 1이라고 가정
        String result = "10 7 + 13 * 5 / 1 -";
        st = new StringTokenizer(result);
        Stack<Integer> stack2 = new Stack<>();

        while(st.hasMoreTokens()){
            String val = st.nextToken();
            // 연산자라면
            if(val.equals("+") || val.equals("*") || val.equals("/") || val.equals("-")){
                int n1 = stack2.pop();
                int n2 = stack2.pop();
                int op = 0;
                switch(val){
                    // 나눗셈, 뺄셈은 순서 중요(n2가 더 먼저 들어간 값임!)
                    case "*": op = n1 * n2; break;
                    case "+": op = n1 + n2; break;
                    case "/": op = n2 / n1; break;
                    case "-": op = n2 - n1; break;
                }
                stack2.push(op);
            // 숫자라면
            } else {
                stack2.push(Integer.parseInt(val));
            }
        }
        System.out.println(stack2.pop());
    }

    // 연산자와 여는 괄호 우선 순위 설정
    private static int getPriority(String s){
        int ret_val = 0;
        if(s.equals("(")){
            ret_val = -1;
        } else if(s.equals("*") || s.equals("/")){
            ret_val = 1;
        }
        return ret_val;
    }
}

 

전위 표기식으로의 변환 또한 Stack을 사용해 수행할 수 있다. 직접 코드를 짜고 테스트해보는 것도 좋은 방법이다.

관련 백준 알고리즘 문제는 다음과 같다.

후위 표기식 변환 문제 : www.acmicpc.net/problem/1918
후위 표기식 연산 문제 : www.acmicpc.net/problem/1935

 

읽어주셔서 감사합니다. 오류가 있으면 피드백 주시면 수정하겠습니다.