1 Introduction In this article we will improve mathematical expressions evaluation for our programming language (please see ) using Dijkstra's Two-Stack algorithm. The essence of this algorithm is that any complex expression ultimately comes down to the simple expression. In the end, It will be a unary or binary operation on one/two operands. Part I How Dijkstra's Two-Stack algorithm works: We iterate tokens expression If our token is an operand (e.g. number), we push it into the operands stack If we find an operator, we push into the operators stack We pop operators with the higher priority than the current one and apply it on the top operand(s) If an opening parenthesis is found, we push it into the operands stack. If a closing parenthesis is found, pop all operators and apply it on the top operand(s) until the opening parenthesis will be reached, and finally pop the opening parenthesis. Example Let’s suppose we have the following expression: . When we calculate this expression first we summarize and in the parentheses. After that, we multiply the result by . And in the end we subtract from the result. Down below is the expression evaluation using Dijkstra's Two-Stack algorithm: 2 * (3 + 4) - 5 3 4 2 5 Push to the operands stack: 2 Push to operators: * Push to operands: ( Push to operands: 3 Push to operators: + Push to operands: 4 Push to operators. Closing parenthesis pops an operation until a nearest opening parenthesis . Therefore, we pop operator and apply it on the operands: ) ( top two top Push to operators. The operators stack's top element has greater precedence than the current operator . Therefore, first we apply operator on operands: - * - top two top Push to operands: 5 Pop left operator: - 2 Operators Let’s dive into the code. First, we will update our enum including operators precedence and introduce a few new operators: Operator @RequiredArgsConstructor @Getter public enum Operator { Not("!", NotOperator.class, 5), StructureValue("::", StructureValueOperator.class, 5), Addition("+", AdditionOperator.class, 3), Subtraction("-", SubtractionOperator.class, 3), LessThan("<", LessThanOperator.class, 2), GreaterThan(">", GreaterThanOperator.class, 2); private final String character; private final Class<? extends OperatorExpression> type; private final Integer precedence; Operator(String character, Integer precedence) { this(character, null, precedence); } public static Operator getType(String character) { return Arrays.stream(values()) .filter(t -> Objects.equals(t.getCharacter(), character)) .findAny().orElse(null); } public boolean greaterThan(Operator o) { return getPrecedence().compareTo(o.getPrecedence()) > 0; } } public class StatementParser { ... private Expression readExpression() { ... while (peek(TokenType.Operator)) { Token operation = next(TokenType.Operator); Operator operator = Operator.getType(operation.getValue()); Class<? extends OperatorExpression> operatorType = operator.getType(); ... } ... } ... } 2.1 StructureInstance We will no longer mark as the keyword lexeme, it will be the operator which will help us to instantiate a structure object inside a more complex expression: new public enum TokenType { ... Keyword("(if|then|end|print|input|struct|arg)"), Operator("(\\+|\\-|\\>|\\<|\\={1,2}|\\!|\\:{2}|new)"); ... } We set it the highest priority: public enum Operator { ... StructureInstance("new", StructureInstanceOperator.class, 5), ... } public class StructureInstanceOperator extends UnaryOperatorExpression { public StructureInstanceOperator(Expression value) { super(value); } @Override public Value<?> calc(Value<?> value) { return value; //will return toString() value } } 2.2 Multiplication & Division We will also include two more operators with higher priority than addition and subtraction. Don’t forget to add regex expression for each operator to be counted when we’re doing lexical analysis: public enum TokenType { ... Operator("(\\+|\\-|\\>|\\<|\\={1,2}|\\!|\\:{2}|new|\\*|\\/)"); ... } public enum Operator { ... Multiplication("*", MultiplicationOperator.class, 4), Division("/", DivisionOperator.class, 4), ... } 2.3 LeftParen & RightParen These operators will be used to change operator’s precedence by surrounding expression in the parentheses. We will not create implementations as we make an expression calculation using parentheses: OperatorExpression public enum TokenType { ... Operator("(\\+|\\-|\\>|\\<|\\={1,2}|\\!|\\:{2}|new|\\*|\\/|\\(|\\))"); ... } public enum Operator { ... LeftParen("(", 1), RightParen(")", 1), ... } 2.4 Assignment We also need to introduce a new assignment operator with a single equal sign. The variable value will be assigned to the variable only when we complete evaluation of the right expression. Therefore, this operator should have the lowest priority: = public enum Operator { ... Assignment("=", AssignmentOperator.class, 6), ... } public class AssignOperator extends BinaryOperatorExpression { public AssignOperator(Expression left, Expression right) { super(left, right); } @Override public Value<?> calc(Value<?> left, Value<?> right) { if (getLeft() instanceof VariableExpression) { ((VariableExpression) getLeft()).setValue(right); } return left; } } During the execution we expect to retrieve the left expression as a - the variable we’re assigning value to. Thus, we introduce a new method in our to set the variable value. As you may remember our variables Map is being stored in the . To set access it and set a new value we introduce a instance, passing variable name as a key and variable value as a new value: VariableExpression VariableExpression StatementParser BiConsumer public class VariableExpression implements Expression { ... private final BiConsumer<String, Value<?>> setter; ... public void setValue(Value<?> value) { setter.accept(name, value); } } public class StatementParser { ... private Expression nextExpression() { ... return new VariableExpression(value, variables::get, variables::put); } ... } 2.5 Expression dividers 2.5.1 End of the row Previously, to build a mathematical expression we expected to obtain an operator after each operand: Expression left = nextExpression(); //recursively read an expression while (peek(TokenType.Operator)) { Token operation = next(TokenType.Operator); Operator operator = Operator.getType(operation.getValue()); Class<? extends OperatorExpression> operatorType = operator.getType(); if (BinaryOperatorExpression.class.isAssignableFrom(operatorType)) { Expression right = nextExpression(); left = operatorType .getConstructor(Expression.class, Expression.class) .newInstance(left, right); } else if (UnaryOperatorExpression.class.isAssignableFrom(operatorType)) { left = operatorType .getConstructor(Expression.class) .newInstance(left); } } With the current behavior we can expect two subsequent operators in the row, e.g. addition of structure instantiation as an right operand or two following opening parentheses: value + new Car [“E30” “325i”] :: model or ( ( 1 + 2) * 3) - 4 To read an entire expression with any sequence of operands and operators we will introduce the lexeme which will help us to catch all expression tokens until we reach end of the row: LineBreak public class StatementParser { LineBreak("[\\n\\r]"), Whitespace("[\\s\\t]"), ... } 2.5.2 Structure arguments The second divider we need to count is when we instantiate a structure object: new Car [ “E30” “325i” new Engine [“M20B25”] :: model ] This structure instantiation is quite complex for the to divide each passing argument into separate expression. To deal with it we can introduce new comma : StatementParser GroupDivider public enum TokenType { ... GroupDivider("(\\[|\\]|\\,)"), ... } new Car [ “E30”, “325i”, new Engine [“M20B25”] :: model ] 3 Expression evaluation Now we can start refactoring our expression evaluation in the using Dijkstra’s Two-Stack algorithm. StatementParser 3.1 Next token Firstly, we will introduce method, that will increment tokens position while we reach token: skipLineBreaks() LineBreak private void skipLineBreaks() { while (tokens.get(position).getType() == TokenType.LineBreak && ++position != tokens.size()) ; } It will be used on the top of each and methods to escape catching token: next() peek() LineBreak private Token next(TokenType type, TokenType... types) { skipLineBreaks(); ... } private Token next(TokenType type, String value) { skipLineBreaks(); ... } private boolean peek(TokenType type, String content) { skipLineBreaks(); ... } private boolean peek(TokenType type) { skipLineBreaks(); ... } We will also override the method without any arguments just returning the next token: next() private Token next() { skipLineBreaks(); return tokens.get(position++); } 3.2 ExpressionReader To read and calculate an entire expression using Dijkstra's Two-Stack algorithm we will need two stacks, the operators stack, and the operands stack. The first stack of operators will contain the enum types. The second stack of operands will have type, it will help us to store every type of expression including values, variables and composite operators. It will be clearer if we perform expression reading in a separate inner class : Operator Expression ExpressionReader private class ExpressionReader { private final Stack<Expression> operands; private final Stack<Operator> operators; private ExpressionReader() { this.operands = new Stack<>(); this.operators = new Stack<>(); } } Then we create a method with a while loop to read an entire expression. Our mathematical expression can begin with , , , or token types. In this case we can’t exclude the token during token retrieval because this token means the end of the expression. Therefore, we introduce an additional method inside our inner class that will read an expression until we reach the end of the row: readExpression() Operator Variable Numeric Logical Text LineBreak peek() private class ExpressionReader { ... private Expression readExpression() { while (peek(TokenType.Operator, TokenType.Variable, TokenType.Numeric, TokenType.Logical, TokenType.Text)) { Token token = next(); switch (token.getType()) { case Operator: ... default: ... } } ... } private boolean peek(TokenType type, TokenType... types) { TokenType[] tokenTypes = ArrayUtils.add(types, type); if (position < tokens.size()) { Token token = tokens.get(position); return Stream.of(tokenTypes).anyMatch(t -> t == token.getType()); } return false; } } 3.2.1 Operator The first lexeme type we will process is . We retrieve the enum by token’s value and use it in the switch block. There are 3 cases we will deal with: Operator Operator - just put an operator into the operators stack LeftParen - calculate previously pushed expressions until we reach the left parenthesis . RightParen LeftParen Before inserting other operators we need to be sure that the current operator has greater precedence than the top operator, in the negative case we pop the top operator and apply it on the top operand(s). In the end we push the less prioritized operator into the operators stack. ... case Operator: Operator operator = Operator.getType(token.getValue()); switch (operator) { case LeftParen: operators.push(operator); break; case RightParen: //until left parenthesis is not reached while (!operators.empty() && operators.peek() != Operator.LeftParen) applyTopOperator(); operators.pop(); //pop left parenthesis break; default: //until top operator has greater precedence while (!operators.isEmpty() && operators.peek().greaterThan(operator)) applyTopOperator(); operators.push(operator); // finally, add less prioritized operator } break; ... To apply the top operator on the top operand(s) we create an additional method. First we pop an operator and the first operand. Then if our operator is binary we pop the second operand. To create an object we retrieve a suitable constructor for unary or binary operator implementation and make an instance with earlier popped operands. In the end we push the instance to the operands stack. Thus, this pushed operand can be used later by other operators inside a more composite expression: applyTopOperator() OperatorExpression OperatorExpression Expression @SneakyThrows private void applyTopOperator() { // e.g. a + b Operator operator = operators.pop(); Class<? extends OperatorExpression> operatorType = operator.getType(); Expression left = operands.pop(); if (BinaryOperatorExpression.class.isAssignableFrom(operatorType)) { Expression right = operands.pop(); operands.push(operatorType .getConstructor(Expression.class, Expression.class) .newInstance(right, left)); } else if (UnaryOperatorExpression.class.isAssignableFrom(operatorType)) { // e.g. new Instance [] operands.push(operatorType .getConstructor(Expression.class) .newInstance(left)); } else { throw new SyntaxException(String.format("Operator `%s` is not supported", operatorType)); } } 3.2.2 Value & VariableExpression If our token is a variable or a literal, we transform it to the appropriate object inside the following switch block and then push the result to the operands stack: Expression ... default: String value = token.getValue(); Expression operand; switch (token.getType()) { case Numeric: operand = new NumericValue(Integer.parseInt(value)); break; case Logical: operand = new LogicalValue(Boolean.valueOf(value)); break; case Text: operand = new TextValue(value); break; case Variable: default: if (!operators.isEmpty() && operators.peek() == Operator.StructureInstance) { operand = readInstance(token); } else { operand = new VariableExpression(value, variables::get, variables::put); } } operands.push(operand); ... A variable token can also indicate the start of the structure instantiation. In this case we read an entire structure expression with arguments inside square brackets and only then assign it to the value. We will move existent method from class into the inner class with following changes: StructureExpression readInstance() StatementParser ExpressionReader ... private Expression readInstance(Token token) { StructureDefinition definition = structures.get(token.getValue()); List<Expression> arguments = new ArrayList<>(); if (StatementParser.this.peek(TokenType.GroupDivider, "[")) { next(TokenType.GroupDivider, "["); //skip open square bracket while (!StatementParser.this.peek(TokenType.GroupDivider, "]")) { Expression value = new ExpressionReader().readExpression(); arguments.add(value); if (StatementParser.this.peek(TokenType.GroupDivider, ",")) next(); } next(TokenType.GroupDivider, "]"); //skip close square bracket } if (definition == null) { throw new SyntaxException(String.format("Structure is not defined: %s", token.getValue())); } return new StructureExpression(definition, arguments, variables::get); } ... 3.2.3 Evaluation After we finished processing expression tokens and reached the end of the expression we will need an extra while loop to pop remaining operators and apply it on the top operand(s). In the end we should have the only one resulting composite operand in the operands stack, we return it as a final expression result: private Expression readExpression() { ... while (!operators.isEmpty()) { applyTopOperator(); } return operands.pop(); } 3.3 AssignStatement Now we can now build in the method. The can start with a Variable or an Operator token type (in case we have a operator for the structure instantiation). When we read an expression we expect to read an entire expression accumulating left value as a variable name and right expression as a variable value. Therefore, we go to one tokens position back and start reading the expression using starting from variable’s name declaration: AssignmentStatement parseExpression() AssignStatement new Assignment ExpressionReader private Statement parseExpression() { Token token = next(TokenType.Keyword, TokenType.Variable, TokenType.Operator); switch (token.getType()) { case Variable: case Operator: position--; Expression value = new ExpressionReader().readExpression(); ... case Keyword: default: ... } } In the end we expect to obtain the complete and we can create an instance: AssignmentOperator AssignmentStatement ... case Variable: case Operator: position--; Expression value = new ExpressionReader().readExpression(); if (value instanceof AssignmentOperator) { VariableExpression variable = (VariableExpression) ((AssignmentOperator) value).getLeft(); return new AssignmentStatement(variable.getName(), ((AssignmentOperator) value).getRight(), variables::put); } else { throw new SyntaxException(String.format("Unsupported statement: `%s`", value)); } ... The last thing we need to do is to update expressions reading for the and statements using our new inner class. It will allow us to read complex expression inside and statements: input if ExpressionReader print if ... case Keyword: default: switch (token.getValue()) { case "print": Expression expression = new ExpressionReader().readExpression(); ... case "if": Expression condition = new ExpressionReader().readExpression(); ... } ... 4 Wrapping up In this article, we improved our own programming language with mathematical expressions evaluation using Dijkstra's Two-Stack algorithm. We injected operators priority with an ability to change it using parentheses, including complex structure instantiations. The full source code is available . over on GitHub
