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.
這個程序要先重排你的算式,移除括號卻保留算式的運算順序.然後你就可以輕易的做計算.你可以增加支援的運算符去提升這演算法的計算方法.
你可以選擇用後置式或前置式去重排,任何一個都可以.我準備用後置式因為它真的是由左至右運算.而且我想它比前置式容易.
你需要一個堆疊去實作這個演算法,我用.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,請不要用來交作業. 版權所有.

Advertisements

Intelligence program is good program! 有智慧的程式就是好程式!

I have read and refactor quite a few projects/programs that coded by my colleagues or former colleagues. And of course refactoring my own projects source code too. Here is something that I feel deeply in my heart.
Just like how to define beauty, how to define what is a good program or coding practice is not something that has an exact correct answer. But there is some traces or characteristics which make you feel like, Ah~ this is good. On the contrary, some of them give you, Oh~ da#n it, you son of the bXtch!
There is one very remarkable thing that justify a program or source code between these two is, is the program smart or not?
我己經看過和重構過不少同事或以前同事的專案和程式.當然包括重構我自己的專案程式碼.這讓我深刻體會到一件事.
就正如怎樣去定義美一樣,要定義一個好的程式或者好的寫程式習慣並沒有一個標準答案.但會有一些蛛絲馬跡或特徵會讓你覺得,啊~這樣很好.相反地,有一些會讓你想罵,噢~他X的,你這X人!
這當中有一樣可以用作鑑定一個程式或程式碼是好是壞的東西,就是這程式聰明嗎?
If a program doesn’t do any checking or validation to the input, or do nothing about controlling the input, it is stupid.
If a programmer do not think about “what if something like that happen”, do nothing about it, for example, what if the connection is broken during some process, he is stupid.
If a program that doesn’t contain any setup or setting for the user when it should, definitely stupid.
If a programmer *assume* something or anything when writing the program, for example, assuming you have the administrator right. The outcome program will be very stupid.
If a programmer compile a program, success, and go through a perfect procedure using the program, telling you that he/she has done testing it. The program and the programmer is both stupid.
如果一個程式對輸入不做任何檢查或確認,又或者不去對輸入做控制,那就是蠢程式.
如果一個程式人員在寫程式時沒有去想”如果這樣的事發生呢”,也沒有對這件事做任何處理的話,例如,如果在某個函式運作途中斷線呢,這是個蠢人.
如果一個程式應該有些使用者設定而沒有提供任何介面或方法來做設定,明顯很蠢.
如果一個程式人員在寫程式時*假設*一些理想狀況或者其他條件,例如,假設你有管理員權限,那寫出來的程式一定很蠢.
如果一個程式人員認為程式編譯沒錯誤,然後經過一個完美的使用流程,跟你說這程式我測過沒問題.那這個程式和這個人都很蠢.
These sorts of look like stupid mistakes which you and I may think you will never make are the most command mistakes I encounter during my refactoring process. So what is going on?
You know what, stupid programs comes from stupid programmers.
這些看似很愚蠢的失誤,可能你和我覺得絕不可能發生在我身上,正正是最常我重構時出現在我眼前.到底怎麼了?
事情是這樣的,蠢程式的來源就是蠢人.

Setup IIS build-in FTP 設定IIS預設FTP

I am using 5.0 as an example. I setup FTP in server 2008 using IIS 7.0 too. There is not much difference.
First of all, I assume you have experience setting up FTP, using Filezilla server maybe. You have to setup basic settings like connection, port, etc. And then you add user/group’s access rights.
In FTP of IIS, it is a little difference. It use system accounts. So you have to turn on the FTP publish service and run the FTP. Go to control panel, add accounts for FTP users. You can then add virtual directory in the FTP station. You also need to go to that actual directory to do appropiate setting to the directory user rights. Then you also have to setup read/write permission in the FTP virtual directory. kind of clumbsy.
After going through all these, you can try to login with some thirdy-party FTP client. If it gives you a 5XX error telling you that your account is not correct. It may not be what it means. You have to turn off anonymous login from IIS FTP to use system account to login. Very Weird logic to me but M$ just love to do things in this way. Just get used to it…
我會用5.0版做例子.我在server 2008使用IIS 7.0版建立過FTP.方法也是大同小異.
首先,我假設你已經有架FTP的經驗,可能是Filezilla的.你要設定好連線方法,連接埠等.然後再設定使用者或群組的存取權限.
在IIS裡的FTP,會跟上述有點不一樣.它用的是系統帳戶.所以你要先打開FTP發佈服務然後啟動FTP.再進去控制台,幫FTP使用者加入帳戶.再把你想在FTP看到的目錄加入為虛擬目錄.還要到實際的目錄設定適當的使用者權限.然後還要去FTP對應的虛擬目錄設定讀/寫的權限.感覺很笨.
在處理好以上步驟後,你就可以用第三方FTP客戶端連看看.如果它傳你一個5XX錯誤.說你的帳號不正確.它可能並不是真正原因.你要去IIS的FTP裡把匿名登入關掉才能用帳戶登入.這真是一個很怪的邏輯,不過M$都喜歡搞這一套.習慣就好…