Skip to content

Instantly share code, notes, and snippets.

@unautre

unautre/AST.java

Created October 10, 2018 11:45
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save unautre/2bdb81ef928f1118d73f3999e0f0b584 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save unautre/2bdb81ef928f1118d73f3999e0f0b584 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. unautre created this gist Oct 10, 2018.
    205 changes: 205 additions & 0 deletions AST.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,205 @@
    import java.util.Stack;

    import ShuntingYard.Operators;

    public class AST {

    public interface Node {
    public <R> R visit(Visitor<R> visitor);
    };

    // the only unary operator is the -.
    public static class UnaryNode implements Node {
    private final Node rhs;

    public UnaryNode(Node rhs) {
    this.rhs = rhs;
    }

    public Node getRhs() {
    return rhs;
    }

    @Override
    public <R> R visit(Visitor<R> visitor) {
    return visitor.visit(this);
    }
    }

    public static class BinaryNode implements Node {
    private final Node lhs, rhs;

    private final Operators operator;

    public BinaryNode(Operators operator, Node rhs, Node lhs) {
    this.operator = operator;
    this.lhs = lhs;
    this.rhs = rhs;
    }

    public Operators getOperator() {
    return operator;
    }

    public Node getLhs() {
    return lhs;
    }

    public Node getRhs() {
    return rhs;
    }

    @Override
    public <R> R visit(Visitor<R> visitor) {
    return visitor.visit(this);
    }
    }

    public interface Leaf extends Node {
    public String getJava();

    public double getValue();

    @Override
    public default <R> R visit(Visitor<R> visitor) {
    return visitor.visit(this);
    }
    }

    public static class ValueLeaf implements Leaf {
    private final double content;

    public ValueLeaf(double content) {
    this.content = content;
    }

    @Override
    public String getJava() {
    return content + "D";
    }

    @Override
    public double getValue() {
    return content;
    }
    }

    public static Leaf PI = new Leaf() {

    @Override
    public String getJava() {
    return "Math.PI";
    }

    @Override
    public double getValue() {
    return Math.PI;
    }
    };

    public interface Visitor<R> {
    public R visit(BinaryNode bin);

    public R visit(UnaryNode una);

    public R visit(Leaf leaf);
    }

    public static class CalculatorVisitor implements Visitor<Double> {

    @Override
    public Double visit(BinaryNode bin) {
    switch (bin.getOperator()) {
    case PLUS:
    return bin.getLhs().visit(this) + bin.getRhs().visit(this);
    case MIN:
    return bin.getLhs().visit(this) - bin.getRhs().visit(this);
    case MUL:
    return bin.getLhs().visit(this) * bin.getRhs().visit(this);
    case DIV:
    return bin.getLhs().visit(this) / bin.getRhs().visit(this);
    case POW:
    return Math.pow(bin.getLhs().visit(this), bin.getRhs().visit(this));
    default:
    throw new IllegalStateException("Unhandled operator " + bin.getOperator());
    }
    }

    @Override
    public Double visit(UnaryNode una) {
    return -una.getRhs().visit(this);
    }

    @Override
    public Double visit(Leaf leaf) {
    return leaf.getValue();
    }
    }

    public static class ToJavaVisitor implements Visitor<String> {

    private final Stack<Integer> precedences = new Stack<>();

    @Override
    public String visit(BinaryNode bin) {
    final Operators op = bin.getOperator();
    final boolean putParenthesis = !precedences.isEmpty() && op.getPrecedence() < precedences.peek();

    precedences.push(op.getPrecedence());
    final String lhs = bin.getLhs().visit(this);
    final String rhs = bin.getRhs().visit(this);
    precedences.pop();

    if (op == Operators.POW)
    return String.format("Math.pow(%s, %s)", lhs, rhs);
    else {
    return String.format(putParenthesis ? "(%s %s %s)" : "%s %s %s", lhs, op, rhs);
    }
    }

    @Override
    public String visit(UnaryNode una) {
    return "-" + una.getRhs().visit(this);
    }

    @Override
    public String visit(Leaf leaf) {
    return leaf.getJava();
    }
    }

    public static class DebugVisitor implements Visitor<Void> {

    private int indent = 0;

    private void printIndent() {
    for (int i = 0; i < indent; i++)
    System.out.print("\t");
    }

    @Override
    public Void visit(Leaf leaf) {
    printIndent();
    System.out.println(leaf.getValue());
    return null;
    }

    @Override
    public Void visit(UnaryNode una) {
    printIndent();
    System.out.println("UNARY_MINUS");
    return null;
    }

    @Override
    public Void visit(BinaryNode bin) {
    printIndent();
    System.out.println(bin.getOperator());
    indent++;
    bin.getLhs().visit(this);
    bin.getRhs().visit(this);
    indent--;
    return null;
    }
    }
    }
    146 changes: 146 additions & 0 deletions ShuntingYard.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,146 @@
    import java.util.Stack;
    import java.util.concurrent.atomic.AtomicBoolean;
    import java.util.function.Consumer;
    import java.util.regex.Matcher;
    import java.util.regex.Pattern;

    import AST.BinaryNode;
    import AST.CalculatorVisitor;
    import AST.DebugVisitor;
    import AST.Node;
    import AST.ToJavaVisitor;
    import AST.ValueLeaf;

    public class ShuntingYard {

    public static Node analyze(String wholeInput) {
    final Stack<String> ops = new Stack<>();
    final Stack<Node> values = new Stack<>();

    Tokenizer.tokenize(wholeInput, Tokenizer.implicitMulFilter(token -> {
    System.out.print(token + " ");
    switch (token) {
    case "(":
    ops.push(token);
    break;
    case ")":
    while (!ops.isEmpty()) {
    final String popped = ops.pop();
    if ("(".equals(popped))
    return;
    else
    values.add(new BinaryNode(Operators.of(popped), values.pop(), values.pop()));
    }
    throw new IllegalStateException("Unmatched parenthesis !");
    case "+":
    case "-":
    case "*":
    case "/":
    case "^":
    final Operators operator = Operators.of(token);
    Operators stackTopOperator;
    while (!ops.isEmpty() && null != (stackTopOperator = Operators.of(ops.peek()))) {
    int precedenceComparison = operator.comparePrecedence(stackTopOperator);
    if (!operator.isRightAssociative() && precedenceComparison == 0 || precedenceComparison < 0) {
    ops.pop();
    values.push(new BinaryNode(stackTopOperator, values.pop(), values.pop()));
    } else
    break;
    }
    ops.push(token);
    break;
    case "π":
    values.push(AST.PI);
    break;
    default: // number
    values.push(new ValueLeaf(Double.parseDouble(token)));
    break;
    }
    }));

    while (!ops.isEmpty())
    values.push(new BinaryNode(Operators.of(ops.pop()), values.pop(), values.pop()));
    return values.pop();
    }

    public static void main(String[] args) {
    Node ast = analyze("1 + 2π^4 + 2(3+4) + (1^2)4");
    ast.visit(new DebugVisitor());
    System.out.println(ast.visit(new ToJavaVisitor()));
    System.out.println(ast.visit(new CalculatorVisitor()));
    }

    public enum Operators {
    PLUS('+', 2), MIN('-', 2), MUL('*', 3), DIV('/', 3), POW('^', 4);

    private final char character;

    private final int precedence;

    private Operators(char character, int precedence) {
    this.character = character;
    this.precedence = precedence;
    }

    public int comparePrecedence(Operators o) {
    return Integer.compare(precedence, o.precedence);
    }

    public boolean isRightAssociative() {
    return this == POW;
    }

    public int getPrecedence() {
    return precedence;
    }

    @Override
    public String toString() {
    return Character.toString(character);
    }

    public static Operators of(String what) {
    if (what == null)
    return null;
    switch (what) {
    case "+":
    return PLUS;
    case "-":
    return MIN;
    case "*":
    return MUL;
    case "/":
    return DIV;
    case "^":
    return POW;
    default:
    return null;
    }
    }
    }

    public static class Tokenizer {
    private final static Pattern TOKEN_PATTERN = Pattern
    .compile("(([0-9]+(\\.[0-9]+)?(e-?[0-9]+)?)|π|\\+|-|\\*|\\/|\\^|\\(|\\))");

    public static void tokenize(String wholeInput, Consumer<String> callback) {
    final Matcher matcher = TOKEN_PATTERN.matcher(wholeInput);
    while (matcher.find()) {
    callback.accept(matcher.group());
    }
    }

    public static Consumer<String> implicitMulFilter(Consumer<String> callback) {
    final AtomicBoolean lastWasValue = new AtomicBoolean(false);
    return token -> {
    final char first = token.charAt(0);
    final boolean currentIsValue = Character.isDigit(first) || first == 'π';
    final boolean precedingWasValue = lastWasValue.get();
    lastWasValue.set(currentIsValue || first == ')');
    if (precedingWasValue && (currentIsValue || first == '('))
    callback.accept("*");
    callback.accept(token);
    };
    }
    }
    }