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.

這個程序要先重排你的算式,移除括號卻保留算式的運算順序.然後你就可以輕易的做計算.你可以增加支援的運算符去提升這演算法的計算方法.

你可以選擇用後置式或前置式去重排,任何一個都可以.我準備用後置式因為它真的是由左至右運算.而且我想它比前置式容易.

你需要一個堆疊去實作這個演算法,我用.NET附的泛型堆疊.它有一個很好的方法Peek()讓你可以不用彈出也能看到堆疊最上面的內容.

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,請不要用來交作業. 版權所有.