How to analyse a algebraic expression

I am going to make a program that can analyse a algebraic expression.

For example:

<?php echo cal ('5*5+2*2'); ?>

My program will know that it will multiply 5 with 5 and 2 with 2 first, then plus them. I want to analyse it mysel开发者_开发技巧f, not by php.

I was going to suggest that you look at recursive descent parsers, but apparently things have moved on since I last did this in the mid 1980s. It appears that a Parsing Expression Grammar is the way to go now if you want to understand the theory behind it all.

If you couldn't care less about the theory, that's OK: implementing the theory means that you're going to end up writing a recursive descent parser anyway, so you can just do that :-)

You can take the 'infix' expression and using a stack, turn it into a 'prefix' or 'postfix' expression to decide order of operation (Parenthesis, Exponentiation, Multiplication or Division, Addition or Subtraction).

For example the expression ([5][ * ][5][ + ][2][ * ][2]) would be transformed into the postfix expression [5][5][ * ][2][2][ * ][ + ]. this 'postfix' expression can now be read as 'five and five multiplied, two and two multiplied, and then added together' which would preserve the order of operation.

Another way to think of the 'prefix/postfix' idea is that of multiple stacks. When you encounter the number 5, push it onto the primary stack. When you encounter the multiply symbol, store it in the secondary stack. When you get to the next 5, push it onto the primary stack, then pop all of the items off of your secondary stack and push them onto your primary stack.

Once you have the operators and operands in correct order, it's a matter of popping the items off the stack and then evaluating them.

I remember figuring out this problem in my Computer Science 102 course in college. Are you doing this for fun, or just trying to figure it out?