Простая арифметика

При разработке приложений бывает полезной возможность выполнить простые вычисления, по некоторой формуле, полученной в RunTime-е. Разумеется, имеется масса возможностей по встраиванию в приложение разнообразных скриптовых языков, таких как Lua и JavaScript, но часто их возможности (и накладные расходы) бывают избыточными. В этой статье мы рассмотрим простейший интерпретатор арифметических выражений.

Для начала, построим диаграмму классов (чтобы потом не заблудиться):

Итак, у нас есть два интерфейса составляющих API (IExpression и IConditionEnvironmet) и один вспомогательный интерфейс IExpressionBuilder, используемый реализацией парсера арифметических выражений. Задачей наследников IExpression является собственно вычисление выражения. Имеется три реализации этого интерфейса:

• ConstantExpression - возвращает константу
• VariableExpression - возвращает значение переменной, запрашивая его у контекста вычисления выражения IConditionEnvironment
• Operation - реализует бинарную (или унарную) операцию над операндами типа IExpression

Таким образом, нашей задачей будет распарсить строку, содержащую формулу арифметического выражения и построить дерево IExpression, которое можно будет выполнить на различных контекстах. Задачу построения этого дерева разделим на две части. Scaner выделит из исходного текста лексемы и передаст их IExpressionBuilder. Задачей наследника ExpressionParser (наследника IExpressionBuilder) будет построение дерева вычислений, с учетом приоритета операций: Реализация сканера примитивна и утомительна:

package com.WhiteRabbit.condition;

public class Scaner {
   
    private static Scaner instance = null;
   
    private Scaner() {}
   
    public static Scaner getInstance() {
        if (instance == null) {
            instance = new Scaner();
        }
        return instance;
    }
   
    private void checkPrev(IExpressionBuilder ctx, char c) throws Exception {
        switch (c) {
            case '!':
                ctx.addOperation(Operation.NOT_OP);
                break;
            case '<':
                ctx.addOperation(Operation.LT_OP);
                break;
            case '>':
                ctx.addOperation(Operation.GT_OP);
                break;
        }
    }
   
    private void checkBuf(IExpressionBuilder ctx, StringBuffer sb, boolean isVar)

    throws Exception {
        if (sb.length() != 0) {
            if (isVar) {
                ctx.addVariable(sb.toString());
            } else {
                ctx.addConstant(sb.toString());
            }
        }
        sb.setLength(0);
    }
   
    private boolean isAlphaDigit(char c) {
        switch (c) {
            case '_':
            case '.':
                return true;
            default:
                return Character.isDigit(c) || Character.isJavaIdentifierPart(c);
        }
    }
   
    public void scan(IExpressionBuilder ctx, String s) throws Exception {
        char [] chars = s.toCharArray();
        StringBuffer sb = new StringBuffer();
        boolean isVar = false;
        char prev = ' ';
        for (char c: chars) {
            switch (c) {
                case '(':
                    checkPrev(ctx, prev);
                    checkBuf(ctx, sb, isVar);
                    ctx.openBracket();
                    break;
                case ')':
                    checkPrev(ctx, prev);
                    checkBuf(ctx, sb, isVar);
                    ctx.closeBracket();
                    break;
                case '=':
                    checkBuf(ctx, sb, isVar);
                    switch (prev) {
                        case '!':
                            ctx.addOperation(Operation.NE_OP);
                            break;
                        case '<':
                            ctx.addOperation(Operation.LE_OP);
                            break;
                        case '>':
                            ctx.addOperation(Operation.GE_OP);
                            break;
                        default:
                            ctx.addOperation(Operation.EQ_OP);
                    }
                    break;
                case '|':
                    checkPrev(ctx, prev);
                    checkBuf(ctx, sb, isVar);
                    ctx.addOperation(Operation.OR_OP);
                    break;
                case '&':
                    checkPrev(ctx, prev);
                    checkBuf(ctx, sb, isVar);
                    ctx.addOperation(Operation.AND_OP);
                    break;
                case '+':
                    checkPrev(ctx, prev);
                    checkBuf(ctx, sb, isVar);
                    ctx.addOperation(Operation.SUM_OP);
                    break;
                case '-':
                    checkPrev(ctx, prev);
                    checkBuf(ctx, sb, isVar);
                    ctx.addOperation(Operation.SUB_OP);
                    break;
                case '*':
                    checkPrev(ctx, prev);
                    checkBuf(ctx, sb, isVar);
                    ctx.addOperation(Operation.MUL_OP);
                    break;
                case '/':
                    checkPrev(ctx, prev);
                    checkBuf(ctx, sb, isVar);
                    ctx.addOperation(Operation.DIV_OP);
                    break;
                default:
                    checkPrev(ctx, prev);
                    if (isAlphaDigit(c)) {
                        if (sb.length() == 0) {
                            isVar = !Character.isDigit(c);
                        }
                        sb.append(c);
                    } else {
                        checkBuf(ctx, sb, isVar);
                    }
            }
            prev = c;
        }
        checkPrev(ctx, prev);
        checkBuf(ctx, sb, isVar);
    }
}

ExpressionParser несколько более сложен (как в реализации, так и в отладке):

package com.WhiteRabbit.condition;

import java.util.Stack;

public class ExpressionParser implements IExpressionBuilder {
   
    private String src;
    private IExpression root = null;
   
    private Stack<IExpression> operands = new Stack<IExpression>();
    private Stack<Integer> operations = new Stack<Integer>();
    private boolean isLastOperand = false;
    private int unaryOpCode = 0;
    private int brkCnt = 0;
   
    public ExpressionParser(String src) {
        this.src = src;
    }
   
    private boolean isBracketOnTop() {
        if (operations.isEmpty()) return false;
        return operations.peek() == Operation.BRK_OP;
    }
   
    private boolean isLeftPrior(int opCode) throws Exception {
        if (operations.isEmpty()) return false;
        return Operation.getPriority(operations.peek()) > 

               Operation.getPriority(opCode);
    }
   
    public IExpression getExpression() throws Exception {
        if (root == null) {
            Scaner.getInstance().scan(this, src);
            while (!operations.isEmpty()) {
                reduce();
            }
            if (operands.size() != 1) {
                throw new Exception("Syntax error");
            }
            root = operands.pop();
        }
        return root;
    }
   
    private void reduce() throws Exception {
        if (!operations.isEmpty() && (operands.size() < 2)) {
            throw new Exception("Syntax error");
        }
        int opCode = operations.pop();
        IExpression rightOp = operands.pop();
        IExpression leftOp = operands.pop();
        operands.push(new Operation(opCode, leftOp, rightOp));
    }

    public void addConstant(String value) throws Exception {
        if (isLastOperand) {
            throw new Exception("Syntax error");
        }
        IExpression r = new ConstantExpression(value);
        if (unaryOpCode != 0) {
            r = new Operation(unaryOpCode, r);
            unaryOpCode = 0;
        }
        operands.add(r);
        isLastOperand = true;
    }

    public void addVariable(String name) throws Exception {
        if (isLastOperand) {
            throw new Exception("Syntax error");
        }
        IExpression r = new VariableExpression(name);
        if (unaryOpCode != 0) {
            r = new Operation(unaryOpCode, r);
            unaryOpCode = 0;
        }
        operands.add(r);
        isLastOperand = true;
    }

    public void addOperation(int opCode) throws Exception {
        if (!isLastOperand || isBracketOnTop()) {
            if (opCode == Operation.SUB_OP) {
                opCode = Operation.NE_OP;
            }
            if ((unaryOpCode != 0) || !Operation.isUnary(opCode)) {
                throw new Exception("Syntax error");
            }
            unaryOpCode = opCode;
            return;
        }
        while (isLeftPrior(opCode)) {
            reduce();
        }
        operations.add(opCode);
        isLastOperand = false;
    }

    public void openBracket() {
        operations.add(Operation.BRK_OP);
        brkCnt++;
    }

    public void closeBracket() throws Exception {
        if (!isLastOperand || (unaryOpCode != 0) || (brkCnt <= 0)) {
            throw new Exception("Syntax error");
        }
        while (!isBracketOnTop()) {
            reduce();
        }
        brkCnt--;
    }
}

Алгоритм построения дерева основан на ведении двух стеков. В стек операндов помещаются IExpression (первоначально константы и переменные, на основании лексем, полученных от сканера).
В стек операций помещаются операции с учетом их приоритета. Если нам необходимо добавить в стек операцию, имеющую более низкий приоритет чем операци ранее помещенные в стек, мы снимаем со стека по одной операции и взяв необходимое количество операндов из стека операндов формируем объекты Operation, после чего возвращаем их на стек операндов.
По завершении разбора строки, таким же образом обрабатываем все операции из стека операций, пока он не опустеет. В стеке операндов должен остаться один элемент, собственно наше искомое дерево. Некоторое усложнение в алгоритм привносят обработка унарных операций и скобок.

Реализация остальных классов предельно примитивна (для Operation еще и многословна). Подробности можно посмотреть здесь.