Upgraded: Reverse Polish Notation with C#

I wrote a reverse polish notation tutorial for Dream In Code almost 2 years ago (wow that’s a long time ago!). The code only parsed for PI, E, numbers, the basic operators (plus, minus, multiply, divide), and the 3 basic trigonometric functions sine, cosine and tangent.

I’ve added more functions to it, and you can download the class here: ReversePolishNotation.cs

You can use the source code in a personal or commercial project. The disclaimer is that it’s given as is, and you’re ultimately responsible for what goes on in your project. Attribution to me (Vincent Tan) or a link to this blog is appreciated, but not necessary. Just do something awesome with it!

The new functions are

  • Absolute function
  • Arc sine (asin, inverse sine function)
  • Arc cosine (acos, inverse cosine function)
  • Arc tangent (atan, inverse tangent function)
  • Hyperbolic sine (sinh)
  • Hyperbolic cosine (cosh)
  • Hyperbolic tangent (tanh)
  • Square root function
  • Sign function

All in all, not very much added. But I’m using regular expressions to parse the input, so the more functions I support, the more complex the regular expression becomes. For example, I have to tell “sin”, “asin” and “sinh” apart. It’s harder because “sin” is a subset of “asin” and “sinh”.

Don’t get it? What if the input is “sing 1”? The parser should output 2 tokens, “sing” and “1”. It shouldn’t output “sin”, “g” and “1” (or “sin” and “g 1”, or whatever weird case that shouldn’t happen).

Anyway, I haven’t been to Dream In Code for a while now… and someone’s commented that the regular expression for detecting the unary minus should be changed. This was the original code (broken up for legibility):

sBuffer =
Regex.Replace(sBuffer,
@"(?<number>(pi|e|(\d+(\.\d+)?)))\s+MINUS",
"${number} -");

This was what that person suggested:

sBuffer =
Regex.Replace(sBuffer,
@"(?<number>(pi|e|(\d+(\.\d+)?)))\s+\)\s+MINUS\s+\(",
"${number} ) - (");

If I understand it correctly, he (or she) wants to catch the situation where the input has something like this:
( 5 ) – ( 3 )

I checked, and my original parsing would indeed fail. I do think he overparsed (I made that word up) though. He made the assumption that the next number is also encapsulated in a round bracket. It doesn’t have to. My code will fail for this too:
( 5 ) – 3

The error was in the right round bracket, so the corrected code is

sBuffer =
Regex.Replace(sBuffer,
@"(?<number>(pi|e|(\d+(\.\d+)?)))\s+(?<bracket>[)]?)\s+MINUS",
"${number} ${bracket} -");

Basically, I checked for the existence of the round bracket. Let me take it out for you to see it better:

(?<bracket>[)]?)\s+

Anyway, I’m putting the upgraded RPN code here because I’m going to shut down the site where I put it. I made a playground site called Ragnarok Code (now defunct). After months, I still only have the RPN code up.

Let me just say that writing articles is hard, and takes a non-trivial amount of time. So that site’s been stagnating, which ironically is the very thing I wanted my coding skills to not be. *sigh*

So have a play with an implementation of RPN while it’s still up.

P.S. I checked that person’s profile on Dream In Code. Seems like the only thing he did was comment on my tutorial. Wow, it must have bugged him really bad for him to register an account just so he could comment on my tutorial. After about 2 months, there’s no more activity from him. Maybe he got tired of waiting for a reply from me… oops…

Reverse Polish Notation with C#

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.