 We Love International Women’s Day  Building Your Own Programming Language From Scratch: Part II - Dijkstra's Two-Stack Algorithm by@alexmakeev1995

# Building Your Own Programming Language From Scratch: Part II - Dijkstra's Two-Stack Algorithm # 1 Introduction

In this article we will improve mathematical expressions evaluation for our programming language (please see Part I) 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.

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: `2 * (3 + 4) - 5`. When we calculate this expression first we summarize `3` and `4` in the parentheses. After that, we multiply the result by `2`. And in the end we subtract `5` from the result. Down below is the expression evaluation using Dijkstra's Two-Stack algorithm:

1. Push `2` to the operands stack: 1. Push `*` to operators: 1. Push `(` to operands: 1. Push `3` to operands: 1. Push `+` to operators: 1. Push `4` to operands: 1. Push `)` to operators. Closing parenthesis pops an operation until a nearest opening parenthesis `(`. Therefore, we pop top operator and apply it on the two top operands: 1. Push `-` to operators. The operators stack's top element `*` has greater precedence than the current operator `-`. Therefore, first we apply top operator on two top operands: 1. Push `5` to operands: 1. Pop left `-` operator: # 2 Operators

Let’s dive into the code. First, we will update our `Operator` enum including operators precedence and introduce a few new operators:

``````@RequiredArgsConstructor
@Getter
public enum Operator {
Not("!", NotOperator.class, 5),
StructureValue("::", StructureValueOperator.class, 5),

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 {
...
...
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 `new` as the keyword lexeme, it will be the operator which will help us to instantiate a structure object inside a more complex expression:

``````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) {
}
}
``````

## 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 `OperatorExpression` implementations as we make an expression calculation using parentheses:

``````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 `VariableExpression` - the variable we’re assigning value to. Thus, we introduce a new method in our `VariableExpression` to set the variable value. As you may remember our variables Map is being stored in the `StatementParser`. To set access it and set a new value we introduce a `BiConsumer` instance, passing variable name as a key and variable value as a new value:

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

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 `LineBreak` lexeme which will help us to catch all expression tokens until we reach end of the row:

``````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 `StatementParser` to divide each passing argument into separate expression. To deal with it we can introduce new comma `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 `StatementParser` using Dijkstra’s Two-Stack algorithm.

## 3.1 Next token

Firstly, we will introduce `skipLineBreaks()` method, that will increment tokens position while we reach `LineBreak` token:

``````private void skipLineBreaks() {
while (tokens.get(position).getType() == TokenType.LineBreak
&& ++position != tokens.size()) ;
}
``````

It will be used on the top of each `next()` and `peek()` methods to escape catching `LineBreak` token:

``````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 `next()` method without any arguments just returning the next token:

``````private Token next() {
skipLineBreaks();
}
``````

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 `Operator` enum types. The second stack of operands will have `Expression` 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 `ExpressionReader`:

``````private class ExpressionReader {
private final Stack<Expression> operands;
private final Stack<Operator> operators;

this.operands = new Stack<>();
this.operators = new Stack<>();
}
}
``````

Then we create a `readExpression()` method with a while loop to read an entire expression. Our mathematical expression can begin with `Operator`, `Variable`, `Numeric` , `Logical` or `Text` token types. In this case we can’t exclude the `LineBreak` token during token retrieval because this token means the end of the expression. Therefore, we introduce an additional `peek()` method inside our inner class that will read an expression until we reach the end of the row:

``````private class ExpressionReader {
...
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) {
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 `Operator`. We retrieve the `Operator` enum by token’s value and use it in the switch block. There are 3 cases we will deal with:

1. `LeftParen` - just put an operator into the operators stack
2. `RightParen` - calculate previously pushed expressions until we reach the left parenthesis `LeftParen`.
3. 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 `applyTopOperator()` method. First we pop an operator and the first operand. Then if our operator is binary we pop the second operand. To create an `OperatorExpression` 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 `OperatorExpression` instance to the operands stack. Thus, this pushed operand `Expression` can be used later by other operators inside a more composite 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 `Expression` object inside the following switch block and then push the result to the operands stack:

``````...
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) {
} 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 `StructureExpression` value. We will move existent `readInstance()` method from `StatementParser` class into the inner `ExpressionReader` class with following changes:

``````...
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, "]")) {

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 `AssignmentStatement` in the `parseExpression()` method. The `AssignStatement` can start with a Variable or an Operator token type (in case we have a `new` operator for the structure instantiation). When we read an expression we expect to read an entire `Assignment` 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 `ExpressionReader` starting from variable’s name declaration:

``````private Statement parseExpression() {
Token token = next(TokenType.Keyword, TokenType.Variable, TokenType.Operator);
switch (token.getType()) {
case Variable:
case Operator:
position--;
...
case Keyword:
default:
...
}
}
``````

In the end we expect to obtain the complete `AssignmentOperator` and we can create an `AssignmentStatement` instance:

``````...
case Variable:
case Operator:
position--;

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 `input` and `if` statements using our new inner `ExpressionReader` class. It will allow us to read complex expression inside `print` and `if` statements:

``````...
case Keyword:
default:
switch (token.getValue()) {
case "print":
...
case "if":
...
}
...
``````

# 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.                