[Design Pattern] 인터프리터(Interpreter) 패턴

인터프리터(Interpreter) 패턴

인터프리터(Interpreter) 패턴은 주어진 언어의 문법을 해석하고 평가하는 방법을 정의하는 디자인 패턴이다.

일반적으로 도메인 특화 언어(DSL: Domain-Specific Language)를 해석하는 데 사용된다.

인터프리터 패턴은 특정 언어의 문법 구조를 정의하고 해당 구조를 해석할 수 있는 클래스를 통해 표현한다.

 

Context

도메인에 맞게 해석이 필요한 정보 

 

TerminalExpression

구문에서 가장 작은 단위를 의미하며, 더 이상 해석이 필요하지 않은 표현식을 나타낸다.

 

NonTerminalExpression

하나 이상의 다른 표현식을 포함하며, 문법 규칙에 따라 더 큰 구조를 형성한다. 

 

특징

반복되는 문제 패턴을 언어 또는 문법으로 정의하고 확장할 수 있다. 

Expression과 하위 TerminalExpression & NonTerminalExpression은 마치 Composite 패턴과 같은 형태를 가진다.

인터프리터(Interpreter) 패턴 before

후위 표현식

 

예제를 이해하기 위해서는 후위 표현식(PostFix Notation)에 대해서 알아야 한다. 

 

보통 우리가 연산을 할 때는 중위 표현식을 사용한다.

1 + 2 = 3

중위 표현식은 연산자가 피연산자 사이에 있다.  

 

후위 표현식은 연산자가 피연산자 뒤에 있다.

후위 표현식: 3 4 + 5 * 

중위 표현식: (3 + 4) * 5

 

PostFixNotation

@RequiredArgsConstructor
public class PostFixNotation {
    private final String expression;
    private void calculate(){
        Stack<Integer> numbers = new Stack<>();
        for(char c : expression.toCharArray()){
            switch (c){
                case '+' -> {
                    numbers.push(numbers.pop() + numbers.pop());
                }
                case '-' -> {
                    int right = numbers.pop();
                    int left  = numbers.pop();
                    numbers.push(left - right);
                }
                default -> {
                    numbers.push(c - '0');
                }
            }
        }
        System.out.println(numbers.peek());
    }
    public static void main(String[] args) {
        PostFixNotation postFixNotation = new PostFixNotation("123+-");
        postFixNotation.calculate();
    }
}

10 이하의 숫자들의 연산을 후위 표현식으로 문자열로 받고 계산(더하기, 빼기)을 해주는 클래스이다. 

출력하면 -4가 나온다. 

 

만약 새로운 Expression이 필요하다면? 

ex) 곱하기 나누기 

 

하지만 인터프리터 패턴을 적용하면 기존 코드를 변경하지 않고 새로운 Expressions을 추가할 수 있다. 

→ OCP

인터프리터(Interpreter) 패턴 after

PostFixExpression 인터페이스

public interface PostfixExpression {
    int interpret(Map<Character, Integer> context);
}

 

VariableExpression

public class VariableExpression implements PostfixExpression{
    private final Character character;
    public VariableExpression(Character character) {
        this.character = character;
    }
    @Override
    public int interpret(Map<Character, Integer> context) {
        return context.get(character);
    }
}

VariableExpression은 단순하게 넘어온 context에 해당하는 숫자를 반환한다. 

해당 expresion은 더이상 다른 expression의 interpret(해석) 하지 않으니 Terminal Expression 이다.

트리 구조에서는 이를 리프 노드(leaf node)라고 한다. 

 

PlusExpression

public class PlusExpression implements PostfixExpression{
    private final PostfixExpression left, right;
    public PlusExpression(PostfixExpression left, PostfixExpression right) {
        this.left = left;
        this.right = right;
    }
    @Override
    public int interpret(Map<Character, Integer> context) {
        return left.interpret(context) + right.interpret(context);
    }
}

PlusExpression은 NonTerminalExpression이다. 

받아온 2개의 Expression의 해석(interpreting)이 필요하다. 

그 2개 표현식의 결과를 더해서 반환한다. 

 

MinusExpression

public class MinusExpression implements PostfixExpression{
    private final PostfixExpression left, right;
    public MinusExpression(PostfixExpression left, PostfixExpression right) {
        this.left = left;
        this.right = right;
    }
    @Override
    public int interpret(Map<Character, Integer> context) {
        return left.interpret(context) - right.interpret(context);
    }
}

마찬가지로 NonTerminalExpression 이다.

받아온 2개의 Expression의 해석(interpreting)이 필요하다. 

그 2개 표현식의 결과를 빼서 반환한다. 

 

PostfixParser

public class PostfixParser {
    private PostfixParser() {
    }
    public static PostfixExpression parse(String expression){
        Stack<PostfixExpression> expressions = new Stack<>();
        for(char c : expression.toCharArray()){
            expressions.push(getExpression(c, expressions));
        }
        return expressions.pop();
    }
    private static PostfixExpression getExpression(char c, Stack<PostfixExpression> expressions) {
        switch (c){
            case '+' -> {
                return new PlusExpression(expressions.pop(), expressions.pop());
            }
            case '-' -> {
                PostfixExpression right = expressions.pop();
                PostfixExpression left = expressions.pop();
                return new MinusExpression(left, right);
            }
            default -> {
                return new VariableExpression(c);
            }
        }
    }
}

 

parse() 메소드는 해석하려고 하는 표현식을 받는다. 

문자열의 표현식을 문자 배열로 바꾸고 순회하면서 각 문자에 해당하는 표현식을 만들어낸다. 

 

ex)

expression: x y z + -

 

→ 

x 스택에 VariableExpression으로 저장

y 스택에 VariableExpression으로 저장

z 스택에 VariableExpression으로 저장 

 

+

z, y에 해당하는 VariableExpression을 스택에서 빼서 PlusExpression을 생성하면서 2개의 expressions을 생성자 주입을 한다. 해당 PlusExpression을 스택에 넣는다. 

그럼 현재 스택에 남아있는 expressions들은 x, PlusExpression 이다.

-

x, plusExpression을 스택에서 빼서 MinusExpression을 생성하면 생성자 주입을 한다.

해당 MinusExpression을 스택에 넣는다.

 

순회가 끝났다. 

그럼 스택에 남아있는 MinusExpression을 빼서 반환한다. 

 

클라이언트

public class App {
    public static void main(String[] args) {
        PostfixExpression expression = PostfixParser.parse("xyz+-");
        int result = expression.interpret(Map.of('x', 1, 'y', 2, 'z', 3));
        System.out.println(result);
    }
}

// 출력 -> -4

클라이언트는 PostFixParser를 통해서 expression을 넘기고 PostFixExpression을 받는다. 

 

이때 받는 PostFixExpression의 계층도 

 

받는 PostfixExpression의 타입은 MinusExpression이다. 

expression.interpret(context)를 하면 주어진 맵 정보에 맞게 값을 재귀적으로 계산해서 값을 반환한다.

parse()해서 반환하는 Expression은 값(context, Map)만 바꿔서 재사용이 가능하다.

 

또한 곱하기 나누기 같은 표현식을 적용하려면 PostfixExpression을 구현하고 

유틸 클래스인 PostfixParser에 swtich case 문에 추가만 하면 끝이다. 

 

인터프리터(Interpreter) 패턴 확장

Expression의 확장은 자바 8에 도입된 람다식이나 익명 클래스를 

인터페이스 static 메소드로 정의하면 더 간편하게 확장이 가능하다. 

 

PostfixExpression

public interface PostfixExpression {
    public int interpret(Map<Character, Integer> context);
    public static PostfixExpression plusExpression(PostfixExpression left, PostfixExpression right){
        return context -> left.interpret(context) + right.interpret(context);
    }
    public static PostfixExpression minusExpression(PostfixExpression left, PostfixExpression right){
        return context -> left.interpret(context) - right.interpret(context);
    }
    public static PostfixExpression variableExpression(Character character){
        return context -> context.get(character);
    }
    public static PostfixExpression multiplyExpression(PostfixExpression left, PostfixExpression right){
       return context -> left.interpret(context) * right.interpret(context);
    }
}

곱하기인 multiplyExpression을 추가했다.

 

PostfixExpreesionFactory

@NoArgsConstructor(access = AccessLevel.PRIVATE)
public class PostfixExpressionFactory {
    public static PostfixExpression parse(String expression){
        Stack<PostfixExpression> stack = new Stack<>();
        for(Character c : expression.toCharArray()){
            stack.push(getExpression(c, stack));
        }
        return stack.pop();
    }
    private static PostfixExpression getExpression(Character c, Stack<PostfixExpression> stack) {
        switch (c){
            case '+' -> {
                return PostfixExpression.plusExpression(stack.pop(), stack.pop());
            }
            case '-' -> {
                PostfixExpression right = stack.pop();
                PostfixExpression left = stack.pop();
                return PostfixExpression.minusExpression(left, right);
            }
            case '*' -> {
                return PostfixExpression.multiplyExpression(stack.pop(), stack.pop());
            }
            default -> {
                return PostfixExpression.variableExpression(c);
            }
        }
    }
}

표현식에 맞는 PostfixExpression을 반환한다. 

해당 표현식은 재사용이 가능하다. 

 

클라이언트

public class App {
    public static void main(String[] args) {
        PostfixExpression expression = PostfixExpressionFactory.parse("xyz-+k*");
        int result = expression.interpret(Map.of('x', 5, 'y', 9, 'z', 5, 'k', 3));
        System.out.println("result = " + result);
    }
}

(x + (y - z)) * k =  (5 + (9 - 5)) * 3 = 27

출력 결과: 27

인터프리터(Interpreter) 패턴 정리

장점

자주 등장하는 문제 패턴을 언어와 문법을 정의할 수 있다. 

자주 사용하는 패턴의 Expression을 재사용 가능하다. 

기존 코드를 변경하지 않고 새로운 Expression을 추가할 수 있다. 

 

단점

복잡한 문법을 표현하려면 Expression가 Parser가 복잡해진다. 

인터프리터(Interpreter) 패턴 적용 사례

정규 표현식

public class InterpreterInJava {
    public static void main(String[] args) {
        System.out.println(Pattern.matches(".pr...", "spring"));
        System.out.println(Pattern.matches("[a-z]{6}", "spring"));
        System.out.println(Pattern.matches("bae[a-z]{3}[0-9]{4}", "baejeu1998"));
        System.out.println(Pattern.matches("\\d", "1")); // one digit
        System.out.println(Pattern.matches("\\D", "a")); // one non-digit
    }
}

 

스프링 SpEL (스프링 Expression Language)

public class InterpreterInSpring {
    @Setter @Getter
    static class Book{
        private String title;
    }
    public static void main(String[] args) {
        Book book = new Book();
        book.setTitle("spring");

        SpelExpressionParser parser = new SpelExpressionParser();
        Expression expression = parser.parseExpression("title");
        System.out.println(expression.getValue(book));
    }
}

// 출력 spring

참고자료

백기선님 디자인 패턴 강의

코딩으로 학습하는 GoF의 디자인 패턴 강의 | 백기선 - 인프런