Java AST를 사용한 계산기 구현

Sep 08, 2024

Contents

요구사항 목차 AST란?Expression을 구조화하여 AST에 저장하기 클래스 설계 ExpressionUtil.java CaculatorAST.java ExpressionNode.java OperatorNode.java Operator.java

요구사항

광주 Nhn Academy 8기 수료중에 주말 과제가 나왔습니다.

위 사진의 요구사항대로 AST를 사용해 계산기를 구현하는 과제였습니다.

먼저 AST(Abstract Syntax Tree)의 개념과 구현 방법을 실제로 적용해보고, 코드의 확장성을 고려하여 과제를 수행해보겠습니다.

제네릭을 활용해보기 위해 제가 구현한 Caculator는 제네릭을 사용해 구현되었습니다.

때문에 소수의 표현범위가 정수의 표현범위를 포함하고 있지만, 제가 구현한 계산기는 정수와 소수를 구분하자는 제한사항을 추가하여 구현하였습니다.

AST란?

AST(Abstract Syntax Tree)는 프로그래밍 언어의 문법 구조를 트리 형태로 표현한 자료구조입니다.

직독 직해를 해보면 구문을 추상화해 트리에 저장한 자료구조라고 해석되는데,

이를 사용하면 복잡한 수식이나 프로그램 구조를 계층적으로 표현할 수 있어, 코드의 의미를 쉽게 이해하고 처리할 수 있습니다.

AST는 보통 컴파일러나 인터프리터에서 소스 코드를 파싱하고 분석하는 데 사용됩니다.

실제로 우리가 IDE를 사용하면 컴파일 전에 컴파일에러가 발생하는 코드를 알려주는 편리한 기능도 AST로 구현되었다고 합니다.

또한 구현중인 이번 과제처럼 계산 용도로 사용하기도 합니다.

Expression을 구조화하여 AST에 저장하기

AST의 구조를 간단한 예시로 살펴보겠습니다:


graph TD
    A[Expression]
    B[Binary Operation]
    C[Number: 5]
    D[Binary Operation]
    E[Number: 3]
    F[Number: 2]
    G["+"]
    H["*"]
    
    A --> B
    B --> C
    B --> G
    B --> D
    D --> E
    D --> H
    D --> F

이 그림은 "5 + 3 * 2"라는 수식의 AST를 나타냅니다.

루트 노드는 전체 표현식을 나타내고, 각 연산자와 피연산자는 자식 노드로 표현됩니다. 이러한 구조를 통해 복잡한 수식도 쉽게 표현하고 계산할 수 있습니다.

1. 수식을 분석하여 최소단위로 분할

최소 단위로 쪼갠 객체들을 AST 트리에 노드로써 저장하면 될 것 같습니다.

하나의 Expression 은 최소 하나 이상의 Sub Expression으로 분할 할 수 있습니다.

1 + 2 * 3 / 4 - 5 라는 수식을 쪼개봅시다

예를들어 a = 2 * 3 , b = a / 4 , c = 1 + b , d = c - 5 … 이런식으로 하나의 수식을 여러개의 작은 수식으로 분할할 수 있습니다.

Expression은 연산자와 피 연산자로 분할 할 수 있습니다.

2 * 3 이라는 수식을 연산자와 피 연산자로 분할해봅시다.

연산자 : *

곱셈 연산자는 2항 연산자 입니다. 따라서 피 연산자는 무조건 2개가 와야합니다.

피연산자는 곱셈이 발생하는 2, 3 입니다.

또한 위에서 a = 2 * 3 , b = a / 4 처럼 a 수식의 결과값이 b 수식의 피 연산자에 해당되는 구조를 확인할 수 있습니다.

2. 트리 저장 방식

분할한 노드들을 트리에 저장할 때 어떻게 저장해야 할까요?

계산기는 사용자가 제공한 수식을 계산하는 역할이 있기 때문에, 수식을 계산하기 편한 형식으로 저장해야 합니다.

또한 요구사항에 출력을 보면 트리의 루트노드를 출력했을 때 원래 수식의 형태가 나와야 하므로, 트리는 원래 수식의 형태를 유지하고 있어야 합니다.

클래스 설계

위의 사항들을 고려하여 클래스를 정의해 봅시다.

ExpressionUtil.java


import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.Stack;

public class ExpressionUtil {

    private ExpressionUtil() {

    }
    /**
     * 중위표기식을 후위표기식으로 변경한 토큰들이 담긴 리스트 반환
     */
    public static <T extends Number> List<String> convertRpn(String infixEx, Class<T> type) throws InvalidExpressionException {
        validateExpression(infixEx, type);

        String[] tokens = infixEx.split(" ");
        List<String> rpnEx = new ArrayList<>();
        Stack<String> stack = new Stack<>();

        for (String token : tokens) {
            if (Operator.isAbsent(token)) {
                rpnEx.add(token);
            } else {
                Operator op = Operator.getOpType(token);
                while (!stack.isEmpty()) {
                    Operator nextOp = Operator.getOpType(stack.peek());
                    if (op.getPriority() >= nextOp.getPriority()) {
                        rpnEx.add(stack.pop());
                    } else break;
                }
                stack.push(token);
            }
        }

        while (!stack.isEmpty()) {
            rpnEx.add(stack.pop());
        }

        return rpnEx;
    }

    private static void validateExpression(String ex, Class<? extends Number> type) throws InvalidExpressionException {
        String[] s = ex.split(" ");

        for (int i = 0; i < s.length; i++) {

            if (i % 2 == 0){
                Optional<Number> number = convertToNumber(s[i], type);
                if (number.isEmpty())
                    throw new InvalidExpressionException("Invalid number format");
            } else {
                if (!Operator.isAbsent(s[i])) {
                    if (Operator.getOpType(s[i]).equals(Operator.DIVIDE) && i + 1 < s.length) {
                        Optional<Number> nextOperand = convertToNumber(s[i + 1], type);
                        if (nextOperand.isPresent() && nextOperand.get().doubleValue() == 0.0) {
                            throw new InvalidExpressionException("Division by zero");
                        }
                    }
                } else throw new InvalidExpressionException("Invalid operator format");
            }
        }
    }

    public static Optional<Number> convertToNumber(String data, Class<? extends Number> type) {
        try {
            if (type == Integer.class) {
                return Optional.of(Integer.valueOf(data));
            } else if (type == Double.class) {
                return Optional.of(Double.valueOf(data));
            }
        } catch (NumberFormatException e) {
            return Optional.empty();
        }

        return Optional.empty();
    }

}

ExpressionUtil 클래스는 수식에 대한 공통적인 메서드를 정의해 놓았습니다.

메서드 소개

convertRpn : 중위 표기식을 컴퓨터가 이해하기 쉬운 후위표기식 형태로 변경하는 메서드입니다.

validateExpression : 수식을 검증합니다. AST를 생성하기 전에, 사용자의 input 형식이 올바른지 확인합니다.

수식을 쪼개고 아래 3가지를 검증합니다.

1. 숫자 형식 검증 2. 지원하는 연산자인지 검증 3. Divided by zero 검증

만약 검증이 실패하면 요구사항에서 명시된대로 InvalidExpressionException 예외를 던집니다.

3. convertToNumber : 수식에 있는 String 형식의 Number를 형식에 맞게 반환하는 메서드입니다.

고려사항 & 문제

validateExpression 함수에 존재하는 몇가지 문제를 생각해봤습니다.

1. 현재 버전에서는 이항 연산자만 지원합니다.

과제에서는 아무런 문제가 없지만 만약 확장을 생각한다면 다양한 다항 연산자를 코드에 추가할때도 저 함수를 수정해서 사용할 수 있어야 합니다. 다양한 다항 연산자를 확장해서 지원하려면 Enumn Operator의 스펙에 몇항 연산자인지 알려주는 필드를 추가하고, 이에 따른 validation 규칙을 더 추가해야함.

연산자에서 두번째 피연산자가 0일때 ArithmeticException 오류가 발생하는데 이를 validation 단계에서 검증하지 못합니다.

현재 단계에서는 '/' 연산자 뒤에 나오는 피연산자가 0인 케이스만 확인하면 됨. 확장성을 생각해볼 때 계산기에 괄호 기능이 추가된다면 모든 연산자의 연산순서를 알아야 합니다.

현재 CaculatorAST 의 전체로직은 다음과 같습니다.

💡

1. 유저에가 받은 중위표기식을 검증 2. 중위표기식을 후위표기식으로 변경 3. 후위표기식으로 CaculatorAST 생성

Expression의 검증은 AST가 생성되기 전에 해야하지만, ArithmeticException을 검증할 때 AST의 인스턴스가 필요한 상황. 그래서 결론적으로 계산기에 괄호 기능을 추가했을 때 검증단계에서 ArithmeticException 을 검증하지 못하는 문제가 발생합니다.

만약 추가할 상황이 발생한다면 전체 로직의 순서를 바꿔야 하기 때문에 코드의 재사용성을 충분히 생각하고 작성하지 못했습니다.

주말과제라 시간이 별로 없었기에 이정도까지 생각하고 넘어갔습니다.

CaculatorAST.java


import java.util.List;
import java.util.Optional;
import java.util.Stack;

public class CalculatorAST<T extends Number> {

    private Class<T> type;

    private ExpressionNode root;

    public CalculatorAST(Class<T> type) {
        if (!Number.class.isAssignableFrom(type)) {
            throw new IllegalArgumentException("Type must be a subclass of Number");
        }

        this.type = type;
    }

    public ExpressionNode generateAST(List<String> rpnEx) {
        Stack<ExpressionNode> stack = new Stack<>();

        for (int i = 0; i < rpnEx.size(); i++) {
            String data = rpnEx.get(i);
            Optional<Number> number = ExpressionUtil.convertToNumber(data, type);
            if (number.isPresent()) {
                stack.push(new OperandNode(number.get()));
            } else {
                OperatorNode operatorNode = new OperatorNode(Operator.getOpType(data));
                operatorNode.right = stack.pop();
                operatorNode.left = stack.pop();
                stack.push(operatorNode);
            }
        }
        this.root = stack.pop();
        return root;
    }

    public T evaluation(ExpressionNode node) throws InvalidExpressionException {

        Class<? extends ExpressionNode> currentClass = node.getClass();
        if (currentClass.equals(OperatorNode.class)) {
            return (T) root.getValue();
        }
        throw new InvalidExpressionException("Root node is not Operator");
    }

    public ExpressionNode getRoot() {
        return this.root;
    }

}

필드 설명

Class :

CaculatorAST는 Number를 상속한 클래스를 제네릭 타입으로 받을 수 있습니다.

저는 정수와 소수를 구분하여 구현하였기에, 생성자에서 제네릭 클래스를 받아 저장하였습니다.

ExpressionNode :

AST를 이루고 있는 최상위 식을 저장하는 root를 갖습니다.

메서드 설명

generateAST :

토큰화된 후위표현식 List를 받아서 AST에 저장합니다.

피연산자는 스택에 저장하고, 연산자를 만나면 스택에서 꺼내 Expression을 생성합니다.

evaluation :

root 노드의 getValue를 호출하고 root노드는 하위 연산자 노드의 getValue를 순차적으로 호출하여 전체 수식이 완성되는 로직입니다.

ExpressionNode.java


public abstract class ExpressionNode {
    public ExpressionNode left;
    public ExpressionNode right;

    public abstract String toString();
    public abstract Number getValue() throws InvalidExpressionException;

}

추상클래스로 정의된 ExpressionNode는 좌, 우 노드를 갖습니다.

요구사항에서 정의된 출력을 수행하기 위해 toString 메서드와 결과값을 출력하기 위한 getValue 메서드를 추상메서드로 정의하였습니다.

OperatorNode.java


public class OperatorNode extends ExpressionNode{

    Operator data;
    public OperatorNode(Operator op) {
        this.left = this.right = null;
        this.data = op;
    }

    @Override
    public Number getValue() throws InvalidExpressionException {
        return data.operate(this.left.getValue(), this.right.getValue());
    }

    @Override
    public String toString() {
        String s = "";
        if (this.left != null) {
            s += this.left;
        }
        s += "," + data + ",";
        if (this.right != null) {
            s += this.right;
        }
        return "(" + s + ")";
    }
}

OperatorNode는 ExpressionNode를 상속받고, 연산자를 정의한 Enum인 Operator를 추가로 갖습니다.

Operator.java


public interface Operable<T extends Number> {
    Number operate(Number a, Number b) throws InvalidExpressionException;
}

public enum Operator implements Operable<Number>{

    PLUS("+", 1) {
        @Override
        public Number operate(Number a, Number b) {
            if (a instanceof Double || b instanceof Double) {
                return a.doubleValue() + b.doubleValue();
            } else {
                return a.intValue() + b.intValue();
            }
        }
    },
    MINUS("-", 1) {
        @Override
        public Number operate(Number a, Number b) {
            if (a instanceof Double || b instanceof Double) {
                return a.doubleValue() - b.doubleValue();
            } else {
                return a.intValue() - b.intValue();
            }
        }
    },
    MULTIPLY("*", 0) {
        @Override
        public Number operate(Number a, Number b) {
            if (a instanceof Double || b instanceof Double) {
                return a.doubleValue() * b.doubleValue();
            } else {
                return a.intValue() * b.intValue();
            }
        }
    },
    DIVIDE("/", 0) {
        @Override
        public Number operate(Number a, Number b) {
            if (a instanceof Double || b instanceof Double) {
                return a.doubleValue() / b.doubleValue();
            } else {
                return a.intValue() / b.intValue();
            }
        }
    };

    private final String value;
    private final int priority;

    Operator(String value, int priority) {
        this.value = value;
        this.priority = priority;
    }

    public static Operator getOpType(String value) {
        for (Operator op : Operator.values()) {
            if(op.value.equals(value))
                return op;
        }

        throw new RuntimeException("Not supported operator");
    }

    public static boolean isAbsent(String value) {
        for (Operator op : Operator.values()) {
            if (op.value.equals(value))
                return false;
        }

        return true;
    }

    public int getPriority() {
        return this.priority;
    }

    @Override
    public String toString() {
        return this.value;
    }
}

Operator는 연산자들의 Enum을 정의한 클래스입니다.

Operable을 상속하여 각 Enum들은 operate 함수를 정의했고, 연산자의 String값, 우선순위를 필드로 갖습니다.

이렇게 해서 AST를 사용하여 계산기를 구현해봤습니다.

제네릭을 자주 사용하지 않다가 이번에 사용해보니 개념이 부족하단걸 알았고 다시 복습해야 겠습니다.

See more posts