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
Raw
AST.java
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;
}
}
}
Raw
ShuntingYard.java
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);
};
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment