I am working on an article which covers how algorithms translate into code. The two algorithms I’m using are a variation of Dijkstra’s “Shunting Yard Algorithm” for the postfix to infix conversion, and the [URL=“http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_postfix_algorithm”]postfix evaluation. This is also a good exercise for people new to data structures. A little stack-based arithmetic to play with too.
The source is in a state for people to play with and I’ve managed to keep the code pretty readable.
The code is attached, but here is the usage.
trace( new ExpressionParser().parse( "(1+(100/10))*3" ) ); // 33
The features are basic (to say the least):
- addition, subtraction, multiplication, division
- grouping
- multi-digit operands
If I (or you) were to take this any further I’d consider:
- negative operands from input (ie. -3+4)
- exponents
- basic math functions (ie. cos(), sin(), round(), floor(), whatever())
(attaching didn’t work … I don’t know why)
http://iamavila.com/dontdelete/expression_parser.zip
- I included the Polygonal data structures … more than was necessary, sorry I’m lazy.
