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
Parseror by the methodparse. 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()) ); } } } } 
