Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Допустим, в какой-то момент времени, тебе, мой дорогой друг, захотелось узнать, а что же находится под капотом у математического движка и вдруг загорелся написать свой? Тогда милости прошу под кат.
Ну-с, начнем!
Постановка задачи
Возьмем простой случай: сложение и вычитание (без скобок). Надо же с чего-то начать? Затем будем постепенно дорабатывать и наращивать функционал.
Хотим, чтобы наш движок мог обрабатывать такие математические выражения:
- 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.015.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.271200 - 450
^D
Subtract{x=Constant{value=1200.0}, y=Constant{value=450.0}}
750.010 - 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Подведем итоги
- написали лексер
- написали парсер
- реализовали бинарные операторы сложения и вычитания
