Suppose, at some point in time, you, my dear friend, wanted to know, what is under the hood of the mathematical engine and suddenly started to write your own? Then you are welcome under the cat.
Well, let's start!
Formulation of the problem
Let's take a simple case: addition and subtraction (no parentheses). Got to start somewhere? Then we will gradually refine and increase the functionality.
, :
- 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);
}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