3
\$\begingroup\$

I've been working on a expression parser which will be part of another project (some sort of DSL). This parser basically uses the Shunting-yard algorithm, except for the case of parenthesis: here it uses a nested stack.

I was going to extend it with unary expressions, variables and function calls among other things. But I thought it might be good check first if I was addressing this problem the right way.

My concerns are:

  • State: I'm not sure that the state is handled here the right way. Should it be owned by the class Parser or by the method parse. I want to recycle parser instances somehow.

  • Unary operators: It doesn't support unary operators yet. Should I make another enum for the unary operators or can it be part of the existing enum Operator. If so, how so?

  • Parenthesis: I chose to not push parenthesis on the operator stack to allow for a more object oriented design. This made me require to nest stacks. Is this a fair trade off? Can it be implemented another way?

Note that:

  • I know that error handling is very bad done. This must be implemented yet.
  • Javadoc has to be added yet.
  • I removed the packages for the sake of simplicity

Also I would appreciate feedback on my approach. Is this a good design and what can be better?

I hope someone can help me out!

// Expression.java

public class Expression {}



// BinaryExpression.java

public class BinaryExpression extends Expression {

    private final Operator operator;
    private final Expression left, right;

    public BinaryExpression(Operator operator, Expression left, Expression right) {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }

    public Operator getOperator() {
        return operator;
    }

    public Expression getLeft() {
        return left;
    }

    public Expression getRight() {
        return right;
    }
}

// NumberLiteral.java
public class NumberLiteral extends Expression {

    private final double value;

    public NumberLiteral(double value) {
        this.value = value;
    }

    public double getValue() {
        return value;
    }
}

// Operator.java
public enum Operator {

    ADDITION        ("+", 2, Associativity.LEFT),
    SUBTRACTION     ("-", 2, Associativity.LEFT),
    MULTIPLICATION  ("*", 3, Associativity.LEFT),
    DIVISION        ("/", 3, Associativity.LEFT);

    private final String symbol;
    private final int precedence;
    private final Associativity associativity;

    private Operator(String symbol, int precedence, Associativity associativity) {
        this.symbol = symbol;
        this.precedence = precedence;
        this.associativity = associativity;
    }

    public static Operator parse(String symbol) {

        for (Operator operator : values()) {
            if (operator.getSymbol().equals(symbol)) {
                return operator;          
            }
        }

        return null;
    }

    public String getSymbol() {
        return symbol;
    }

    public Associativity getAssociativity() {
        return associativity;
    }

    public int getPrecedence() {
        return precedence;
    }

    public static enum Associativity {
        LEFT,
        RIGHT;
    }
}

// Token.java
public class Token {

    private final Type type;
    private final String content;

    public Token(Type type, String content) {
        this.type = type;
        this.content = content;
    }

    public Type getType() {
        return type;
    }

    public String getContent() {
        return content;
    }

    public static enum Type {

        WHITESPACE("\\s"),
        NUMBER("[0-9]+(\\.[0-9]+)?"),

        OPERATOR("[\\*\\+-/]"),

        LPAR("("),
        RPAR(")"),

        ;

        Pattern pattern;

        private Type(String pattern) {
            this.pattern = Pattern.compile(pattern);
        }

        public Pattern getPattern() {
            return pattern;
        }
    }
}

// Scanner.java
public class Scanner {

    private final int index;
    private final String source;

    public Scanner(String source) {

        this.index = 0;
        this.source = source;
    }

    public boolean hasMore() {
        return index < source.length();
    }

    public Token nextToken() {

        for (Type type : Type.values()) {

            Token token = nextToken(type);

            if (token != null) {
                return token;
            }
        }

        throw new RuntimeException("Unknown token");
    }

    public Token nextToken(Token.Type type) {

        Matcher matcher = type.getPattern().matcher(source);

        matcher.region(index, source.length());

        if (matcher.lookingAt()) {

            String content = matcher.group();

            index += content.length();

            return new Token(type, content);
        }

        return null;
    }
}

// Parser.java
public interface Parser<T> {

    T parse(Scanner scanner);
}

// ExpressionParser.java
public class ExpressionParser implements Parser<Expression> {

    @Override
    public Expression parse(Scanner scanner) {

        State state = new State(scanner);

        state.pushScope();

        while (scanner.hasMore()) {

            Token 
                    currentToken = scanner.nextToken(), 
                    previousToken = null
            ;

            switch (currentToken.getType()) {

                case NUMBER: {

                    double value = Double.parseDouble(currentToken.getContent());

                    state.getScope().pushOperand(new NumberLiteral(value));

                    break;
                }

                case LPAR: {
                    state.pushScope();
                    break;
                }

                case RPAR: {

                    Expression result = state.popScope();

                    state.getScope().pushOperand(result);

                    break;
                }

                case OPERATOR: {

                    Operator operator = Operator.parse(currentToken.getContent());

                    state.getScope().pushOperator(operator);

                    break;
                }
            }
        }

        return state.popScope();
    }

    private static final class State {

        Scanner scanner;
        Stack<Scope> scopes = new Stack<>();

        public State(Scanner scanner) {
            this.scanner = scanner;
        }

        public void pushScope() {
            scopes.push(new Scope());
        }

        public Scope getScope() {
            return scopes.peek();
        }

        public Expression popScope() {

            assert(!scopes.isEmpty());

            Scope scope = getScope();

            // Pop and place all remaining operators:
            scope.popAllOperators();

            assert(scope.hasOperand());

            // Access the last operand:
            Expression result = scope.popOperand();

            assert (!scope.hasOperand()); // Should be the last operand

            scopes.pop();

            return result;
        }

        private static class Scope {

            private final Stack<Expression> operands = new Stack<>();
            private final Stack<Operator> operators = new Stack<>();

            public boolean hasOperand() {
                return !operands.isEmpty();
            }

            public void pushOperand(Expression expression) {
                operands.push(expression);
            }

            public Expression popOperand() {
                return operands.pop();
            }

            public boolean hasOperator() {
                return !operators.isEmpty();
            }

            public void pushOperator(Operator operator) {

                while (hasOperator() && compareOperator(operator)) {

                    popOperator();

                }

                operators.push(operator);
            }

            public void popOperator() {

                Expression lhs, rhs;

                rhs = operands.pop();
                lhs = operands.pop();

                operands.push(new BinaryExpression(operators.pop(), lhs, rhs));
            }

            public void popAllOperators() {
                while (hasOperator()) {
                    popOperator();
                }
            } 

            private boolean compareOperator(Operator o1) {

                Operator o2 = operators.peek();

                return (
                        (o1.getAssociativity() == Operator.Associativity.LEFT && o1.getPrecedence() <= o2.getPrecedence())
                    ||  
                        (o1.getAssociativity() == Operator.Associativity.RIGHT && o1.getPrecedence() < o2.getPrecedence())
                );
            }

        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ FYI. For a cheap, built-in expression evaluator, use Nashorn. 99% of the time, if this sort of thing is built into the JRE, you shouldn't implement your own. \$\endgroup\$ – Reinderien Mar 1 '16 at 17:40
  • \$\begingroup\$ @Reinderien That depends on whether the input might be hostile. \$\endgroup\$ – 200_success Mar 1 '16 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.