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:

https://www.google.com/search?q=(((6+%2B+422534+*+3)+%2F+2+%2B+233)+*+3+%2B+13)+%2F+2

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! :

https://www.wolframalpha.com/input/?i=pow(233,+42)+%2B+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 + * 2 or 5 * 6 -
  • missing or mismatched parentheses: 1 + 2) * 3 or (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:

  1. push some object onto the top;
  2. 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

source: https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues

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:

source: https://en.wikipedia.org/wiki/Shunting-yard_algorithm

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:

  1. convert the expression from infix notation to postfix notation with Shunting-Yard Algorithm
  2. 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:

  • --1 which is arguably legit
  • +233 also arguably legit
  • or -                                1 what'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:

https://www.wolframalpha.com/input/?i=(a+%2B+1)+*+(b+%2B+2)+*+(c+%2B+3)

Or do things like what we've seen before:

https://www.wolframalpha.com/input/?i=pow(233,+42)+%2B+42!

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:

  1. tokenization, also known as lexing (lexical analysis)
  2. 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:

source: https://en.wikipedia.org/wiki/Tree_(data_structure)

So in a more humane visual representation, our expression tree looks like:

tool used: Monodraw

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 call ev_binary method;
  • for paren, we just need to call ev again on its child;
  • and for @int type, 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, :-@, [:@int, "1", [1, 1]]]

And for --1 yes it is valid! it generates:

[:unary, :-@, [:unary, :-@, [:@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 :+@ then ev(child)
    when :-@ 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:

https://www.wolframalpha.com/input/?i=1+%2B+pow(2+*+3,+4)+*+50+-+(4+%2B+2*5)!

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 afu@forresty.com.