如何分析代数表达式

Question

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 myself, not by php.

Answer 1

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?