This is a very basic algorithm which CS student must have came across. Whereas non-CS programmer may not aware its exsistence.
I learned it in my university lesson but never thoroughly implement it. Single digit without parentheses, unsigned integer, without UI doesn’t count.
So, I implement it to practice and see how am I difference from my school days. This implementation support nested parentheses, percentage, exponent, negative number and fractional number.
It is a procedure that start with re-organizing the expression so that parentheses are invisible and it is in evaluation priority descending order. And then you can easily evaluate that expression. You can somehow extend its ability by adding more supported operators.
You can use postfix or prefix(polish) notation, either one will do. I am going to use postfix notation because it actually matches the left to right order while evaluating it. And I think it is easier this way.
You will need a stack for this algorithm. I use .NET generic stack and which is great that is has Peek() to see what is on the top of the stack without poping it out.
You read the expression from left to right, one unit at a time, a unit can be an operator, a parenthese or an operand.
If you get an open parenthese, push it into the stack so that you can match with the close parenthese later.
if you get a close parenthese, pop the stack and append it to output expression until you have the open parenthese on the top of the stack. Remove the open parenthese from the stack, neither append any parenthese to your output expression nor push it into your stack.
If you get an operator, compare its priority with the stack top operator, while its priority is higher, pop the stack and append it to the output expression. Then push your current operator to the stack. Or if the stack is empty, push.
If you get an operand, append it to the output expression.
After the input expression is use up, append anything left in the stack to the output expression.
Here comes the part to evaluate the output expression. Read the output from left to right.
If it is an operand, push it into the stack. If it is an operator, pop out two operands, first one as right operand, second one as left operand, use the operator to evaluate these two. Push the result back. Get the answer from the stack when the output expression use up. That’s it.
Source code here, please do not hand it in as your assignment. All rights reserved.