What is reverse polish notation? It means rewriting a mathematical expression into a postfix notation form. For example, “1 + 5 * 2” is rewritten into “1 5 2 * +”.
Why would anyone want to do that? I actually wrote a C# tutorial on this at Dream In Code, with my explanations there. I wanted to make it really comprehensive, so I edited and reedited my draft. The draft turned out to be more than 4000 words, and that’s not even including the code segments.
Well, apparently the forum engine couldn’t handle my long article, so it’s been shortened. And I really worked hard at the article too…
Anyway, someone at the forum asked something about the Mandelbrot fractal and how to generate colours to make it “pretty”. I gave my take on the matter, but somehow I felt more could be said. It reminded me of a time back in the past …
I was young and full of drive and found the music visualisation in Windows Media Player mesmerising. So I researched on how I could make my own music visualisation software. I needed it to take on different patterns, and I didn’t want to hardcode stuff in.
It was at this point where I stumbled upon reverse polish notation (RPN). RPN allows me to form mathematical expressions and evaluate them in the program code. I was working with C then, so I had
for loops and lots of forward and backward checks going through every single character when reading in the expression.
It was terrible. When I got an “s”, I had to check if the next two characters were “i” and “n” respectively, then I could be sure it’s a sine function. I couldn’t find my C code anymore, but I remember that I got it working.
Basically, tokenising the expression was the hard part. Once the tokens were obtained, parsing the expression and evaluating it was easy.
So, back to my tutorial. That question about Mandelbrot fractals got me thinking, “Maybe I can write something on RPN?” With C#, I could use regular expressions to recognise all the different tokens available. So I did that. The thing was, explaining RPN wasn’t the hard part. Explaining the queue and stack data structures, and how regular expressions worked, is. And I used the better part of my tutorial explaining that. We’re going for comprehensive here.
There are two things I left out in the tutorial. One is the use of variables in the expression. The other is adding more functions. Right now only sine, cosine and tangent are supported. The regular expressions used won’t be able to handle hyperbolic sine “sinh” for example. It would fail to recognise whether a token was “sin” or “sinh”. Oh well, maybe another tutorial…
The complete code can be downloaded at the tutorial page.