Simple arithmetic expression evaluation C# 簡單算式運算

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.
原始碼在這裡here,請不要用來交作業. 版權所有.

2 thoughts on “Simple arithmetic expression evaluation C# 簡單算式運算

  1. 真的非常的謝謝您,我找了好久終於找到完整的程式碼,

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s