I have just recently completed my stack math parser for OST2. I started this morning by looking at some examples that I found in my Java book that showed using infix/postfix expressions for operations. The book didn't give any code, however, so I had to implement everything myself (which was the funnest part, if I may add).
But now that I have it done, I'm quite happy, it parses all of the basic programming operators, including:
+ - / * % && || & | ^ == != >= <= > <
and also supports infinite layers of parenthesis (till you run out of ram or something)
Also, because it is a 3-part process to generate the result, I can now compile the math operations at PreRun time in my OST2 compiler, and then process the stack at execution time, which will be a tremendous gain in speed.
Run-down
The 3 parts include:
Part 1
parse the original string IE: "3+43*(324/975.243)>0&&32<54-3"
This step returns a list of all of the operators and values from the string
Part 2
Compile the list: This is the part of the algorithm that works the magic, it takes the list, processes it, and outputs a postfix expression for the original infix expression. This gets incredibly complex when processing this many different operators, as you need to handle order of ops and also the fact that you can have as many layers of parenthesis as you choose.
But anyways, it compiles the list in to a list of values and operators which are placed in a perfect order for processing efficiently and fast.
Part 3
The third and final step is to just run through the list and process each of the operators until you hit the end of the list, then you just read the last value of the stack (which there should only be one of if everything worked correctly) and that is the result!
Detailed Example
So here's a more detailed example of what's going on:
You start off with the string, we'll say:
3*(6+2)
Now by looking at this, we know that the answer should be 24, so we'll just remember that to check our answer in a bit...
Next we parse the string, so we run through the string and when we hit one of the operators, we chop out the value before it and append that on to an infix list, and append the operator on to the list after that. We continue doing this until we hit the end of the string, at which point we return the list we created.
So now our list should look like this:
Value: 3, Operator *, Operator (, Value: 6, Operator +, Value 2, Operator )
or more condensed:
3, *, (, 6, +, 2, )
As you can see we've basically just chopped up the list in to each separate operator/value.
Then the compilation process is very tricky, as we need to make it recursive so that we can have parenthesis, so I'm not going to explain that here, i'd have to write a few pages to explain it all correctly.
But anyways, after compiling the list, we should have a postfix list that looks like this:
3, 6, 2, +, *
As you can see we eliminated the parenthesis from the list, this simplifies the calculations later on.
So when we actually want to calculate the result, we run through the list like so:
Step 1:
pull value: 3
push it on the stack (Stack: 3)
Step 2:
pull value: 6
push it on the stack (Stack: 3, 6)
Step 3:
pull value: 2
push it on the stack (Stack: 3, 6, 2)
Step 4:
pull operator: +
Pop op2: 6
Pop op1: 2
ADD op1+op2==8
Push result: 9 (Stack: 3, 8)
Step 5:
pull operator: *
Pop op2: 8
Pop op1: 3
MUL op1*op2==24
Push result: 24 (Stack: 24)
Step 6:
We're done! Pop the last value off the stack and that's our answer!
So there you have it, that's a simple example of a stack-based calculator.
I'm including with this post a zip that includes two exes, both do the same thing, however, one displays the output as it processes everything, and the other does it silently and calculates the time to calculate everything.
Hopefully you learned something from this little pseudo-article
-Jeff Verkoeyen
-edit-
Please note that this is a rough put-together of the parser that will be implemented in my OST2 Interpreter, so it assumes that the string you give it is devoid of errors, and free of whitespace.
So while 3+3 would work, 3 + 3 might not work, but sometimes it will.
Also make sure that your strings are syntactically correct, so 3+*/-3 would not work, and *might* crash the parser. So just make sure that the string that you pass in is correct and free of whitespace.
