Math Parser, Part 1: Introduction

November 03, 2008 / category: Parsing / 2 comments

Everyone knows how to calculate value of a simple math expression, like "2 + 3 * 7". But not every programmer knows how to write a program that would accomplish the same task.

The first idea usually looks like this:

My eBook: “Memoirs of a Software Team Leader”
Read more »


result = get_number()
while operator = get_operator()
  operand = get_number()
  result = result operator operand
end

return result

It means: "read the expression from left to right and perform appropiate calculations when operator occured". Let's try this approach out on our previous example, "2 + 3 * 7":

get_number: 2

get_operator: +
get_number: 3
result: 5

get_operator: *
get_number: 7
result: 35

So we end up with 35 as the expected expression's value. Obviously, we are mistaken. The reason is simple: our algorithm does not preserve operator precedence. It would be acceptable for long additive operations chains like "5 + 6 - 7 + 2 - 1", but algorithm will fail on even slightly more complex expressions. It seems like we need a completely different approach.

Reverse Polish Notation

The notation that we used to know from school is called an "infix notation", since the operator is written between its arguments ("5 + 2"). But there are also other notations, like prefix notation and postfix notation. They are called "Polish notation" and "Reverse Polish notation", respectively. The first one was invented by Polish logician Jan Łukasiewicz, while the latter is complementary to the first one. The Reverse Polish notation (postfix notation) makes calculating expression value a whole lot easier. Let's look at an example of expression written using Reverse Polish notation:

5 2 +

As you can see, the operator is written after its arguments. Reverse Polish notation has two big advantages: it doesn't require to set operators' priority and it allows to compute the value of the expression using a simple algorithm. All we have to know is how many arguments does the specific operator require. Moreover, any expression written in Reverse Polish notation is unambigous, even without using parenthesis.

So, our first example, "2 + 3 * 7", looks like this when written in Reverse Polish notation:

2 3 7 * +

The algorithm that calculates value of the expression written in Reverse Polish notation is usually implemented using a stack. It consists of few simple steps:

while input_left
end

while symbol = get_symbol()
  if symbol.is_number?
    stack.push(symbol)
  elsif symbol.is_operator?
    arguments = pop_as_many_numbers_from_stack_as_the_operator_requires
    result = argument1 symbol argument2...
    stack.push(result)
  end
end

return stack.pop()

Let's follow these steps using our example, "2 3 7 * +":

read 2:
  push 2 on stack
read 3:
  push 3 on stack
read 7:
  push 7 on stack
read *:
  pop two numbers from stack
  got 3 and 7, calculate 3 * 7 = 21
  push 21 on stack
read +:
  pop two numbers from stack
  got 2 and 21, calculate 2 + 21 = 23
  push 23 on stack

return 23

Algorithm is quite simple, and it is also quite easy to implement. By the way, Reverse Polish notation calculator is a common task on a programming course at the beginning of computer science study (even if it is called a "Postfix calculator", it's still the same task). If you are looking for a ready-to-use implementation, read the Reverse Polish notation parser article.

Everything seems to be fine, but could you imagine yourself telling a spreadsheet's user: "Use postfix notation instead. It saves me a lot of work."?. Our deliberations have been interesting from theoretical point of view, but we need some practical solution for computing infix expressions' values. Of course, we could use an algorithm to convert expression from infix to postfix notation, but that's not what we were looking for. Why? Firstly, conversion itself is complicated. Secondly, what if we would like to evaluate something different than math expressions, e.g. procedure written in the programming language that we just invented?

We need a more general solution: the recursive parser. Stay tuned!

Comments

There are 2 comments / Submit your comment

dread_lord
May 27, 2012 05:29 PM

That is exactly what i was looking for. Thank you very much.

Math Parser User
November 28, 2013 03:45 AM

Excellent article. Clearly articulates the steps to parse mathematical expressions. I would like to add that if a user needs a parser to be implemented in many different languages, they may check out http://www.mathparsers.com Thanks.

You can use Markdown in your comments if you wish. Examples:

*emphasis*
emphasis
**strong**
strong
`inline code`
inline code
[My blog](http://lukaszwrobel.pl)
My blog
# use 4 spaces to indent
# a block of code
    def my_method(x)
      x = x + 1
    end
def my_method(x)
  x = x + 1
end

* First.
* Second.
  • First.
  • Second.

> This is a citation.
> Even more citation.

I don't agree with you.

This is a citation. Even more citation.

I don't agree with you.


Submit your comment

(required)

(optional)

(required, Markdown supported)


Preview:

My eBook: “Memoirs of a Software Team Leader”

Read more »