Регистрация

[Ненормальное программирование, Программирование, Java, Совершенный код, Алгоритмы] Пишем свой аналог Wolfram|Alpha

Ответить на тему
Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

Создавать темы news_bot ® написал(а)
06-Ноя-2020 02:30
Цитировать

Допустим, в какой-то момент времени, тебе, мой дорогой друг, захотелось узнать, а что же находится под капотом у математического движка и вдруг загорелся написать свой? Тогда милости прошу под кат.

Ну-с, начнем!
Постановка задачи
Возьмем простой случай: сложение и вычитание (без скобок). Надо же с чего-то начать? Затем будем постепенно дорабатывать и наращивать функционал.
Хотим, чтобы наш движок мог обрабатывать такие математические выражения:
  • 125 + 375
  • 15.25 + 7.90 + 3.12
  • 1200 — 450
  • 10 — 9 + 8 — 7 + 6 — 5 + 4 — 3 + 2 — 1

Формализация
Первым делом, нам надо понять, как разобрать математическое выражение на составляющие: без этого мы не продвинемся дальше — на числа и знаки математических операций. Напишем грамматику (громко сказано, скорее адскую смесь регулярных выражений):
expression := expression '+' expression
    | expression '-' expression
    | NUMBER
NUMBER := [0-9]+

Написание лексера
Взглянем на класс java.util.Scanner, в частности на методы:
  • boolean hasNextDouble()
  • double nextDouble()
  • boolean hasNext(Pattern pattern)
  • String next(Pattern pattern)

Да это же то, что нам нужно! Создадим класс ArsenicTau со следующим содержимым (куда же без элемента периодической системы и греческой буквы — мы же создаем аналог W|A):
import java.util.ArrayList;
import java.util.Scanner;
public class ArsenicTau {
    public static void main(String[] args) {
        var scanner = new Scanner(System.in);
        var tokens = new ArrayList<String>();
        for (; ; ) {
            if (scanner.hasNextDouble()) {
                var number = scanner.nextDouble();
                tokens.add(String.valueOf(number));
            } else if (scanner.hasNext("[+-]")) {
                var operator = scanner.next("[+-]");
                tokens.add(operator);
            } else {
                break;
            }
        }
        System.out.println(tokens);
    }
}

Запускаем, смотрим:
125 + 375
^D
[125.0, +, 375.0]
15.25 + 7.90 + 3.12
^D
[15.25, +, 7.9, +, 3.12]
1200 - 450
^D
[1200.0, -, 450.0]
10 - 9 + 8 - 7 + 6 - 5 + 4 - 3 + 2 - 1
^D
[10.0, -, 9.0, +, 8.0, -, 7.0, +, 6.0, -, 5.0, +, 4.0, -, 3.0, +, 2.0, -, 1.0]

Гуд. Теперь выделим класс Token:
import java.util.regex.Pattern;
public class Token {
    private final TokenType type;
    private final String value;
    public Token(TokenType type, String value) {
        this.type = type;
        this.value = value;
    }
    @Override
    public String toString() {
        return "Token{" +
                "type=" + type +
                ", value='" + value + '\'' +
                '}';
    }
    public enum TokenType {
        NUMBER(""),
        PLUS("\\+"),
        MINUS("-"),
        ;
        private final Pattern pattern;
        TokenType(String pattern) {
            this.pattern = Pattern.compile(pattern);
        }
        public Pattern getPattern() {
            return pattern;
        }
    }
}

Правим функцию ArsenicTau.main(String[]):
...
var tokens = new ArrayList<Token>();
...
for (; ; ) {
    Token.TokenType type;
    String value;
    if (scanner.hasNextDouble()) {
        var number = scanner.nextDouble();
        type = Token.TokenType.NUMBER;
        value = String.valueOf(number);
    } else if (scanner.hasNext(Token.TokenType.MINUS.getPattern())) {
        type = Token.TokenType.MINUS;
        value = scanner.next(type.getPattern());
    } else if (scanner.hasNext(Token.TokenType.PLUS.getPattern())) {
        type = Token.TokenType.PLUS;
        value = scanner.next(type.getPattern());
    } else {
        break;
    }
    var token = new Token(type, value);
    tokens.add(token);
}

Смотрим, что получилось:
125 + 375
^D
[Token{type=NUMBER, value='125.0'}, Token{type=PLUS, value='+'}, Token{type=NUMBER, value='375.0'}]
15.25 + 7.90 + 3.12
^D
[Token{type=NUMBER, value='15.25'}, Token{type=PLUS, value='+'}, Token{type=NUMBER, value='7.9'}, Token{type=PLUS, value='+'}, Token{type=NUMBER, value='3.12'}]
1200 - 450
^D
[Token{type=NUMBER, value='1200.0'}, Token{type=MINUS, value='-'}, Token{type=NUMBER, value='450.0'}]
10 - 9 + 8 - 7 + 6 - 5 + 4 - 3 + 2 - 1
^D
[Token{type=NUMBER, value='10.0'}, Token{type=MINUS, value='-'}, Token{type=NUMBER, value='9.0'}, Token{type=PLUS, value='+'}, Token{type=NUMBER, value='8.0'}, Token{type=MINUS, value='-'}, Token{type=NUMBER, value='7.0'}, Token{type=PLUS, value='+'}, Token{type=NUMBER, value='6.0'}, Token{type=MINUS, value='-'}, Token{type=NUMBER, value='5.0'}, Token{type=PLUS, value='+'}, Token{type=NUMBER, value='4.0'}, Token{type=MINUS, value='-'}, Token{type=NUMBER, value='3.0'}, Token{type=PLUS, value='+'}, Token{type=NUMBER, value='2.0'}, Token{type=MINUS, value='-'}, Token{type=NUMBER, value='1.0'}]

Написание парсера
С лексером справились. Осталось дело за малым: пишем парсер. Шучу. Рано еще. Выделим интерфейс Expression:
public interface Expression {
    double evaluate();
}

Затем интерфейс BinaryOperator:
public interface BinaryOperator extends Expression {
    double apply(double x, double y);
}

Имплементируем класс Constant:
public class Constant implements Expression {
    private double value;
    public Constant(double value) {
        this.value = value;
    }
    @Override
    public double evaluate() {
        return value;
    }
    @Override
    public String toString() {
        return "Constant{" +
                "value=" + value +
                '}';
    }
}

Реализуем общие методы операторов в абстрактном классе AbstractBinaryOperator:
public abstract class AbstractBinaryOperator implements BinaryOperator {
    private final Expression x;
    private final Expression y;
    protected AbstractBinaryOperator(Expression x, Expression y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public double evaluate() {
        return apply(x.evaluate(), y.evaluate());
    }
    @Override
    public String toString() {
        return getClass().getSimpleName() + "{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

Затем, собственно, сами операторы Add, Subtract:
public class Add extends AbstractBinaryOperator {
    protected Add(Expression x, Expression y) {
        super(x, y);
    }
    @Override
    public double apply(double x, double y) {
        return x + y;
    }
}
public class Subtract extends AbstractBinaryOperator {
    protected Subtract(Expression x, Expression y) {
        super(x, y);
    }
    @Override
    public double apply(double x, double y) {
        return x - y;
    }
}

Фух! Теперь мы наконец-то готовы к самому интересному: появлению виновника торжества — парсер собственной персоной. Определим интерфейс Parser:
import java.util.List;
public interface Parser {
    Expression parse(List<Token> tokens);
}

Реализуем метод рекурсивного спуска в классе ParserImpl:
import java.util.List;
import java.util.ListIterator;
import java.util.Objects;
public class ParserImpl implements Parser {
    private List<Token> tokens;
    private ListIterator<Token> iterator;
    @Override
    public Expression parse(List<Token> tokens) {
        Objects.requireNonNull(tokens, "tokens can't be null");
        this.tokens = tokens;
        this.iterator = tokens.listIterator();
        return expression();
    }
    private Expression expression() {
        var x = primary();
        while (iterator.hasNext()) {
            var operator = iterator.next();
            var y = primary();
            var type = operator.getType();
            if (Token.TokenType.PLUS.equals(type)) {
                x = new Add(x, y);
            } else if (Token.TokenType.MINUS.equals(type)) {
                x = new Subtract(x, y);
            } else {
                return x;
            }
        }
        return x;
    }
    private Expression primary() {
        if (!iterator.hasNext()) {
            throw new IllegalStateException("expected primary but not found");
        }
        var token = iterator.next();
        if (Token.TokenType.NUMBER.equals(token.getType())) {
            var value = Double.parseDouble(token.getValue());
            return new Constant(value);
        } else {
            throw new IllegalStateException("expected token but found [" + token + "]");
        }
    }
}

Допишем наш основной метод ArsenicTau.main(String[]):
...
var parser = new ParserImpl();
var expression = parser.parse(tokens);
System.out.println(expression);
System.out.println(expression.evaluate());

Проверяем:
125 + 375
^D
Add{x=Constant{value=125.0}, y=Constant{value=375.0}}
500.0
15.25 + 7.90 + 3.12
^D
Add{x=Add{x=Constant{value=15.25}, y=Constant{value=7.9}}, y=Constant{value=3.12}}
26.27
1200 - 450
^D
Subtract{x=Constant{value=1200.0}, y=Constant{value=450.0}}
750.0
10 - 9 + 8 - 7 + 6 - 5 + 4 - 3 + 2 - 1
^D
Subtract{x=Add{x=Subtract{x=Add{x=Subtract{x=Add{x=Subtract{x=Add{x=Subtract{x=Constant{value=10.0}, y=Constant{value=9.0}}, y=Constant{value=8.0}}, y=Constant{value=7.0}}, y=Constant{value=6.0}}, y=Constant{value=5.0}}, y=Constant{value=4.0}}, y=Constant{value=3.0}}, y=Constant{value=2.0}}, y=Constant{value=1.0}}
5.0

Подведем итоги
  • написали лексер
  • написали парсер
  • реализовали бинарные операторы сложения и вычитания

 ===========
 Источник:
habr.com
===========
Похожие новости: Теги для поиска: #_nenormalnoe_programmirovanie (Ненормальное программирование), #_programmirovanie (Программирование), #_java, #_sovershennyj_kod (Совершенный код), #_algoritmy (Алгоритмы), #_java, #_java_11, #_metod_rekursivnogo_spuska (метод рекурсивного спуска), #_nenormalnoe_programmirovanie (
Ненормальное программирование
), #_programmirovanie (
Программирование
), #_java, #_sovershennyj_kod (
Совершенный код
), #_algoritmy (
Алгоритмы
)
Профиль  ЛС 
Показать сообщения:     
Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 18:50
Часовой пояс: UTC + 5