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

При разработке приложений бывает полезной возможность выполнить простые вычисления, по некоторой формуле, полученной в 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 еще и многословна). Подробности можно посмотреть здесь.

Коллизии

В процессе нашего изучения Box2d мы не затронули очень важную тему - обработку событий. Разумеется, Box2d обрабатывает события столкновения объектов вполне самостоятельно и без нашей помощи, но иногда нам тоже хочется принять в этом участие :) Внесем изменения в наш проект Kepler таким образом, чтобы столкнувшиеся объекты "сливались" в один.

Один из столкнувшихся объектов будем удалять, а у второго будем изменять параметры. Нам необходимо зарегистрировать объект ContactListener, чтобы получать сообщения  о коллизиях и внести в проект изменения, связанные с обработкой этих коллизий. Главное, о чем необходимо помнить, это то, что объекты Box2d НЕ ДОЛЖНЫ изменяться, в процессе расчета очередной итерации. Получив уведомление о коллизии, мы должны сохранить параметры, для того, чтобы выполнить необходимые изменения после расчета итерации Box2d. Измененный модуль Task будет выглядеть следующим образом:

package com.WhiteRabbit.Kepler;

import java.util.Random;
import java.util.Timer;
import java.util.TimerTask;

import org.jbox2d.callbacks.ContactImpulse;
import org.jbox2d.callbacks.ContactListener;
import org.jbox2d.collision.Manifold;
import org.jbox2d.collision.shapes.CircleShape;
import org.jbox2d.collision.shapes.PolygonShape;
import org.jbox2d.common.Vec2;
import org.jbox2d.dynamics.Body;
import org.jbox2d.dynamics.BodyDef;
import org.jbox2d.dynamics.BodyType;
import org.jbox2d.dynamics.World;
import org.jbox2d.dynamics.contacts.Contact;

public class Task extends TimerTask implements ContactListener {

    private static long SECONDS_INTERVAL = 1000L;
    private static long FRAME_RATE = 15L;
   
    private KeplerActivity ctx;
    private Timer timer = new Timer();
   
    private World             world;
    private Body              ground;
   
    public Task(KeplerActivity ctx) {
        this.ctx  = ctx;
        configure();
    }
   
    @Override
    public void beginContact(Contact contact) {}

    @Override
    public void endContact(Contact contact) {}

    @Override
    public void preSolve(Contact contact, Manifold folds) {}
   
    @Override
    public void postSolve(Contact contact, ContactImpulse impulse) {
        Item a = (Item)contact.getFixtureA().getBody().getUserData();
        Item b = (Item)contact.getFixtureB().getBody().getUserData();
        if (a.isMarked() || b.isMarked()) return;
        a.mark(); b.delete();
        Vec2 aSpeed = a.getBody().getLinearVelocity();
        Vec2 bSpeed = b.getBody().getLinearVelocity();
        a.getBody().setLinearVelocity(new Vec2(aSpeed.x + bSpeed.x, 
                                               aSpeed.y + bSpeed.y));
        a.setRadius((float)Math.sqrt((a.getRadius()*a.getRadius()) +  
                                     (b.getRadius()*b.getRadius())));
    }

    private void configure() {
        MainView v = ctx.getView();
        float X = v.SZ_X / 2;
        float Y = v.SZ_Y / 2;
       
        // Создать мир
        Vec2 gravity = new Vec2(0.0f, 0.0f);
        world = new World(gravity, true);
        world.setContactListener(this);
        BodyDef bd = new BodyDef();
        ground = world.createBody(bd);
       
        // Создать границы
        bd.position.set(0, Y);
        Body edge = world.createBody(bd);
        PolygonShape sd = new PolygonShape();
        sd.setAsBox(1, Y);
        edge.createFixture(sd, 1);
        bd.position.set(2 * X, Y);
        edge = world.createBody(bd);
        edge.createFixture(sd, 1);
        bd.position.set(X, 0);
        edge = world.createBody(bd);
        sd.setAsBox(X, 1);
        edge.createFixture(sd, 1);
        bd.position.set(X, 2 * Y);
        edge = world.createBody(bd);
        edge.createFixture(sd, 1);
       
        // Создать объекты
        CircleShape shape = new CircleShape();
        bd.type = BodyType.DYNAMIC;
        Random r = new Random();
       
        for (int i = 0; i < 15; i++) {
            bd.position.set(r.nextInt((int)X * 2 - 10) + 5, 
                            r.nextInt((int)Y * 2 - 10) + 5);
            bd.linearVelocity.set(r.nextInt(20) - 5, r.nextInt(20) - 10);
            shape.m_radius = r.nextInt(4) + 1;
            Body b = world.createBody(bd);
            b.createFixture(shape, r.nextInt(3) + 1);
            ctx.getView().addBody(b, shape.m_radius);
        }
       
        // Запустить рассчет
        timer.scheduleAtFixedRate(this, 0, SECONDS_INTERVAL / FRAME_RATE);
    }
   
    public void terminate() {
        if (timer != null) {
            timer.cancel();
            timer = null;
        }
    }

    @Override
    public void run() {
        // Выполнить расчет итерации
        float timeStep = 2.0f / FRAME_RATE;
        world.step(timeStep, 10, 10);
        // Удалить столкнувшиеся объекты
        ctx.getView().removeDeleted(world);
        // Рассчитать действующие силы
        ctx.getView().calcForces();
        // Обновить view
        ctx.getView().update();
    }
}

1. Мы наследуем интерфейс ContactListener и регистрируем его вызовом setContactListener
2. Для обработки коллизий будем использовать метод postSolve (от других он выгодно отличается наличием параметра impulse, по которому можно оценивать "силу" соударения, чего мы правда не будем делать)
3. В configure вместо 3 генерируем 15 объектов, используя генератор случайных чисел для формирования начальных параметров
4. Добавляем границы по краям экрана, чтобы объекты не улетали в открытое пространство
5. В методе run добавляем фазу удаления объектов помеченных для удаления

В MainView немного изменяем метод addBody (сохраняя в Body ссылку на объект Item) и добавляем метод removeDeleted, осуществляющий удаление объектов:

package com.WhiteRabbit.Kepler;

import java.util.ArrayList;
import java.util.List;

import org.jbox2d.collision.shapes.CircleShape;
import org.jbox2d.common.Vec2;
import org.jbox2d.dynamics.Body;
import org.jbox2d.dynamics.Fixture;
import org.jbox2d.dynamics.World;

import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.view.SurfaceHolder;
import android.view.SurfaceView;

public class MainView extends SurfaceView implements SurfaceHolder.Callback {
    

    ...

    public void addBody(Body b, float r) {
        Item it = new Item(b, r);
        b.setUserData(it);
        items.add(it);
    }
   
    public void removeDeleted(World w) {
        List<Item> newItems = new ArrayList<Item>();
        for (Item it: items) {
            if (it.isDeleted()) {
                w.destroyBody(it.getBody());
            } else {
                if (it.isMarked()) {
                    Body b = it.getBody();
                    CircleShape shape = new CircleShape();
                    shape.m_radius = it.getRadius();
                    Fixture f = b.getFixtureList();
                    if (f !=null) {
                        b.destroyFixture(f);
                    }
                    b.createFixture(shape, 1);
                    it.clear();
                }
                newItems.add(it);
            }
        }
        items = newItems;
    }
    ...   
}

Item приобретает новые члены, но не становится от этого менее тривиальным:

package com.WhiteRabbit.Kepler;

import org.jbox2d.dynamics.Body;

public class Item {
   
    private Body body;
    private float radius;
    private boolean isDeleted = false;
    private boolean isMarked = false;
   
    public Item(Body body, float radius) {
        this.body = body;
        this.radius = radius;
    }
   
    public boolean isDeleted() {
        return isDeleted;
    }
   
    public boolean isMarked() {
        return isDeleted || isMarked;
    }
   
    public void delete() {
        isDeleted = true;
    }
   
    public void mark() {
        isMarked = true;
    }
   
    public void clear() {
        isMarked = false;
    }
   
    public Body getBody() {
        return body;
    }
   
    public float getRadius() {
        return radius;
    }
   
    public void setRadius(float radius) {
        this.radius = radius;
    }
}

Вот и все. Запускаем программу на выполнение и наблюдаем картину "должен остаться только один":

Как обычно, полный исходный код проекта можно взять здесь.