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())
);
}
}
}
}
