Допустим, в какой-то момент времени, тебе, мой дорогой друг, захотелось узнать, а что же находится под капотом у математического движка и вдруг загорелся написать свой? Тогда милости прошу под кат.
Ну-с, начнем!
Постановка задачи
Возьмем простой случай: сложение и вычитание (без скобок). Надо же с чего-то начать? Затем будем постепенно дорабатывать и наращивать функционал.
Хотим, чтобы наш движок мог обрабатывать такие математические выражения:
- 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
Подведем итоги
- написали лексер
- написали парсер
- реализовали бинарные операторы сложения и вычитания
ссылка на оригинал статьи https://habr.com/ru/post/526656/
Добавить комментарий