Angenommen, Sie, mein lieber Freund, wollten irgendwann wissen, was sich unter der Haube der mathematischen Engine befindet, und haben plötzlich angefangen, Ihre eigenen zu schreiben. Dann sind Sie unter der Katze willkommen.
Nun, lass uns anfangen!
Formulierung des Problems
Nehmen wir einen einfachen Fall: Addition und Subtraktion (keine Klammern). Müssen Sie irgendwo anfangen? Dann werden wir die Funktionalität schrittweise verfeinern und erweitern.
, :
- 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