Page 1 of 1

Reverse Polish Notation in C# Avoiding recompilation and dynamic expression evaluation

#1 orcasquall  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 158
  • Joined: 14-September 07

Posted 14 October 2007 - 06:47 AM

Background
One of the basic tenets of good coding practices is design your programs to be data driven. Changing the data then changes the output, yet retaining the program logic. The program is thus written once, but can be used for a broad range of input values. The data is usually stored in text files or databases, outside of the source code.

Well, the values are usually simple, such as numbers and character strings. What if even calculation formulas can be stored? Instead of
double myvalue = 4.0 * Math.Sin(3.14159 / 2.0);

What if you could do something like this?
double myvalue = mymagicclass.Evaluate(“4 * sin(pi / 2)”);


The benefit of the above is that you can avoid recompilation. Suppose you find that the cosine function should be used instead of the sine function. You’d have to change your code and recompile
double myvalue = 4.0 * Math.Cos(3.14159 / 2.0);

“But it’s the same thing with the mymagicclass!” you exclaim.
Ahh, but what if it’s written this way
double myvalue = mymagicclass.Evaluate(stringfromtextfile);

And the text file contains “4 * sin(pi / 2)”. Then simply change the file contents to “4 * cos(pi / 2)”, and the program will automatically use the new formula.

There are two fields that benefit from this way of abstracting calculation formulas: game development and music visualisation. Games usually employ game scripts to drive the game events and calculations. With many code files and resources, build times can be long. Near delivery time, every second counts, so avoiding recompilation is good. Allowing non-programmers to easily change game mechanics by modifying text files is even better.

As for music visualisation, you know those pretty colours when you fire up a media player such as Windows Media player? Those colours are calculated with mathematical functions and expressions. But the player software is already compiled. How would additional patterns be added? A solution is using text files to describe those patterns. The program then reads in all the text files for all the available patterns. Add a new text file with a new pattern, and the program automatically uses the new pattern. Check out Sound Spectrum at http://www.soundspectrum.com/ for an example of how this is done.

The problem
So how do we read in a calculation formula and understand it in code? How do we read in “3 + 4” and know that the result is 7? The answer is to use reverse polish notation (RPN), also known as the postfix notation. It means the operators come after the operands.

For our example above, “3 + 4” becomes “3 4 +”. What’s the point of all this? Humans can tell that when we see the plus sign, we add the number before and after the plus sign together. Computers have a little bit more trouble, since the program reading “3 + 4” needs to backtrack when it hits “+” to find “3”. This is even harder when operator precedence and associativity come in. How would a program recognise that it’s supposed to do the multiplication first before the addition for “1 + 5 * 2”?

When “3 + 4” is rewritten to “3 4 +”, the evaluation algorithm reads in the string, and when it hits the “+”, it simply adds the two numbers before it. The RPN for “1 + 5 * 2” is “1 5 2 * +”. The evaluation algorithm then reads in stuff until it hits the first operator “*”. Then it multiplies the two numbers before it and shoves the result back in. So “1 5 2 * +” becomes “1 [5 2 *] +”, then becomes “1 10 +” (square brackets added to show the operation). Then it hits the “+”, and adds the two numbers before it and we finally get 11.

Now I present to you, coming all the way from Wikipedia, an algorithm for changing “3 + 4” to “3 4 +”, the Shunting yard algorithm
While there are tokens to be read:
   Read a token.

   If the token is a number, then add it to the output queue.

   If the token is a function token, then push it onto the stack.

   If the token is a function argument separator (e.g., a comma):
	  Until the topmost element of the stack is a left parenthesis, pop the element onto the output queue.
	  If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.

   If the token is an operator, o1, then:
	  while there is an operator, o2, at the top of the stack, and either
			o1 is associative or left-associative and its precedence is less than (lower precedence) or equal to that of o2, or
			o1 is right-associative and its precedence is less than (lower precedence) that of o2,
		 pop o2 off the stack, onto the output queue;
	  push o1 onto the operator stack.

   If the token is a left parenthesis, then push it onto the stack.

   If the token is a right parenthesis:
	  Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
	  Pop the left parenthesis from the stack, but not onto the output queue.
	  If the token at the top of the stack is a function token, pop it and onto the output queue.
	  If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

When there are no more tokens to read:
   While there are still operator tokens in the stack:
	  If the operator token on the top of the stack is a parenthesis, then there are mismatched parenthesis.
	  Pop the operator onto the output queue.
Exit.


And the RPN evaluation algorithm
While there are input tokens left
   Read the next token from input.

   If the token is a value
	  Push it onto the stack.

   Otherwise, the token is a function. (Operators, like +, are simply functions taking two arguments.)
	  It is known that the function takes n arguments.
	  So, pop the top n values from the stack.
		 If there are fewer than n values on the stack
			(Error) The user has not input sufficient values in the expression.
	  Evaluate the function, with the values as arguments.
	  Push the returned results, if any, back onto the stack.

   If there is only one value in the stack
	  That value is the result of the calculation.
   If there are more values in the stack
	  (Error) The user input too many values.



Looking through the algorithms, we notice that parentheses are also supported, meaning “(1 + 5) * 2” can be interpreted differently from “1 + 5 * 2”. We can even do functions, so “sin (3.14)” becomes “3.14 sin”. So the algorithms allow us to systematically change the original formula into something a program can systematically evaluate into a result. Then we notice that the terms “output queue” and “stack” are mentioned quite often. They refer to the data structures used to store tokens (we’ll get to explaining tokens a little later), the queue and the stack.

Data structures – Queues and Stacks
Queues and stacks are just ordered lists of objects. So “3 4 +” can be represented as three objects: “3”, “4” and “+”. Queues can be thought of as First-In-First-Out (FIFO). Imagine you’re queuing to buy cinema tickets (hence the name “queue”).
Attached Image

You, person A, by some stroke of good luck, happen to be first in line. Four other people come into the queue, but you get to buy your tickets first and get out of the queue first. Of course, this doesn’t account for inconsiderate people who jump queue, but queues in computer programs are very well behaved... :)

Stacks can be thought of as First-In-Last-Out (FILO). The usual example for explaining stacks is the “stack of plates”. You wash a plate A and put it on a table. You wash another plate B and put it on top of plate A. You then wash another plate C and put that on top of plate B. Somebody then needs a plate. You’re not going to pull out plate A from underneath, right? You’re going to take the topmost plate, plate C.

Well, I’ve got a more interesting example. Suppose there were five adventurers A, B, C, D and E, exploring the unlit dungeons of an (supposedly) uninhabited castle. A was the bravest of them all, so he’s designated the leader of the pack.
Attached Image

Being the geniuses that they were, they only had one lantern amongst them. So A carried the lantern and the others moved in a single file behind him. Unbeknownst to them, A led them into a dead-end corridor. By the time A realised the error, all of them had collided with each other. Since the corridor only had room for one person at a time, they had to back out starting from the last person E. By the time all of them got out of the corridor, wiping off cobwebs and sputtering curses, B, C, D and E were already reconsidering the wisdom of appointing A as their leader...

Hmmm... superheroes seem to act like stacks too. They’re the first in to dangerous situations, and they’re the last out of dangerous situations. Just a thought :) Ok, moving on...

Tokens
So we have an algorithm for systematically breaking down a string containing a calculation formula. So how do we write a program to recognise the different parts of the formula? How do we get a program to interpret “3 + 4” as three elements “3”, “+” and “4”?

A token is the smallest element with meaningful information. So “3” is a token, and it’s a number with value 3. “+” is a token, and it’s an addition operator. It’s more meaningful and easier to code if we enumerate the possible token types, so we have
public enum TokenType
{
	None,
	Number,
	Constant,
	Plus,
	Minus,
	Multiply,
	Divide,
	Exponent,
	UnaryMinus,
	Sine,
	Cosine,
	Tangent,
	LeftParenthesis,
	RightParenthesis
}


You should be able to understand how most of them fit into our program. We will be supporting the following tokens
- literal numbers, such as “3” or “1.618” or “98765.4321”
- constants, such as PI (3.14159) and the natural logarithmic base E (2.71828)
- operations: addition “+”, subtraction “-“, multiplication “*”, division “/”, exponentiation “^”
- basic trigonometry functions: sine, cosine and tangent
- left and right parentheses for operation control

You might notice there’s a unary minus. For example, a “-4” is interpreted as a negative four, and it can also be represented as “0 - 4". What if it’s “1 -4”? This is why we’ve got to check explicitly for this. The program won’t be able to tell the difference. It’s quite easy to check, using a method which I’ll explain a little bit farther down.

Then we have a struct to represent a token
public struct ReversePolishNotationToken
{
	public string TokenValue;
	public TokenType TokenValueType;
}


If the token is the number 3, then the value is 3, and the token type is TokenType.Number. We’re storing the value as a string because the constants can then be stored in their alphabetic representations “pi” and “e” instead of their actual numeric values. This saves the evaluation of actual values all the way to the end.

I’m sure you’ve done long math calculations where you leave something in a nice form (like a fraction such as 1/3 instead of 0.3333333) until the end of the calculation, and then you whip out your calculator to churn out numbers. This reduces rounding errors. Same idea here.

If the token type is not a number, then the value part is just unused.

Now that we’ve got a token structure to represent our tokens, how do we get those tokens? Traditionally, this involves storing the formula text into an array of characters and reading the characters one by one. Based on the value of each character, we then decide what to do and proceed with the next character.

So we could have “32 + 4” in an array
char[] ca = new char[]{‘3’, ‘2’, ‘ ‘, ‘+’, ‘ ‘, ‘4’};

Then we read “3”. Oh, it’s a number. Wonder if the next character is still a digit. Oh, it’s a “2”! What’s next? A space. So we’ve read in a “3” and “2”, so we’ve got a number 32. Next character is a “+”. Got to note somewhere to do addition. Reads in a space next (do nothing). Reads in a “4”. Ok, check if anymore digits. Oh good, none. So, noted somewhere that we need to do addition. Got a number 32 and a number 4. Aha! Add 32 and 4 together.

That is one long descriptive pseudo algorithm. The problem worsens if you want to take care of “sin”, “cos” and other functions. If you read in “s”, you’ll have to forward read the next two characters and check that they are “i” and “n” respectively. Doing all this backtracking and forward tracking requires a lot of if statements (probably nested) and even nested loops. Terrible.

So what can we do? This is where regular expressions come in.

Regular expressions
Regular expressions are useful for searching, extracting and even modifying text. For example, suppose we want to search for a web site address in a text string. Let’s assume that the format we want is “http://”, followed by any number of alphanumeric characters including the period “.” character, and ends with a “.net”. That is a very long way of saying we want to find something like “http://www.dreamincode.net”.

First, let’s go through some simple string patterns used in regular expressions.
\ is the escape character (you should be familiar with this if you do any C, C++ or C# programming)
\d matches any digit (0, 1, 2, 3, 4, 5, 6, 7, 8 and 9)
\s matches any whitespace character (spaces, tabs, newlines and so on)
\w matches any alphanumeric and underscore character
^ matches the start of a string
$ matches the end of a string
* matches the preceding pattern zero or more times
+ matches the preceding pattern one or more times
? matches the preceding pattern either zero or one time
. (the period character) matches any character except for the newline character
[a-e] matches any single character from “a” to “e”
[ae] matches any single character that’s either “a” or “e”
[^ae] matches any single character that’s NOT “a” nor “e” (compare with ^ for matching start of string)
cod(ing|er) matches either the word “coding” or “coder”

So for the web site matching example, we’d probably have “http://[\w.]+\.net”. The “\w” does the matching for alphanumeric characters. We also want to match the period character, so we “[\w.]”. We want to match “[\w.]” at least one time, so we get “[\w.]+”. Now the period is a special character, so we need to escape it. To match “.net”, we need “\.net”. Combining everything together, we get “http://[\w.]+\.net”.

There are many more patterns, but for our purposes, the above is sufficient.

So how do we describe a number? A number can be thought of as a series of consecutive digits, followed by a decimal point and another series of consecutive digits. The rule is that if there’s a decimal point, there must be at least one digit before and after the decimal point. So “023” and “4” are valid. “3.1415” and “9.87” are valid. But “.01” and “34.” are not valid. This rule is in place so our pattern matching efforts are easier.

We might try this “\d+\.\d+”, which means match at least one digit, followed by a period, followed by at least another digit. This only matches numbers with decimal points. However, “023” and “4” aren’t matched. Remember the question mark pattern, which matches the preceding pattern zero or one time? We do this “\d+(\.\d+)?”, grouping the “\.\d+” together because they must occur together. Then we use the question mark to note that either “(\.\d+)” occurs or not at all. So we match both “\d+” and “\d+\.\d+”, that is, integers as well as numbers with decimal values.

Breaking it down
So, the purpose of everything we’ve covered so far comes down to the following
1. We use regular expressions to extract the meaningful tokens from the calculation formula, and put a space before and after each token.
2. Then we use the string.Split() function with the space character as the delimiter to split the formula into an array (where each element is a string containing the token).
3. Then we run through this array and perform the Shunting yard algorithm, converting the array of tokens into postfix notation and storing them in queue and stack structures.
4. The final notation result is stored in a queue, so we run through the queue and do evaluation (using the evaluation algorithm).

The idea of step 1 is to separate each token with a space character between them. So “3+4” becomes “3 + 4”. Not a big deal you think? Until you consider “3+___4” or “____3+___4” (using underscores to represent spaces). Using regular expressions allows you to easily take care of a lot of conditions at once. With the space character as a delimiter, the formula text can be transformed into a string array of tokens easily with the string.Split() function. Ahhh, the power of regular expressions and .NET string functions combined...

Let’s look at the code first, and we’ll go through the explanations of the above steps as they come.

The code
We’ve finally covered enough material to actually see the code in action (woohoo!). First, I present to you the code that uses the class for RPN.
double result = 0.0;
MathText.ReversePolishNotation rpn = new MathText.ReversePolishNotation();
rpn.Parse("3+4*2/(1-5)^2^3");
result = rpn.Evaluate();
Console.WriteLine("orig:   {0}", rpn.OriginalExpression);
Console.WriteLine("tran:   {0}", rpn.TransitionExpression);
Console.WriteLine("post:   {0}", rpn.PostfixExpression);
Console.WriteLine("result: {0}", result);

Console.WriteLine();
rpn.Parse("-4.5* sin(-pi/6) + e -0.25");
result = rpn.Evaluate();
Console.WriteLine("orig:   {0}", rpn.OriginalExpression);
Console.WriteLine("tran:   {0}", rpn.TransitionExpression);
Console.WriteLine("post:   {0}", rpn.PostfixExpression);
Console.WriteLine("result: {0}", result);

Console.WriteLine();
rpn.Parse("-4^-2");
result = rpn.Evaluate();
Console.WriteLine("orig:   {0}", rpn.OriginalExpression);
Console.WriteLine("tran:   {0}", rpn.TransitionExpression);
Console.WriteLine("post:   {0}", rpn.PostfixExpression);
Console.WriteLine("result: {0}", result);


The usage is quite straightforward. You initialise the class, use the Parse() function, and then the Evaluate() function. We have the OriginalExpression (which is the uhm original expression), TransitionExpression (to store our working phase expression) and the PostfixExpression (which is the final expression after we’re done parsing).

The TransitionExpression and PostfixExpression are mainly for educational purposes (like in debugging) and not really used in the evaluation. The private queue variable is used instead. No point parsing the expression into a string in postfix notation and parse that string for evaluation.


Completed code can be downloaded by clicking link below.

Attached File(s)



Is This A Good Question/Topic? 2
  • +

Replies To: Reverse Polish Notation in C#

#2 Guest_ArtemOGRE*


Reputation:

Posted 22 March 2008 - 11:59 PM

Thanks for that tutorial work. Really helped me.

But I have a problem running my application not from IDE.
code string that contains
double.Parse()


throwing an exception when parsing string with floating point numbers like "2.1"
Changing of double.Parse() on my implementation killed problem.

This post has been edited by ArtemOGRE: 23 March 2008 - 12:00 AM

Was This Post Helpful? 0

#3 PsychoCoder  Icon User is offline

  • Google.Sucks.Init(true);
  • member icon

Reputation: 1642
  • View blog
  • Posts: 19,853
  • Joined: 26-July 07

Posted 23 March 2008 - 08:55 AM

Try using Convert.ToDouble()
Was This Post Helpful? 0
  • +
  • -

#4 Guest_ArtemOGRE*


Reputation:

Posted 24 March 2008 - 10:08 AM

Unfortunately, situation is the same wth Convert.ToDouble()
So, I use smth like that:
tokenvalue = System.Convert.ToDouble(dig[0]);
if (dig.Length==2)
	   tokenvalue += System.Convert.ToDouble(dig[1])/System.Math.Exp(dig[1].Length * System.Math.Log(10));


Know thats not good. But otherwise parsing works incorrect.
PS same error on Windows Mobile 5.0 .Net Framework 2.0.
Going to test my app. on university comps tomorrow.
Was This Post Helpful? 0

#5 herminator  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 04-March 09

Posted 08 March 2009 - 03:04 AM

Hi, The zip file seems corrupt , can somebody please upload a new one?
/herm

This post has been edited by herminator: 08 March 2009 - 03:06 AM

Was This Post Helpful? 0
  • +
  • -

#6 nganassan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 04-June 09

Posted 04 June 2009 - 08:49 AM

It seems to me that in Step 2 Unary operations chunk replacement has to be done also :

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

as '-' is here binary operation

initially
"...) - (..." to Unary gives "... ) ~ (..." which is not correct
Was This Post Helpful? 0
  • +
  • -

#7 madsnb  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 01-December 09

Posted 01 December 2009 - 05:27 PM

View Postnganassan, on 4 Jun, 2009 - 07:49 AM, said:

It seems to me that in Step 2 Unary operations chunk replacement has to be done also :

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

as '-' is here binary operation

initially
"...) - (..." to Unary gives "... ) ~ (..." which is not correct


Yeah I agree!

Could not figure out why I kept getting an exception while trying a simple infix like "20-((1+2)*4)-3..
Found out the same as you did. I solved it by adding like this:
sBuffer = Regex.Replace(sBuffer, @"(?<number>(pi|e|[)]|(\d+(\.\d+)?)))\s+MINUS", "${number} -");

In addition I modified the code so you can call parse and evaluate independently. Wanted to use it for a GUI where you can convert infix as one function and calculate result of postfix as another.

Really nice code though! :^:
Was This Post Helpful? 0
  • +
  • -

#8 nonggiatu  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 07-June 08

Posted 15 December 2009 - 08:01 AM

This is really a helpful tutorial for me. I and my friends have a winform exercise of calculating a formula. Can I write a tutorial in Vietnamese base on yours?
Was This Post Helpful? 0
  • +
  • -

#9 user_pz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 18-December 11

Posted 18 December 2011 - 10:26 PM

It fails on "3+4*2/(1-5)^2^3" expression. Moreover, what about variables with indexes? For example, "x0" or "y0". In your code it would be "x" "0" and "y" "0". And why does the program still work if i check wrong expression "sina(-pi)" where "sine" is not defined? udefined variables works too also :(

View Postuser_pz, on 18 December 2011 - 10:23 PM, said:

It fails on "3+4*2/(1-5)^2^3" expression. Moreover, what about variables with indexes? For example, "x0" or "y0". In your code it would be "x" "0" and "y" "0". And why does the program still work if i check wrong expression "sina(-pi)" where "sine" is not defined? udefined variables works too also :(


"3.0+4*2/(1-5)^2^3" i mean.
Was This Post Helpful? 0
  • +
  • -

#10 user_pz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 18-December 11

Posted 18 December 2011 - 10:38 PM

"3.0+4*2/(1-5)^2^3" i mean and "sina".
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1