Step Nine
In our last step, we postponed multiplication of multiple and division numbers. Looking at the code Calculator, you might say that this should already work now. There is no distinction between multiplication/division and addition/subtraction. You are right, but this is exactly the problem. The code does not take operator precedence into account. This means, an expression containing both addition or subtraction and multiplication or division could fail. This is because our code is working from left to right.
Integration Tests
Let’s put this analysis into new integration tests. We start with multiplication and division of multiple numbers:
def test_multiplication_of_multiple_numbers(self):
output = self.app.calculate("3 * 5 * 2")
self.assertEqual(output, "30")
output = self.app.calculate("0 * 5 * 7 * 1231")
self.assertEqual(output, "0")
def test_division_of_multiple_numbers(self):
output = self.app.calculate("3 / 5 / 2")
self.assertEqual(output, "0.30")
output = self.app.calculate("0 / 5 / 7")
self.assertEqual(output, "0.00")
output = self.app.calculate("1.5 / -1 / 3 / -1")
self.assertEqual(output, "0.50")
As we expected, these tests are green. We don’t need to implement anything to make this work.
But what about mixed operations? Let’s write tests for them:
def test_mixed_operations(self):
output = self.app.calculate("3 + 5 * 2")
self.assertEqual(output, "13")
output = self.app.calculate("10 + 5 / 2")
self.assertEqual(output, "12.50")
output = self.app.calculate("3 * 5 + 2")
self.assertEqual(output, "17")
Which result should we expect from the first operation, knowing the operators are evaluated only from left to right? Instead of the correct result “13” we should expect “16”. We let our test prove it:
FAIL: test_mixed_operations (testIntegrationCalculatorApplication.TestIntegrationCalculatorApplication)
----------------------------------------------------------------------
Traceback (most recent call last):
File ".../testIntegrationCalculatorApplication.py", line 147, in test_mixed_operations
self.assertEqual(output, "13")
AssertionError: '16' != '13'
- 16
+ 13
We were right – 16! Our next task is to figure out how to implement mixed operations.
Implementing Mixed Operations
Where do we need to change our program to make mixed operations work? Tokenizer does not need to know about operator precedence. Also, ExpressionValidator does not need to change, because it accepts the mixed operations without problems. The problem lies within Calculator, which always calculates the terms from left to right. Calculator needs a kind of preprocessing step in which it determines the order of the terms to calculate. Before we decide how the preprocessing looks like, we add unit tests for Calculator with mixed operations. Later, these tests will show us that we did the preprocessing right.
def test_mixed_operations(self):
result = self.calculator.calculate([Number(3), Operator.Addition, Number(5), Operator.Multiplication, Number(2)])
self.assertEqual(result, 13)
result = self.calculator.calculate([Number(3), Operator.Division, Number(6), Operator.Subtraction, Number(2)])
self.assertEqual(result, -1.5)
Designing a Term Building Algorithm
Now we have a failing unit test. Let’s design the algorithm for building a term. It will need to create a tree of terms. Then the calculation can start with the root term. Each operand in that term can either be a number or another term. In case of a term, the result of that term needs to be calculated before the current term can be calculated. This means we will end up with an iterative algorithm.
To build the tree of terms, we can use the following algorithm:
- Take the first three tokens and create a term containing them.
- Check the next token and compare its precedence with the operator of the current term.
- If the next token has a higher precedence, then replace the right hand side of the current term with a new term containing the right hand side, the operator and the next number.
- If the next token has the same precedence, build a new term with the current term the left hand side and the new number the right hand side.
- If all tokens have been processed, return the current term, which is the root term.
Introducing a Term Class
Our algorithm will need to check if an operand is a term or a number. We already have a class that represents a number, but we need a class to represent a term. It shall accept three parameters in the initializer. The first one and third need to be either of type Number or Term, and the second one needs to be an Operator. Let’s test for that:
class TestTerm(unittest.TestCase):
def test_getters(self):
term1 = Term(Number(0), Operator.Addition, Number(1))
self.assertEqual(term1.get_operand_1(), Number(0))
self.assertEqual(term1.get_operator(), Operator.Addition)
self.assertEqual(term1.get_operand_2(), Number(1))
term2 = Term(term1, Operator.Subtraction, Number(2))
self.assertEqual(term2.get_operand_1(), term1)
self.assertEqual(term2.get_operator(), Operator.Subtraction)
self.assertEqual(term2.get_operand_2(), Number(2))
The implementation of Term looks like this:
class Term:
def __init__(self, operand_1, operator, operand_2):
self.operand_1 = operand_1
self.operator = operator
self.operand_2 = operand_2
def get_operand_1(self):
return self.operand_1
def get_operand_2(self):
return self.operand_2
def get_operator(self):
return self.operator
Operator Precedence
Another prerequisite of our algorithm is that we can check for the priority of operators. It makes sense to check this in Operator itself. Let’s add a test that checks all possible combinations of operators:
class TestOperator(unittest.TestCase):
def test_operator_precedence(self):
self.assertFalse(Operator.Addition.has_higher_precedence_than(Operator.Addition))
self.assertFalse(Operator.Addition.has_higher_precedence_than(Operator.Subtraction))
self.assertFalse(Operator.Addition.has_higher_precedence_than(Operator.Multiplication))
self.assertFalse(Operator.Addition.has_higher_precedence_than(Operator.Division))
self.assertFalse(Operator.Subtraction.has_higher_precedence_than(Operator.Addition))
self.assertFalse(Operator.Subtraction.has_higher_precedence_than(Operator.Subtraction))
self.assertFalse(Operator.Subtraction.has_higher_precedence_than(Operator.Multiplication))
self.assertFalse(Operator.Subtraction.has_higher_precedence_than(Operator.Division))
self.assertTrue(Operator.Multiplication.has_higher_precedence_than(Operator.Addition))
self.assertTrue(Operator.Multiplication.has_higher_precedence_than(Operator.Subtraction))
self.assertFalse(Operator.Multiplication.has_higher_precedence_than(Operator.Multiplication))
self.assertFalse(Operator.Multiplication.has_higher_precedence_than(Operator.Division))
self.assertTrue(Operator.Division.has_higher_precedence_than(Operator.Addition))
self.assertTrue(Operator.Division.has_higher_precedence_than(Operator.Subtraction))
self.assertFalse(Operator.Division.has_higher_precedence_than(Operator.Multiplication))
self.assertFalse(Operator.Division.has_higher_precedence_than(Operator.Division))
The method has_higher_precedence_than looks like this:
class Operator(Enum):
Addition = 1
Subtraction = 2
Multiplication = 3
Division = 4
def has_higher_precedence_than(self, other_operator):
if(other_operator == Operator.Addition or other_operator == Operator.Subtraction) and (self == Operator.Multiplication or self == Operator.Division):
return True
else:
return False
Term Building
Now we can begin implementing the term building method. The resulting code looks as follows:
class Calculator:
def calculate(self, tokens):
if len(tokens) < 3:
return 0
# Build first root term
root_term = Term(*tokens[0:3])
rest = tokens[3:]
# Consume expression from left to right and update the root term
while(type(rest) is list and len(rest) > 0):
root_term = self.build_term(root_term, *rest[0:2])
rest = rest[2:]
# Calculate the result of the expression, starting with the root term
return self.calculate_term(root_term).get_value()
def build_term(self, operand_1, operator, operand_2):
if type(operand_1) is Term:
if operator.has_higher_precedence_than(operand_1.get_operator()):
# Rebuild term to reflect higher operator precedence
term_1 = Term(operand_1.get_operand_2(), operator, operand_2)
term_2 = Term(operand_1.get_operand_1(), operand_1.get_operator(), term_1)
return term_2
# No operator precedence, build new term from left to right
term = Term(operand_1, operator, operand_2)
return term
def calculate_term(self, term):
operand_1 = term.get_operand_1()
operator = term.get_operator()
operand_2 = term.get_operand_2()
# Calculate operands recursively until we have a Number
while type(operand_1) is Term:
operand_1 = self.calculate_term(operand_1)
while type(operand_2) is Term:
operand_2 = self.calculate_term(operand_2)
# Calculate result
if operator == Operator.Addition:
sum = operand_1 + operand_2
return sum
if operator == Operator.Subtraction:
sub = operand_1 - operand_2
return sub
if operator == Operator.Multiplication:
mul = operand_1 * operand_2
return mul
if operator == Operator.Division:
div = operand_1 / operand_2
return div
return Number(0)
This code makes all our test cases pass.
It works in three steps:
- Build the first root term from the first three tokens.
- Update the root term by taking the current root term and the next two tokens.
- If the next operator has a higher precedence then the current root term, update the root term by creating a new term for the new operator. This will give this operator a higher precendence because its result will be calculated first.
- Otherwise create a new term with the current root term as the first operator. Thus the current root term will be calculated first.
- Calculate the result of the expression. Start with the current root term.
- Extract operands and operator.
- If an operand is a Term, call calculate_term recursively until the result is a Number.
- Calculate result by performing the operation specified by the Operand.
Overloading of Arithmetic Operators
You might have noticed that the implementation of calculate_term had been changed to return a Number instead of an intor a float. This was done so that calculate_term can be called recursively. This way, no conversion between Number and an integral data type was needed. This conversion is at the end of the calculation, in the last line of calculate.
As all calculations in this method are done with Numbers, it became necessary to overload the arithmetic operators for Number. This avoids having to call get_value multiple times in calculate_term, which clutters the code. Instead, we do it in the implementation of Number, which now looks like this:
class Number():
def __init__(self, value):
self.value = value
def __eq__(self, other):
return self.value == other.value
def __repr__(self):
return "Number with value: " + str(self.value)
def __add__(self, other):
return Number(self.get_value() + other.get_value())
def __sub__(self, other):
return Number(self.get_value() - other.get_value())
def __mul__(self, other):
return Number(self.get_value() * other.get_value())
def __truediv__(self, other):
return Number(self.get_value() / other.get_value())
def get_value(self):
return self.value
It is not necessary to add unit tests for the overloaded operators, because the implementation is very simple. It is thoroughly tested by the unit tests for calculate, which calls all of Number‘s methods. More unit tests would not add any more value here.
With all the tests green and the refactoring of Number completed, we can conclude the implementation of operator precedence.
Summary of Step Nine
In this step, we successfully implemented mixed operations. We did it by formalizing the concept of terms in a corresponding class. The challenge was to find an algorithm that builds a term tree while taking operator precedence into account. Once we formalized the algorithm, we first implemented the helper methods that we needed to write the algorithm in a convenient way. Then it was relatively easy to implement the algorithm and make the tests pass.
After successfully implementing mixed operations, only one item is left: Bracketed expressions. We will implement them in Step Ten.