TOPTAL Calculator

Introduction

This project is part4 of the interview for joining Toptal.

Specification

Text of the task is given in the file task.txt

Technology

Calculator is implemented in Scala programming language. ScalaFX library was used for Calculator's GUI implementation and sbt for project building.

Requirements

• Java 8
• ScalaFX 8
• Scala 2.11
• sbt 0.13.8

Run calculator

Enter the project folder and type:

sbt run

Tests

Code is developed by applying TDD and tests are located in folder /src/test/scala-2.11, For running all tests enter the project folder and type:

sbt test

Tests Coverage

Class	Class %	Method %	Line %
Calculator	100% (9/ 9)	100% (13/ 13)	96.3% (52/ 54)
LinearEquation	100% (3/ 3)	100% (6/ 6)	95% (38/ 40)
ShuntingYard	100% (4/ 4)	100% (7/ 7)	100% (34/ 34)
TokenParser	100% (1/ 1)	100% (2/ 2)	100% (10/ 10)

Library dependencies

• scalatest - test driven development
• scalafx - modern library for GUI
• scala-logging - for logging

More details about project libraraies (e.g. version etc..) can be found in file build.sbt

Logs

Logs are located in logs folder. Log settings are located in resources/logback.xml

ScalaDocs

ScalaDocs can be generated by entering project folder and typing:

sbt doc

ScalaDoc will be generated in folder scalaDoc. Open file index.html in browser in order to start browsing projects documentation

Using a calculator

After running calculator will show up in the center of the screen as shown on the next image:

Buttons

Here's the list of the available buttons:

•     to     are numbers
•     are used for linear equation
•     clear, delete all
•     operations
•     logarithm
•     brackets
•     point for floating point numbers
•     calculate!

Functionality

Calculations

This functionality supports addition, subtraction, multiplication, division, log on floating point and integer numbers.

e.g.

(2+(4-1))*5

A number of samples is given in test file CalculatorSpec.scala.

Source files that are implementing this functionality are:

• Calculator.scala
• TokenParser.scala
• ShuntingYard.scala

Calculator.scala object has 2 methods : calculate and rpn. Method calculate is a high level
workflow that goes from receiving input string, parsing it to tokens, transforming to postfix and evaluating. All these sub-functionalities are handled in separate methods. e.g. method rpn evaluates postfix expression.

Normally humans tend to enter math expressions in inflix notation and that is what is expected as input to calculator. However , machines are more suitable for evaluating postfix notation so workflow of data goes like this:

• get inflix notation as input
• create tokens by applying regex (method getTokens from Object TokenParser)
• transform tokens to postfix notataion (method infixToPostfix from Object ShuntingYard)
• Finally evaluate postfx and return value to GUI (method rpn from Object Calculator)

Probably the most interesting part is ShuntingYard algorithm. High overview of algorithm is:

1. Loop through the tokens
2. In case of operand, push to the operand stack
3. In case of operator: While there is an operator on top of the operator stack of precedence higher than or equal to that of operator we are currently processing, pop it and apply. Next, push the current operator on the operator stack.
4. When we get to the end of the formula, apply any operators remaining on the stack, from the top down. Then the result is the only item left on the operand stack (assuming well-formed input).

Here are few good resources for understanding this algorithm in details:

• oxfordmathcenter
• wikipedia

For evaluating that posfix notation again stack is used and it is pretty straight forward as shown in method rpn in file Calculator.scala Here , the biggest catch is to make sure that logarithm is unary operand.

Simple linear equation

Calculator also supports solving linear equations. For simplicity, only addition and multiplication operations are allowed as described in the task text.

Here's example of the linear equation:

2 * x + 0.5 = 1    , and response should be x=0.25

This functionality is located in these classes:

• ShuntingYard.scala
• LinearEquation.scala

ShuntingYard was again used for creating postfix notation as in standard calculator mode. Interesting part related to equation solving is actually located in LinearEquation.scala

Main idea is to transform both sides of the equation to the form:

m1 * x + b1 =  m2 * x +b2

From this form it is very easy to isolate variable x

x=  (b2 - b1) / (m1 - m2)   

which is solution to linear equation.

So main obstacle is to transform left and right side of equation to the form : m * x + b In order to accomplish this task similar way of evaluating was used as in method rpn from file Calculator.scala Again data structure Stack has proved useful. However , in this case it is not possible to evaluate pieces of the expression and push to the stack cause value of x variable is not known.

Solution to this problem is to represent all non operation tokens as two elements Array which represents m and b. These arrays will be pushed and popped from the stack e.g.

variable        x ->  (1,0)

expression:  2*x+1 -> (2,1)

number:     4.2 ->  (0,4.2)

Next , we have to define rules for applying binary operands (+,*) in this space on Array(m0,b0) and Array(m1,b1)

For addition (+) rule is:

Array(m0,b0) + Array(m1,b1)  = Array(m0 + m1,b0 + b1)

For multiplication (*) rules are:

if(m0>0) ->   Array(m0,b0) * Array(m1,b1) = Array(m0 * b1,b0 * b1)

and

if(m1>0) ->   Array(m0,b0) * Array(m1,b1) = Array(b0 * m1,b0 * b1)