「Felys」簡易腳本語言【逆波蘭】
【概述】
逆波蘭表達(dá)式轉(zhuǎn)換和計算可以說是Felys中最核心的部分，因為他可以將字符串形式的表達(dá)式解析出其中的邏輯并加以計算，并且我進(jìn)行了一些魔改使其用起來和其他編程語言的表達(dá)式幾乎沒差異，如果你看不懂逆波蘭表達(dá)式轉(zhuǎn)換的話，強(qiáng)烈推薦去網(wǎng)上了解一下，會有很多非常細(xì)致的講解，這里篇幅原因只會不會大量展開。
【流程】
讀取，如果需要賦值，拆分變量名和表達(dá)式
將表達(dá)式中空格去除，并在將負(fù)數(shù)轉(zhuǎn)化為零減這個數(shù)
處理好的表達(dá)式轉(zhuǎn)化為逆波蘭表達(dá)式（字符串形式存儲）
解析數(shù)字和變量，同時利用棧的特性對逆波蘭式進(jìn)行計算
得到計算結(jié)果，如需賦值則賦值，返回表達(dá)式最終的結(jié)果
【第一步】
賦值符號可以隨意定制，我這里用的是小于號和連接符的組合，畢竟我覺得賦值和等價是兩回事，之前有個教授一直在強(qiáng)調(diào)是a variable is assigned the value而不是variable equals a value，影響深刻。這一段代碼相當(dāng)基礎(chǔ)，直接看圖。
【第二步】
在開始第二步之前，有必要介紹一下token函數(shù)，這個函數(shù)要求你輸入一個字符，返還給你一個整型，這個返回值就是優(yōu)先級：0代表數(shù)字和字母，1～3是三種不同的操作符，-1是括號，？則是未知。在標(biāo)準(zhǔn)化的過程中遇到問好會報錯，空格自動跳過。
由于逆波蘭表達(dá)式轉(zhuǎn)換的時候是不存在負(fù)數(shù)的，所以我們要把-x轉(zhuǎn)化為0-x的形式，這里我們會遇到兩種特別的情況。
a/-b或者a+-b，我們需要能正確的修正為a/(0-b)和a+(0-b)，不然這在逆波蘭轉(zhuǎn)換時是災(zāi)難性的bug
如何正確解析-(a+b)+c為(0-(a+b))+c，這個后括號的位置顯然不能簡單的放在負(fù)號后面第一個數(shù)字的后面
判定邏輯都在代碼注釋里自己看，這里主要講一下這里棧的作用。括號本質(zhì)也是層層相扣先進(jìn)后出，完美吻合棧的特性。不過這次棧中儲存的是計數(shù)器，即一個前括號被讀取之后，后面又遇到了多少前括號，如果計數(shù)器歸零（即要被彈出）了，就說明這個前括號所對應(yīng)的后括號可以加上去了，不然就得等夠的后括號之后才能被彈出。里面用到了一個特殊的函數(shù)stkone就是對全棧進(jìn)行自增或自減，畢竟不論是先進(jìn)還是后進(jìn)的括號計數(shù)器，只要遇到前括號，那就是所有都多遇到了一個前括號。運(yùn)行完成之后得到的字符數(shù)組，就是我們逆波蘭轉(zhuǎn)換算法能穩(wěn)定運(yùn)作的標(biāo)準(zhǔn)輸入。前提是你的棧清干凈了，沒清干凈就代表用戶輸入錯誤。
【第三步】
真正的轉(zhuǎn)換從這里開始。前文我提了無數(shù)次逆波蘭表達(dá)式，所以這究竟是什么？它的另一個名字叫后綴式，顧名思義就是把運(yùn)算符寫在數(shù)字的后面，比如我們常用的中綴式a+b在后綴式中就是ab+，通過一定的組合之后，后綴式可以做到完全不用括號，也能完全表達(dá)出一個式子的含義，比如a*(b+c)在后綴式中即可寫為abc+*，計算時我們必須要先結(jié)算bc+，因為ab后面沒有運(yùn)算符，計算后我們得到了ad*（假設(shè)d是bc+的值），最后就可以得到我們想要的結(jié)果了，你可能覺得沒啥用，但是這對于計算機(jī)而言卻極容易運(yùn)算，畢竟計算機(jī)并沒聰明到可以隨心所欲的找括號再一步一步計算。如果你有興趣的話可以去網(wǎng)上查閱相關(guān)資料，然后自己練習(xí)練習(xí)就能理解這種運(yùn)算方式的優(yōu)勢了。
背景知識補(bǔ)充完，接下來就可以開始轉(zhuǎn)換了。首先要明確一點(diǎn)，后綴式是把運(yùn)算符寫在后面，對于其中每一個數(shù)字的排列順序是完全不用動的，我們需要考慮的只有調(diào)整運(yùn)算符的位置。想到這里，第一步已經(jīng)呼之欲出了，即遍歷表達(dá)式時遇到數(shù)字直接存進(jìn)container之中。為了讓讀者循序漸進(jìn)地理解，我們姑且先不考慮括號問題，只考慮基礎(chǔ)的四則運(yùn)算優(yōu)先級即乘除大于加減。簡單的排列組合，我們可以得到以下四種情況：
a+b*c轉(zhuǎn)化為abc*+；中綴式中的優(yōu)先級為+小于*
a*b+c轉(zhuǎn)化為ab*c+；中綴式中的優(yōu)先級為*大于+
a+b+c轉(zhuǎn)化為ab+c+；中綴式中的優(yōu)先級為+等于+
a*b*c轉(zhuǎn)化為ab*c*；中綴式中的優(yōu)先級為*等于*
注意：3和4可以轉(zhuǎn)化為abc++和abc**，但這樣相當(dāng)于先算bc+和bc*，與中綴式的從左到右邏輯不符合，我們不把這種混淆視聽的寫法考慮在內(nèi)。
仔細(xì)觀法就會發(fā)現(xiàn)，當(dāng)前面一個的運(yùn)算符的優(yōu)先級大于等于后一個時，他們的輸出其實是一樣的，都必須在c寫入之前提前把運(yùn)算符丟進(jìn)去；只有當(dāng)前面一個的運(yùn)算符的優(yōu)先級小于等于后一個時，可以直接無腦輸出數(shù)字在無腦出運(yùn)算符?，F(xiàn)在邏輯理通順了，就可以嘗試用計算機(jī)來轉(zhuǎn)換了。
如你所料，我們再一次會需要使用棧來臨時存放運(yùn)算符，再次提醒，當(dāng)遇到數(shù)字的時候，直接存入container即可，只需要關(guān)注好運(yùn)算符就行。這里我們會遇到三種情況：
空棧，直接把運(yùn)算符壓棧
棧頂優(yōu)先級小于當(dāng)前運(yùn)算符，直接壓棧
棧頂優(yōu)先級大于當(dāng)前運(yùn)算符，彈出全部內(nèi)容到container直到觸底（或者遇到括號，稍后展開講括號），然后再把自己壓棧
對照我們前面的邏輯，完全吻合，至于第三種情況為什么是直接輸出到觸底，你可以自己去嘗試一下a+b*c+d的情況就可以理解了。最后在完成的時候，我們還需要把棧中剩下的內(nèi)容全部彈出到container即可。如果你是第一次學(xué)這個東西，覺得有些步驟看不懂，要多嘗試一下把邏輯徹底弄通就好，邏輯這種東西很多時候只能意會。如果你完全理解這個邏輯，你可以非常簡單的支持比較符，它的優(yōu)先級應(yīng)當(dāng)比加減還要低。
現(xiàn)在我們只差最后一步了，解析括號。然而括號的解析其實異常簡單。因為你可以把括號理解為棧中棧，當(dāng)你壓入一個括號的時候，括號外的東西都與你無關(guān)，在里面繼續(xù)進(jìn)行對于四則運(yùn)算的解析，而后括號就是結(jié)束這個棧中棧的時候，也就是把剩余的全部彈出進(jìn)container直到這對括號的結(jié)束，即棧彈到左括號的時候。
這一步結(jié)束之際，我還是想說一下，我寫這一段的價值不是帶你細(xì)致地過一遍逆波蘭表達(dá)式轉(zhuǎn)換算法，而是當(dāng)你在查閱相關(guān)資料時看不懂的地方，你可以來看看我這邊額外的思路。
【第四步】
終于來到實際計算的地方了，你沒猜錯，我們還是需要借助棧的幫助來完成。在這里你只需要知道后綴式子的一個特點(diǎn)即可：不論運(yùn)算到哪一步，遇到的第一個運(yùn)算符前面必然有兩及以上的數(shù)字。根據(jù)這條定理，我們只需要遍歷container，把數(shù)字進(jìn)行字符串轉(zhuǎn)數(shù)字后直接壓棧（遇到字母則認(rèn)為是變量名，直接去變量庫里面取值），如果遇到了運(yùn)算符，我們則取出棧頂兩次，運(yùn)算，再壓回去，直到遍歷完成。如果輸入正確的話，棧中應(yīng)該只有一個數(shù)字，便是結(jié)果，返回即可。
注意：在計算的時候，比如bc-，在棧中表現(xiàn)為棧頂是c，第二層是b，如果按照順序取彈出的話，第一個值為c，第二值為b，你要用第二個值去減第一個值才行，或者你可以像我一樣運(yùn)用好數(shù)學(xué)改寫成負(fù)的第一個值加第二個值，乘除和比較符同理。
【第五步】
我們終于得到值，根據(jù)第一步的情況，如果要賦值就去賦值，最后在返還這個表達(dá)式的值給主程序就好了方便后面的判定。
【總結(jié)】
這一部分涉及了三套算法做三件事情，是Felys語言中最復(fù)雜抽象的一章，如果你對棧不熟悉的話，相信通過這次你一定能玩轉(zhuǎn)棧操作的，畢竟這也是我第一次實際應(yīng)用棧，真的花了我很多時間研究。記得多去外面查查資料。
