Creating Your Own Calculator for Fun and Profit
Have you ever wondered how to create a computer program that can understand arithmetic expressions like:
(3 + 11) * 5 - 21 / 7
and yield the right result?
As a human, such tasks seems incredibly easy: just perform 3 + 11 first and we will get 14, then 14 * 5 and we will get 70, finally we minus the result of 21 / 7 which 3 and we will end up with 67.
Easy as a piece of cake right?
OK, then try this:
(((6 + 422534 * 3) / 2 + 233) * 3 + 13) / 2
Unless you are some mad scientist, or a math genius, or your brain works in an insanely mysterious way, or, you are some unknown extraterrestrial life form, this won't be that easy.
But our omniscient Google still yields the result in a very short amount of time:
OK, OK, you can argue that with pen and pencil you can do this in a quite short amount of time as well, then what about something that's more than simple arithmetic expressions?
The powerful WolframAlpha can compute expressions like pow(233, 42) + 42! :
Hmm. This is interesting.
So, what if we can write a small program that can perform such calculation, so that we won't get lost when there is no internet connection, at the same time impress your friends in a very nerdy way, and better, be able to solve https://leetcode.com/problems/basic-calculator/, https://leetcode.com/problems/basic-calculator-ii/ and https://leetcode.com/problems/basic-calculator-iv/ to gain some programming interview credits, also start to understand how compilers and interpreters work?
What are we waiting for? Let's begin!
The Brute-Force Way
Let's design our program interface first, ideally we want the users of our calculator to use it like this:
calc = Calculator.new
puts calc.compute('(((6 + 422534 * 3) / 2 + 233) * 3 + 13) / 2')
# yields 951062
And in a minute, we dash out and create a Calculator class like this:
# brute_force.rb
class Calculator
def compute(expression)
eval(expression)
end
end
And it works!
[2] pry(main)> calc = Calculator.new
=> #<Calculator:0x00007fd2f6938570>
[3] pry(main)> calc.compute('(((6 + 422534 * 3) / 2 + 233) * 3 + 13) / 2')
=> 951062
So that's it. We have our first calculator and is super powerful. It relies on Ruby's Kernel#eval method, essentially allow you to run any ruby code, and of course, arithmetic expressions are just a subset of valid Ruby expressions.
In fact, our program is so powerful that it even has the power to destroy your computer:warning: do not try this at home!!!!!
calc = Calculator.new
calc.compute('require "fileutils"; FileUtils.rm_rf("/**")')
Maybe we can use some Regular Expression style blacklist or whitelist rules to ensure the given expression only contains valid tokens so that above example will not be valid, but it will never understand whether it is semantically correct, until we actually perform the calculation. For example, things like:
- consecutive or dangling operators:
1 + * 2or5 * 6 - - missing or mismatched parentheses:
1 + 2) * 3or(5 + 3 * () 1) + 2
They are all consisted of valid tokens only, but definitely are not valid arithmetic expressions.
So looks like we cannot cheat our way to finishing this program. Time to get serious.
The Domain-Specific Solution
Since evaluating arithmetic expressions is an ancient and thoroughly studied topic, we have very simple and efficient algorithms for it.
To get started, we need to understand two jargons:
Reverse Polish Notation
Reverse Polish Notation is also called "Postfix Notation".
Still not sure what that mean? Don't worry. When you realize that our everyday arithmetic notations like 1 + 2 * 3 are called "Infix Notations", because the operators are essentially "infixes", then "Postfix Notation" won't sound too strange after all.
The same expression written in Reverse Polish Notation looks like this:
1 2 3 * +
Our brain is trained to understand infix notations easily, but computers will have some difficulty understanding them. Reverse Polish Notation, on the contrary, is super easy for computer to understand.
In order for computer to evaluate an arithmetic expression written in postfix notation, we simply need a data structure called stack.
If you don't know already, stack is a simple data structure that normally only allow interacting with it's top, so you can either:
- push some object onto the top;
- pop an object from the top.
Think of it like a stack of plates you don't want to take some plates away from the bottom, or insert new plates into the bottom, do you?? or the Tower of Hanoi game where you can only interact with the topmost disk
Stack is very commonly used in computer science world, one of its most important usage is keeping track of your program's running state. That's why sometimes if your program has runtime errors, you will be greeted with the stack trace or stack dump. And sometimes, when your program has bad recursive calls, you will have StackOverflow.
Let's see how we can use a stack to evaluate postfix notations.
The algorithm in pseudocode:
while the token array is not empty:
take (and remove) the leftmost element of the array
if it is a number:
push onto the stack
else: (it is an operator):
pop two numbers from the stack
perform the operation on the two numbers
push result back onto the stack
endif
endwhile
result is the remaining element in the stack
Take our example 1 2 3 * +:
tokens = [1, 2, 3, *, +]
stack = []
take leftmost which is 1
current = 1
tokens = [2, 3, *, +]
stack = []
it is a number, push onto stack, and take next token
current = 2
tokens = [3, *, +]
stack = [1]
number again, push onto stack, take next:
current = 3
tokens = [*, +]
stack = [1, 2]
number again, push onto stack, take next:
current = *
tokens = [+]
stack = [1, 2, 3]
operator *, pop twice, perform 2 * 3
right = pop() => 3
left = pop() => 2
current = *
tokens = [+]
stack = [1]
push 6 onto stack:
tokens = [+]
stack = [1, 6]
operator +, pop twice, perform 1 + 6:
right = pop() => 6
left = pop() => 1
current = +
tokens = []
stack = []
push 7 onto stack:
tokens = []
stack = [7]
No more token, the remaining token on the stack is the result (7)
Simple and straightforward. Let's implement it in Ruby:
# rpn_evaluator.rb
class RPNEvaluator
def ev(tokens)
stack = []
until tokens.empty?
token = tokens.shift
case token
when Integer then stack.push(token) # token is number
when Symbol
right = stack.pop
left = stack.pop
stack.push ev_op(left, token, right) # token is op
end
end
stack.pop
end
def ev_op(left, op, right)
case op
when :* then left * right
when :/ then left / right
when :+ then left + right
when :- then left - right
end
end
end
And it works:
calc = RPNEvaluator.new
puts calc.ev([1, 2, 3, :*, :+])
# => 7
# infix: ((15 ÷ (7 − (1 + 1))) × 3) − (2 + (1 + 1))
# https://en.wikipedia.org/wiki/Reverse_Polish_notation#Example
puts calc.ev([15, 7, 1, 1, :+, :-, :/, 3, :*, 2, 1, 1, :+, :+, :-])
# => 5
Shunting-Yard Algorithm
So if we have a way to convert our arithmetic expressions from infix notation to postfix notation, we will have a way to evaluate them. The algorithm we need, is called Shunting-Yard Algorithm. According to Wikipedia, it can produce either a postfix notation string, also known as Reverse Polish notation (RPN), or an abstract syntax tree (AST).
We will discuss AST later. Interestingly, the Shunting-Yard Algorithm also depends on the usage of a stack. Wikipedia has a very nice illustration on how it works:
If you read the pseudocode on Wikipedia it may seem terrifying, but when we implement it in Ruby, it is not so scary:
# shunting_yard.rb
class ShuntingYard
def build_rpn(tokens)
output = []
operators = []
until tokens.empty?
token = tokens.shift
case token
when Integer then output << token
when :'(' then operators.push(token)
when :')'
while (top = operators.pop) != :'('
output << top
end
when :+, :-
until operators.empty? || operators[-1] == :'('
output << operators.pop
end
operators.push(token)
when :*, :/
while operators.size > 0 && [:*, :/].include?(operators[-1])
output << operators.pop
end
operators.push(token)
end
end
output << operators.pop until operators.empty?
output
end
end
Test it:
class Calculator
def initialize
@yard = ShuntingYard.new
@rpn_evaluator = RPNEvaluator.new
end
def compute(infix_tokens)
rpn_tokens = @yard.build_rpn(infix_tokens)
@rpn_evaluator.ev(rpn_tokens)
end
end
calc = Calculator.new
# 3 + 6 * 2 / (1 - 5)
puts calc.compute([3, :+, 6, :*, 2, :/, :'(', 1, :-, 5, :')'])
# => 0
Cross-reference with IRB:
[1] pry(main)> 3 + 6 * 2 / (1 - 5)
=> 0
[2] pry(main)>
It works.
In summary, for any given arithmetic expression written in infix notation, if we take following two steps:
- convert the expression from infix notation to postfix notation with Shunting-Yard Algorithm
- evaluate the postfix notation with a stack
Then we will have the result.
Generating Tokens with a Lexer
But wait. Remember at the beginning of our blog post, we mention that we want our program interface to be like:
calc = Calculator.new
puts calc.compute('(((6 + 422534 * 3) / 2 + 233) * 3 + 13) / 2')
# yields 951062
So instead of an array of tokens, the input should be a String.
Not a big deal, we just need to use some Regular-Expression-fu to convert the string into tokens.
In computer science, such process is called tokenization, or in a more professional term: lexing, which mean lexical analysis. A program that is capable of lexing the input string into tokens, is called a lexer. If the lexer detects illegal characters or invalid tokens, it can throw an error immediately.
With the help of StringScanner class in Ruby, we quickly come up with our hand written lexer:
# lexer.rb
require 'strscan'
class Lexer
REGEXP = /(\d+)|\+|\*|\/|\(|\)/.freeze
def tokenize(expression)
s = StringScanner.new(expression)
tokens = []
while s.scan_until(REGEXP)
token = s.matched
tokens << ((token =~ /\d+/) ? token.to_i : token.to_sym)
end
tokens
end
end
Done!?
Combining everything, we have:
# domain_specific_calc.rb
require_relative 'lexer'
require_relative 'shunting_yard'
require_relative 'rpn_evaluator'
class Calculator
def initialize
@lexer = Lexer.new
@yard = ShuntingYard.new
@rpn_evaluator = RPNEvaluator.new
end
def compute(expression)
infix_tokens = @lexer.tokenize(expression)
rpn_tokens = @yard.build_rpn(infix_tokens)
@rpn_evaluator.ev(rpn_tokens)
end
end
calc = Calculator.new
puts calc.compute('(((6 + 422534 * 3) / 2 + 233) * 3 + 13) / 2')
# => 951062
The Good, the Bad and the Ugly: What's Missing?
Some very smart readers may have already noticed that we have a bug in our implementation: we overlooked a very important case in everyday arithmetic expressions.
Let's look at another example:
calc = Calculator.new
puts calc.compute('-1 + 2')
Traceback (most recent call last):
3: from calc.rb:96:in `<main>'
2: from calc.rb:88:in `compute'
1: from calc.rb:28:in `ev'
calc.rb:39:in `ev_op': undefined method `-' for nil:NilClass (NoMethodError)
The reason of this bug is we are treating - here as a binary operator, but it does not have the left part of it.
One quick and dirty fix is we can change our lexer, so it generates [-1, :+, 2] instead of current [:-, 1, :+, 2]. To do so, we just need to update our REGEX to:
REGEXP = /(-?\d+)|\+|\*|-|\/|\(|\)/.freeze
But what if, the user wants to calculate:
-
--1which is arguably legit +233also arguably legit- or
- 1what's the harm in adding more spaces? - or
-(2*3)which is (almost) perfectly legit
If we still use current implementation, we need to update our algorithm significantly, mainly the Shunting-Yard part and the RPN evaluation part. Actually, the - here is considered a unary operator in this context, here is a StackOverflow post discussing this topic, free feel to take a look.
But hey, although our algorithm is not 100% perfect, it handles many cases already, and it allows us to solve
Which is something right?
But if we want to fix this problem, and at the same time solve:
https://leetcode.com/problems/basic-calculator-iv/
Which is expanding the expression like:
Or do things like what we've seen before:
We need new tools.
We Shape Our Tools, and Thereafter Our Tools Shape Us.
New Weapons: Language Built-in Toolkit
Let's look at our expression again:
(((6 + 422534 * 3) / 2 + 233) * 3 + 13) / 2
Virtually every mainstream programming languages understand expressions like those above, so maybe we can consult how language interpreters (when you run a ruby or python or javascript file, the program that's responsible of inspecting, understanding and executing your code, is called an interpreter) run those code.
In computer science, the language interpreters almost always take at least 2 steps to understand your code, they are, respectively:
- tokenization, also known as lexing (lexical analysis)
- parsing, also known as syntactic analysis
First the interpreter will lex our code into tokens, then run the tokens into a parser to understand the semantic meaning of the code.
The program that's responsible of parsing the tokens and form valid Syntax Trees is called a parser. We will discuss parser later.
We've already built a lexer in the first part of this blog post. By lexing, we normalize the expressions so that the presence or absence of whitespaces no longer matter. That is, this expression:
(3+11)* 5
albeit visually very different, will also yield the same tokens with (3 + 11) * 5. note: sometimes not 100% exact because language lexer often generates "whitespace" tokens as well, but it doesn't affect the semantics in our calculator context
Lexing to Get Tokens
In fact, with Ruby we have a built in lexer called ripper, let's see with Ruby what tokens our expression will generate:
require 'ripper'
require 'pp'
pp Ripper.lex('(3 + 11) * 5')
Here "pp" is basically a "prettier p," it formats a ruby object in a visually more pleasant way. When we run above code, it prints:
[[[1, 0], :on_lparen, "(", EXPR_BEG|EXPR_LABEL],
[[1, 1], :on_int, "3", EXPR_END],
[[1, 2], :on_sp, " ", EXPR_END],
[[1, 3], :on_op, "+", EXPR_BEG],
[[1, 4], :on_sp, " ", EXPR_BEG],
[[1, 5], :on_int, "11", EXPR_END],
[[1, 7], :on_rparen, ")", EXPR_ENDFN],
[[1, 8], :on_sp, " ", EXPR_ENDFN],
[[1, 9], :on_op, "*", EXPR_BEG],
[[1, 10], :on_sp, " ", EXPR_BEG],
[[1, 11], :on_int, "5", EXPR_END]]
As we see, Ruby generates a little more tokens space tokens, to be exact than our previous hand-written lexer because somehow it needs them, but you get the idea.
Parsing and Understand the Semantics
So we have the tokens, the next step is to parse the tokens and understand the semantic meaning of it.
Let's see how Ruby does it, again with ripper:
require 'ripper'
require 'pp'
pp Ripper.sexp("(3 + 11) * 5")
Produces:
[:program,
[[:binary,
[:paren, [[:binary, [:@int, "3", [1, 1]], :+, [:@int, "11", [1, 5]]]]],
:*,
[:@int, "5", [1, 11]]]]]
The arrays like [1, 1], [1, 5] are the source code locations for the token so the ruby interpreter can provide meaningful debugging information when needed.
Here sexp I swear I did not choose the name! means S-expression, which essentially is a tree. If we compare the sexp result to what Ripper.lex generates, you will see that lex only generates a flat array of tokens, which might or might not be valid syntax for an expression.
In computer science, a tree is not like your everyday trees, if you compare it to our natural mother earth trees, it's upside down. So the root is on the top, and it grows downwards, bending to the will of the gravity. In the image below, the root node is number 2, and it has two children, 7 and 5, each has more children:
So in a more humane visual representation, our expression tree looks like:
And if we have the tree, it will be very easy to evaluate the whole expression:
# ripper_calc.rb
require 'ripper'
require 'pp'
class Calculator
def compute(expression)
tree = Ripper.sexp(expression)
ev(tree[-1][0]) # only take first expression in the program body
end
private
def ev(node)
type, _ = node
case type
when :binary then ev_binary(node)
when :paren then ev(node[-1][0]) # ev the child of `paren` node
when :@int then node[1].to_i
end
end
def ev_binary(node)
_, left, op, right = node
case op
when :* then ev(left) * ev(right)
when :/ then ev(left) / ev(right)
when :+ then ev(left) + ev(right)
when :- then ev(left) - ev(right)
end
end
end
calc = Calculator.new
puts calc.compute("(3 + 11) * 5")
# => 70
The program may look a little bit daunting if you are not familiar with recursive style programming. If you are not very confident about it, feel free to Google around and run some experiments yourself then come back. (Promise me you will come back okay?
Here we walk the sexp tree, and depends on different node type, we use different strategies.
- for
binary, which is operations like+or*etc that involves two operands, we callev_binarymethod; - for
paren, we just need to callevagain on its child; - and for
@inttype, we just need to turn it into integer.
The Unary Node Type
So are we done? Let's add more tests.
puts calc.compute("((3 + 11) * 5 - 2) * 3")
# => 204
puts calc.compute("-2 * 3")
Traceback (most recent call last):
3: from sexp.rb:36:in `<main>'
2: from sexp.rb:8:in `compute'
1: from sexp.rb:16:in `ev'
sexp.rb:25:in `ev_binary': undefined method `*' for nil:NilClass (NoMethodError)
Of course, the unary type.
If we try '-1', it generates:
[:unary, :[email protected], [:@int, "1", [1, 1]]]
And for --1 yes it is valid! it generates:
[:unary, :[email protected], [:unary, :[email protected], [:@int, "1", [1, 2]]]]
Which makes sense as well. unary is a kind of operator that only involve one operand, common unary operators are - and +. So let's update our code to accept unary node types.
# ripper_calc.rb
require 'ripper'
require 'pp'
class Calculator
def compute(expression)
tree = Ripper.sexp(expression)
ev(tree[-1][0]) # only take first expression in the program body
end
private
def ev(node)
type, _ = node
case type
when :unary then ev_unary(node)
when :binary then ev_binary(node)
when :paren then ev(node[-1][0]) # ev the child of `paren` node
when :@int then node[1].to_i
end
end
def ev_binary(node)
_, left, op, right = node
case op
when :* then ev(left) * ev(right)
when :/ then ev(left) / ev(right)
when :+ then ev(left) + ev(right)
when :- then ev(left) - ev(right)
end
end
def ev_unary(node)
_, op, child = node
case op
when :[email protected] then ev(child)
when :[email protected] then -ev(child)
end
end
end
calc = Calculator.new
puts calc.compute("(3 + 11) * 5")
# => 70
puts calc.compute("((3 + 11) * 5 - 2) * 3")
# => 204
puts calc.compute("-2 * 3")
# => -6
puts calc.compute("--1")
# => 1
puts calc.compute("+1 + 2")
# => 3
Fabulous! Now we have a fully functional calculator, we should be proud of ourselves! It will be very easy to extend our example to support floating point arithmetics as well, we are not going to do it here, and it is left for you as an exercise.
But wait. Essentially we are cheating here as well, because we now rely on the ripper library which is Ruby specific. What about other languages, like Python?
The Pythonic Way
With Python, we don't have direct access to the lexer, but by using the ast module, which is essentially combining lexing and parsing steps, we get similar result:
import ast
import astpretty
tree = ast.parse('(3 + 11) * 5')
# only show the expression, and ignore token position in source code
astpretty.pprint(tree.body[0], show_offsets=False)
yields:
Expr(
value=BinOp(
left=BinOp(
left=Num(n=3),
op=Add(),
right=Num(n=11),
),
op=Mult(),
right=Num(n=5),
),
)
here we use an open source library called astpretty to have prettier result.
ast actually means Abstract Syntax Tree. By forming such tree, Python already parsed and ensured the code is semantically meaningful.
That means, like Ripper.sexp, the AST will be of valid syntax, for example if we try to parse 3 + 11) * 5 missing parenthesis we will have an error:
Traceback (most recent call last):
File "ast_example.py", line 6, in <module>
tree = ast.parse('3 + 11) * 5')
File "/Users/forresty/.pyenv/versions/2.7.9/lib/python2.7/ast.py", line 37, in parse
return compile(source, filename, mode, PyCF_ONLY_AST)
File "<unknown>", line 1
3 + 11) * 5
^
SyntaxError: invalid syntax
It will be very easy to write our Calculator in Python as well:
# ast_calc.py
import ast
import operator
class Calculator(ast.NodeVisitor):
_BIN_OP_MAP = {
ast.Add: operator.add,
ast.Sub: operator.sub,
ast.Mult: operator.mul,
ast.Div: operator.div
}
_UNARY_OP_MAP = {
ast.UAdd: operator.pos,
ast.USub: operator.neg
}
def compute(self, expression):
tree = ast.parse(expression)
return self.visit(tree.body[0])
def visit_Expr(self, node):
return self.visit(node.value)
def visit_BinOp(self, node):
left = self.visit(node.left)
right = self.visit(node.right)
return self._BIN_OP_MAP[type(node.op)](left, right)
def visit_UnaryOp(self, node):
child = self.visit(node.operand)
return self._UNARY_OP_MAP[type(node.op)](child)
def visit_Num(self, node):
return node.n
calc = Calculator()
print(calc.compute('(3 + 11) * 5'))
# => 70
print(calc.compute('(+3 + 11) * 5'))
# => 70
print(calc.compute('(-3 + 11) * 5'))
# => 40
print(calc.compute('(--3 + 11) * 5'))
# => 70
print(calc.compute('(-(3 + 11)) * 5'))
# => -70
Above code adapted from StackOverflow, how it works is left as an exercise for you as well. hint: Read the Documentation
Diving Deeper: RLTK
But wait, we are still using the language construct itself ripper and ast to build the syntax tree therefore we are limited to the language itself, which makes it not so easy to extend. say, remember at the beginning of the article, what if we want more advanced math expression like, pow(233, 42) + 42! ?
So let's dive deeper, and write our own Parser.
With Ruby we have a very powerful language toolkit: RLTK, which is a collection of classes and methods designed to help programmers work with languages in an easy to use and straightforward manner.
Essentially arithmetic expressions are a very simple domain-specific language, so we definitely can use this.
By reading its README.md we already found a calculator example, with a little modification:
# rltk_calc.rb
require 'rltk'
class Calculator
class Lexer < RLTK::Lexer
rule(/\+/) { :PLS }
rule(/-/) { :SUB }
rule(/\*/) { :MUL }
rule(/\//) { :DIV }
rule(/\(/) { :LPAREN }
rule(/\)/) { :RPAREN }
rule(/[0-9]+/) { |t| [:NUM, t.to_i] }
rule(/\s/)
end
class Parser < RLTK::Parser
left :PLS, :SUB
left :MUL, :DIV
production(:e) do
clause('NUM') { |n| n }
clause('LPAREN e RPAREN') { |_, e, _| e }
# unary
clause('PLS e') { |_, e| e }
clause('SUB e') { |_, e| -e }
# binary
clause('e PLS e') { |e0, _, e1| e0 + e1 }
clause('e SUB e') { |e0, _, e1| e0 - e1 }
clause('e MUL e') { |e0, _, e1| e0 * e1 }
clause('e DIV e') { |e0, _, e1| e0 / e1 }
end
finalize
end
def initialize
@lexer = Lexer.new
@parser = Parser.new
end
def compute(expression)
tokens = @lexer.lex(expression)
@parser.parse(tokens)
end
end
And test it:
calc = Calculator.new
puts calc.compute('5 * (2 + 20 / 4)')
# => 35
puts calc.compute('5 * (-2 + 20 / 4)')
# => 15
puts calc.compute('5 * (--2 + 20 / 4)')
# => 35
See? So easy!
And now we can extend it to support our custom syntax:
class Calculator
class Lexer < RLTK::Lexer
# ...omitted
# extension
rule(/,/) { :COMMA }
rule(/pow/) { :POW }
rule(/!/) { :FACT }
end
class Parser < RLTK::Parser
left :PLS, :SUB, :POW # added
left :MUL, :DIV, :FACT # added
production(:e) do
# ...omitted
# extension
clause('e FACT') { |e, _| (1..e).reduce(1, :*) }
clause('POW LPAREN e COMMA e RPAREN') { |_, _, base, _, exp, _| base ** exp }
end
finalize
end
end
And voila! Now we have:
calc = Calculator.new
puts calc.compute('1 + pow(2 * 3, 4) * 50 - (4 + 2*5)!')
# => -87178226399
Which seems legit...
Let's cross reference with WolframAlpha:
It works!
Wrapping Up
But in fact to fully understand this is not easy, and we have a big brick to describe how everything work. The RLTK syntax is simple and intuitive, I highly recommend you to run some experiments. We are not going to explain everything here, and in fact, in the future hopefully we will have a full series of posts describing how to create your own programming language.
So this wraps it up. If you are still reading this, congratulations, you should be proud of yourself! Your hard work and persistence will definitely pay off in the future. (if they haven't already)
The source code of this blog post lives on GitHub, if you have any feedback feel free to drop me a message at [email protected]