04 October 2007

Wild (Geeky) Idea

This morning I got up and looked at my phone as I normally do to check for any new messages or emails. Of course, there weren't any as usual (I feel so lonely :( ), so went to my calculator to try to figure out what time I would need to start work in order to make it to class within a reasonable amount of time. That's about the time when I got my wild idea:
Most programmers know that to create a calculator that allows infix expressions such as 2+3 or 9*4/5 where the operators like +, -, *, and / are in between operands, you utilize a stack to parse those expressions so that it becomes a postfix expression like 23+ or 94*5/. I know that it probably is not a new concept, but I thought that they could be evaluated using binary expression trees. In other words, a binary tree would be built with the operator as the root and its operands as leaves. This allows for complex equations to be evaluated in order if you follow the tree from left-to-right, bottom-to-top. In fact, theoretically, this could lend itself to expression simplifers to simplify complex algebraic expressions and potentially allow the evaluation of abstract calculus equations (those equations using variables).
Now, you may be asking yourself "Why the heck would you be thinking about that first thing in the morning?" Well the answer is simple and has 3 parts: a) I'm a geek (the most important answer), b) I'm a programmer and want to utilize this idea for a graphing calcuator for my Windows Mobile-based phone, and c) because its interesting to see if what I've come up with really works.
But here's the thing: I don't want to come up with it all on my own and want to try to see if I can set up an open-source project for it. Well, if your interested and have ideas for it, please let me know. I'll probably start on it in a while, but I'm just brainstorming right now.


ajpapa.net said...

Sean. Actually as I remembered it in my CS classes you build a binary tree for each expression and then you use a stack to push each node in the binary tree to evaluate the expression.

Also my friend in college had a postfix calculator. He was insane with it. I could never get use to writting postfix notation.

Sean said...

Actually, the way I thought of it was going from the bottom of the tree to the top recursively, similar to a binary tree sort, except that the root would be the operator and have 2 children (operands), so 3(4+5)/2 would have the '/' operator as the root of the tree, then the left would have '(' (or implicit '*') as the root, 3 as its left child and '+' as its other child, then 4 and 5 as the leaves. Then you would evaluate up, so it would eval 4+5, bring the result up 1 level, then evaluate 3*9 and bring the result up again, then 27/2 and return the element. It basically evaluates using a bottom-up approach that recurively evaluates the left, then the right children, then itself and returns the result. No stacks needed (except the system stack which will hold each recursive call). Its actually pretty efficient and doesn't need to convert to postfix to evaluate the expression.