Clever Geek Handbook

Écrire notre analogique Wolfram | Alpha

Supposons qu'à un moment donné, vous, mon cher ami, vouliez savoir ce qu'il y a sous le capot du moteur mathématique et avez soudainement commencé à écrire le vôtre? Alors vous êtes les bienvenus sous le chat.





Eh bien, commençons!



Formulation du problème



Prenons un cas simple: l'addition et la soustraction (pas de parenthèses). Vous devez commencer quelque part? Ensuite, nous affinerons et augmenterons progressivement les fonctionnalités.



, :



  • 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






More articles:


All Articles