[알고리즘] 후위 표기식 계산

 

 

참고 - 후위 표기식 만들기

https://ttl-blog.tistory.com/629

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

 

 

 

 

 

후위 표기식을 계산하는 알고리즘은 매우 간단합니다. 

 

 

 

후위 표기식 계산법

후위 표기식의 계산에는 스택을 사용하는 것이 쉽고 효율적입니다.

과정은 다음과 같습니다.

 

• 연산자가 나타날 때까지 스택에 연산값(피연산자)을 삽입합니다.
• 연산자가 나타나면 다음 과정을 진행합니다.
  • 스택에서 연산자에 필요한 수 만큼의 연산값을 삭제합니다.
  • 삭제한 연산값을 사용하여 연산자를 실행
  • 연산 결과를 스택에 삽입합니다.
• 위의 과정을 후위 표기식의 마지막까지 진행하며, 이때 후위 표기식의 마지막 값을 받아 연산이 진행되었을 때, 스택의 사이즈는 1이어야 합니다. 그렇지 않다면 오류가 발생한 것입니다.

 

 

 

---

 

구현

피연산자는 무조건 한자리 숫자라고 가정하면 다음과 같이 구현할 수 있습니다.

import java.util.Arrays;
import java.util.function.BiFunction;

/**
 * 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);



    public static Operator from(char operator){
        return Arrays.stream(Operator.values())
                .filter(op -> op.getCharValue() == operator)
                .findAny().orElse(NOT_DEFINED);
    }



    public boolean isNotEqual(Operator operator){
        return !this.equals(operator);
    }


    public int getPriorityInStack() {
        return priorityInStack;
    }

    public int getPriorityAsInput() {
        return priorityAsInput;
    }

    public char getCharValue() {
        return charValue;
    }

    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);
    }

    public BiFunction<Integer, Integer, Integer> getOperate() {
        return operate;
    }

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

    private BiFunction<Integer, Integer, Integer> operate;




    Operator(char operator, int priorityInStack, int priorityAsInput, BiFunction<Integer, Integer, Integer> operate) {
        this.charValue = operator;
        this.priorityInStack = priorityInStack;
        this.priorityAsInput = priorityAsInput;
        this.operate = operate;
    }

}

 

 

import java.util.Stack;

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


    public int calculate(String postfixExpression){

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

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

            if(Character.isDigit(c)){
                stack.push(Character.getNumericValue(c));
                continue;
            }

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


            Integer pop1 = stack.pop();
            Integer pop2 = stack.pop();
            stack.push(operator.execute(pop2, pop1));// 1/2 -> 12/ 이며, 따라서 더 먼저 들어온 수를 먼저 계산해야 함

        }

        if(stack.size() != 1) throw new IllegalStateException("수식에 오류가 있습니다");
        return stack.pop();
    }

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