This is a medium difficulty problem in Leetcode. This is medium only if you are talking in terms of algorithm and time complexity. But let’s say you have to build a calculator for an enterprise. The calculator that will be extensible, maintainable and optimized at the same time.
How would you build such a calculator?
Well the first thing would still be coming up with the correct logic to solve the infix expressions entered by the user. But this is just a part. You would want your calculator to be extensible. Maybe you would want to add more and more operations to it. Also, you would want multiple developers to work on different operations at the same time so that you can reduce the overall time to market.
Now, that’s a tough one, isn’t it?
In this article, I would attempt to build this calculator in a similar manner using the Object oriented and SOLID design principles.
If you are not aware about the SOLID principles then follow the link.
Table of Contents
UML Design
I created a high-level UML design of the calculator. Just take a look at it and then we can go over it briefly.
The thought process behind this design is as follows:
- Operator: This is the interface that contains any behaviour associated with the operator. For example – BODMAS. This rule applies when we talk about operators. It could be an arithmetic operator or grouping operators. Therefore, the method precedence should get the precedence of the operator.
- Arithematic Operator: This interface is used to provide the abstraction for all the arithmetic operations (ex – addition, subtraction, multiplication, division).
- Basic Calculator: This calculator is the main calculator that the user interacts with. You can think of it as an orchestrator. It will aggregate Convertor engine and evaluate engine. For now, I’ve used InfixToPostFixConvertor as Convertor engine and ReversePolishNotation as the calculation engine.
With this our basic UML design is ready and we have something to proceed with. This is however not concrete and we might add, change or remove some of the attributes or classes later on (if required).
How to proceed with the development?
I always prefer to code in the TDD style. It means I write the test case first and then write enough code to make that test pass and move ahead one step at a time.
But even before that we have to make a decision whether we want to start coding from top-to-bottom or bottom-to-up.
Top to bottom typical means looking at the application from the eagle eye view and then move down the path. In our case it would be writing tests for the BasicCalculator first. And whenever we identify the new component, we will stop the BasicCalculator and move on to writing test cases for that new component.
Whereas in the bottom-up approach, we start by building the basic building blocks like Addition class, then subtraction class and then a pattern starts to emerge. Once we see the common pattern we extract an interface out-of-it. However, it sounds easy and straightforward but usually, I find it to be tough. Going this path means that you already know what you want from the system and you directly start building the smaller components.
For this BasicCalculator, I would like to proceed with the Top-Down approach.
It serves me well and helps me align my thoughts better.
Basic Calculator
This is going to be the starting point for the application. I’ll have a method calculate that will take the infix expression. This is the same expression that we are used to. For ex – 50 + (50 / 10) - 10.
Just to set a little bit of context for the code that you are about to read.
You will find two classes in use:
- InfixToPostFixConverter
- ReversePolishNotation (Postfix Expression Evaluator)
Now, why would I want to convert an infix expression to postfix?
Well, there is a very good reason, and that is Postfix doesn’t require any operator-driven order of operations; it’s always explicit. So for a stack-based compiler, it’s very easy to implement.
For humans it would make sense to say something like “Add A to B” rather than saying “A and B: Add Them”. But eh, I would chose postfix any time over infix.
And Reverse Polish Notation is just the PostFix Expression Evaluator that you will find below.
import lombok.RequiredArgsConstructor;
@RequiredArgsConstructor
public class BasicCalculator {
private final InfixToPostfixConverter infixToPostfixConverter;
private final ReversePolishNotation reversePolishNotation;
public int calculate(String infixExpression) {
String postfix = infixToPostfixConverter.convert(infixExpression);
return reversePolishNotation.eval(postfix.split(" "));
}
}Infix To PostFix Converter
I’ve shared the entire code for the same.
At first it might look daunting but just keep calm and read through the comments. The code is really simple.
And if you do not understand something then please do comment below, I will make sure to explain that part in detail.
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class InfixToPostfixConverter {
private static final Map<String, Operator> OPERATORS = Map.of(
"/", new Division(),
"*", new Multiplication(),
"+", new Addition(),
"-", new Subtraction()
);
private static final Map<String, GroupingOperator> GROUPING_OPERATORS = Map.of(
"(", new OpenParenthesis(),
")", new CloseParenthesis()
);
public static final String SPACE = " ";
private final ExpressionParser expressionParser;
public InfixToPostfixConverter(ExpressionParser expressionParser) {
this.expressionParser = expressionParser;
}
/**
* @param infixExpression
* @return
*/
public String convert(String infixExpression) {
List<String> tokens = expressionParser.parseInfix(infixExpression);
var output = new StringBuilder();
var stack = new LinkedList<Operator>();
for (String token : tokens) {
// if current token is an arithmetic operator
if (OPERATORS.containsKey(token)) {
Operator curr = OPERATORS.get(token);
// if the precedence of the current token is less than the top of the stack
// then pop from the stack and append it to the output
// then push the current token back into the stack
while (!stack.isEmpty() && less(curr, stack.peekFirst()))
output.append(stack.pop()).append(SPACE);
stack.push(curr);
}
// if the current token is a grouping operator
else if (GROUPING_OPERATORS.containsKey(token)) {
GroupingOperator currOp = GROUPING_OPERATORS.get(token);
if (currOp instanceof OpenParenthesis)
stack.push(currOp);
// if the current token is a closing parenthesis ')'
// then pop all the operators from the stack till you reach the opening parenthesis '('
// and add them to the output expression
else if (currOp instanceof CloseParenthesis) {
Operator curr;
while (! ((curr = stack.pop()) instanceof OpenParenthesis))
output.append(curr).append(SPACE);
}
}
// if current token is an operand
else output.append(token).append(SPACE);
}
// add remaining operators from stack to the output postfix expression
while (!stack.isEmpty())
output.append(stack.pop()).append(SPACE);
return output.toString().trim();
}
private boolean less(Operator op1, Operator op2) {
return op1.precedence().compareTo(op2.precedence()) <= 0;
}
}
Reverse Polish Notation (PostFix)
This is where the actual calculation takes place. The postfix expression is evaluated and the power of Object Oriented design kicks in.
Now, let’s say you have to add further operations. For example, you now want to add the powers operation to your calculator. All you have to do is create a new class (say PowerOfNumber) and append it to the arithmeticOperations map.
Well, that’s all you have to do. No if-else ladder, not complex logics to perform. And the code is perfectly modular.
And let’s say you want to remove some operation in the future, then simply remove it from your map. That operation won’t be processed.
import java.util.*;
public class ReversePolishNotation {
public Integer eval(final String[] notation) {
var arithmeticOperations = Map.of(
"/", new Division(),
"*", new Multiplication(),
"+", new Addition(),
"-", new Subtraction()
);
var operands = new LinkedList<Operand<Integer>>();
Arrays.stream(notation).forEach(token -> {
if (isANumber(token)) operands.push(new IntegerOperand(token));
else {
var b = operands.pop();
var a = operands.pop();
operands.push(new IntegerOperand(arithmeticOperations.get(token).eval(a, b)));
}
});
return operands.pop().get();
}
private boolean isANumber(String token) {
if (token.equals("-")) return false;
return token.chars().filter(c -> c != '-').allMatch(Character::isDigit);
}
}
I will give you one example operation for the addition and similarly you can code the rest for yourself. This will help you understand the structure and the flow of the application.
Addition Operation
Here is the Addition class that performs the addition of two numbers.
class Addition implements ArithmeticOperator {
@Override
public Integer precedence() {
return 1;
}
@Override
public Integer eval(Operand<Integer> a, Operand<Integer> b) {
return a.get() + b.get();
}
@Override
public String toString() {
return "+";
}
}Just like the Addition class you can code Subtraction, Multiplication and Division.
I would strongly recommend you to code those classes by yourself to learn and understand the overall flow and what’s happening in the background.
Showtime
Here’s the test case that I wrote for the BasicCalculator. I will execute the test case and we will see if we get the correct output.
class BasicCalculatorTest {
@Test
void itShouldEvaluateTheGivenExpressionAndReturnTheResult() {
String infixExpression = "(1+(4+5+2)-3)+(6+8)";
var expressionParser = new ExpressionParser();
var infixToPostfixConverter = new InfixToPostfixConverter(expressionParser);
var reversePolishNotation = new ReversePolishNotation();
var calculator = new BasicCalculator(infixToPostfixConverter, reversePolishNotation);
int result = calculator.calculate(infixExpression);
assertEquals(23, result);
}
}Here’s the result of the test case,
Conclusion
I chose this particular example to explain the power of object oriented programming and SOLID design principles because it is a perfect combination of complex parsing logic, infix to postfix conversion, expression evaluation and operand handling.
There is a lot of things going on in this small application. And I also find it a good mini-project to showcase your object-oriented skills with the proper implication of SOLID design principles.
If you are not aware about the SOLID design principles then do read the following article:
And if I would have done it in a procedure-oriented way then you would find a bunch of small functions lying around the space which will be getting called from all over the places. There would definitely be a lot many branches in the code which would make it difficult to read.