[알고리즘] 후위 표기법 만들기 (Infix를 Postfix로 바꾸기)

 

 

수식의 표기법

Infix (중위 표기법)

Infix 표기법은 연산자가 연산값 사이에 들어 있으며, 연산의 순서를 지정하기 위해 괄호가 필요합니다

예시 : 3 * (7 - 5)

 

 

Prefix (전위 표기법)

Prefix 표기법은 연산자가 연산값 앞에 등장하며 괄호가 불필요합니다

예시 :  * 3 - 7 5

 

 

Postfix (후위 표기법)

Postfix 표기법은 연산자가 연산값 뒤에 등장하며 괄호가 불필요합니다.

또한 이는 컴파일러가 수식을 계산하는데 사용하는 표기법입니다.

예시 :  3 7 5 - *

 

 

 

---

 

 

Infix를 Postfix로 바꾸기

사람은 대부분 Infix 방식의 표기법이 익숙하고 편할 것입니다.

그러나 컴퓨터는 Postfix 방식의 표기법을 쉽게 이해하고 계산할 수 있기에, 컴퓨터에게 계산을 맡길 때에는 Postfix 방식으로 바꿔주어야 합니다.

이제부터 그 방법에 대해 알아보도록 하겠습니다.

 

 

아래 식으로 예시를 들어가며 살펴보겠습니다.

a / b - c + d * e - a * c

 

 

우선 Infix 방식의 수식에 괄호를 완벽하게 칩니다.

((( (a / b) - c ) + (d * e)) - ( a * c ))

 

괄호 속 연산자를 가장 오른쪽 위치로 옮깁니다.

((( (a b / ) c - )  (d  e * ) + )  ( a c * )  -  )

 

모든 괄호를 제거합니다. (완성)

a b /  c -   d  e * +   a c *   -  

 

 

 

---

 

 

스택을 사용한 변환

수식을 왼쪽에서 오른쪽으로 스캔하며, 다음 과정에 따라 진행합니다.

 

먼저 피연산자(연산값)은 나타날 때마다 바로바로 출력합니다. 

즉, 연산값들 끼리의 순서는 절대 바뀌지 않습니다.

 

 

연산자는 스택에 삽입합니다. 단 삽입 전 다음 과정을 진행합니다.

현재 스택 안에 있는 연산자 중에서, 삽입되는 연산자보다 우선순위가 높거나 같은(먼저 계산되어야 하는) 연산자들은 차례대로 스택에서 꺼내어, 출력합니다.

 

 

괄호가 있는 경우

괄호가 있는 경우에는 다음 방식을 추가합니다.

여는 괄호( '(' )를 만나면 대응되는 닫는 괄호( ')' )를 만날 때까지 그 괄호 안의 수식만 별도로 변환합니다.

 

즉 괄호를 연산자의 Stack에 집어넣는 경우에는 우선순위가 가장 높게 처리하여, 이전에 존재하던 연산자들이 빠져나가지 못하게 합니다.

또한 괄호 안의 수식을 처리하는 동안은, 즉 스택에 여는 괄호가 들어와 있는 동안은, 이후 들어오는 연산자들보다 우선 순위를 가장 낮게 판단하여, 닫는 괄호가 나타나기 전까지 괄호가 빠져나가지 못하게 막습니다.

 

닫는 괄호가 나타난 경우, 스택에서 여는 괄호를 만날 때까지 존재하는 모든 연산자를 출력합니다.

 

 

 

오른쪽우선(Right - to - Left) 결합법칙의 연산자의 경우

대부분의 연산자들을 왼쪽우선 결합법칙을 가집니다. 그러나 2^3(2의 3제곱)과 같이 오른쪽우선 연산자들도 있습니다.

또다른 예시로는 a = 3 등의 대입 연산도 오른쪽우선 연산입니다.

 

왼쪽우선 연산자의 경우에는 스택에 들어오기 전, 스택 속 연산자들과 비교할 때 우선순위를 같게 주어, 먼저 들어온 연산자가 먼저 출력되도록 하였습니다. 그러나 오른쪽우선 연산자는 이와 반대로 작동해야 합니다.

이를 해결하기 위해서, 다음과 같은 방법을 사용할 수 있습니다.

 

입력으로 들어올 때의 우선순위는 스택 안에서의 우선순위보다 높게 판단합니다.

 

 

즉 정리하면 다음과 같습니다.

연산자	스택 안에서의 우선순위	입력으로 들어올 때의 우선순위
(	0 (가장 낮음)	6
)	5	5
+	1	1
_	1	1
*	2	2
/	2	2
%	2	2
^(제곱)	3	4

 

 

 

 

 

---

 

 

 

자바로 구현

import java.util.Arrays;
import java.util.function.BinaryOperator;

/**
 * Created by ShinD on 2022-05-07.
 */
public enum Operator {

    OPEN_BRACKET('(', 0, 6, (a, b) -> 0 ),
    CLOSE_BRACKET(')', 5, 5, (a, b) -> 0 ),
    PLUS('+', 1, 1, (a, b) -> a+b ),
    MINUS('-', 1, 1, (a, b) -> a-b ),
    MULTIPLY('*', 2, 2, (a, b) -> a*b ),
    DIVIDE('/', 2, 2, (a, b) -> a/b ),
    REMAIN('%', 2,2, (a, b) -> a % b),
    SQUARED('^', 3, 4, (a, b) -> (int) Math.pow((double) a,(double) b) ),
    NOT_DEFINED( '\u0000', -1, -1 , null);

    private int priorityInStack;//스택 안에서의 우선순위
    private int priorityAsInput;//입력으로써의 우선순위
    private char charValue;
    private BinaryOperator<Integer> operate;


    public static Operator from(char operator){
        return Arrays.stream(Operator.values())
                .filter(op -> op.getCharValue() == operator)
                .findAny().orElse(NOT_DEFINED);
    }
    
    
    public int execute(int i1, int i2){
        if((this.equals(DIVIDE) || this.equals(REMAIN)) && i2 == 0){
            throw new IllegalStateException("0으로 나눔!");
        }
        return this.operate.apply(i1, i2);
    }
    
    
    Operator(char operator, int priorityInStack, int priorityAsInput, BinaryOperator<Integer>  operate) {
        this.charValue = operator;
        this.priorityInStack = priorityInStack;
        this.priorityAsInput = priorityAsInput;
        this.operate = operate;
    }
    
    
    public int getPriorityInStack() {
        return priorityInStack;
    }
    public int getPriorityAsInput() {
        return priorityAsInput;
    }
    public char getCharValue() {
        return charValue;
    }
    public BinaryOperator<Integer>  getOperate() {
        return operate;
    }



}

 

 

import java.util.Stack;

/**
 * Created by ShinD on 2022-05-07.
 */
public class InfixToPostfixTranslator {


    public String infixToPostfix(String infixExpression){
        StringBuilder postfixExpressionBuilder = new StringBuilder();
        Stack<Operator> operatorStack = new Stack<>();

        middleProcess(infixExpression, postfixExpressionBuilder, operatorStack);
        extractRemainOperatorFromStack(postfixExpressionBuilder, operatorStack);

        return postfixExpressionBuilder.toString();
    }


    private void extractRemainOperatorFromStack(StringBuilder postfixExpressionBuilder, Stack<Operator> operatorStack) {
        while (!operatorStack.isEmpty()){
            Operator pop = operatorStack.pop();
            if(Operator.OPEN_BRACKET.equals(pop)) throw new IllegalStateException();//남은 연산자에 (가 있으면 오류
            postfixExpressionBuilder.append(pop.getCharValue());
        }
    }



    private void middleProcess(String infixExpression, StringBuilder postfixExpressionBuilder, Stack<Operator> operatorStack) {
        for (int i = 0; i < infixExpression.length(); i++) {
            char character = infixExpression.charAt(i);

            if (Character.isDigit(character)) {
                postfixExpressionBuilder.append(character);
                continue;
            }

            Operator inputOperator = Operator.from(character);
            checkValid(inputOperator);//유효한 연산자인지 검사하고, 아닌 경우 예외 발생


            if (Operator.CLOSE_BRACKET.equals(inputOperator)) {//닫는 괄호가 나온 경우
                if (operatorStack.isEmpty()) throw new IllegalStateException();//스택이 비어있으면 오류
                Operator poppedOperator = operatorStack.pop();
                while (!Operator.OPEN_BRACKET.equals(poppedOperator)) {
                    postfixExpressionBuilder.append(poppedOperator.getCharValue());
                    if (operatorStack.isEmpty()) throw new IllegalStateException();
                    poppedOperator = operatorStack.pop();
                }
            }

            else {//닫는 괄호 이외의 연산자
                while (!operatorStack.isEmpty() &&
                        operatorStack.peek().getPriorityInStack() >= inputOperator.getPriorityAsInput()) {
                    postfixExpressionBuilder.append(operatorStack.pop().getCharValue());
                }
                operatorStack.push(inputOperator);
            }
        }
    }

    private void checkValid(Operator inputOperator) {
        if(Operator.NOT_DEFINED.equals(inputOperator))  throw new IllegalStateException();
    }


}