這個是有成熟的算法的。不過需要將日常的四則運算表達式轉換為另外一種表示形式,稱為逆波蘭表達式。下面我們具體介紹一下。
我們日常的運算表達式通常是如下形式,這種成為中綴表達式,也就是運算符在運算數的中間。這種表達式人類人容易識別,并根據其進行計算,但計算機識別這種表達式非常困難。
a+b*(c-d)+e/f
因此,1920年,波蘭科學家揚·武卡謝維奇(Janukasiewicz)發明了一種不需要括號的計算表達式的表示法將操作符號寫在操作數之前,也就是前綴表達式,即波蘭式(PolishNotation,PN)。上述中綴表達式轉換為波蘭表達式的格式如下:
+a+*b-cd/ef
從上面表達式可以看出,運算符在2個運算數的前面,因此波蘭表達式也稱為前綴表達式。為了便于理解,我們給出一個具體的實例,這個實例將上面的字母換成具體的數字(1+2*(4-3)+6/2),這個結果很容易看出來,也就是1+2*1+3=6。然后我們看一下波蘭表達式的表示形式及運算過程。
+1+*2-43/62//從右向左掃描,當遇到運算符時計算其最近的右側2個運算數
+1+*2-433//先計算最右側的數據,也就是6/2=3
+1+*213//同理,4-3=1
+1+23//同理,2*1=1
+1+5
6
通過上面示例可以大概理解波蘭表達式的計算過程,上面的運算符和運算數就可以通過通用的數據結構進行計算(請自己思考一下,我們后面再介紹)。
什么是逆波蘭表達式
前面了解了波蘭表達式,那什么是逆波蘭表達式呢?波蘭表達式也成為前綴表達式,而逆波蘭表達式則成為后綴表達式,對比可以猜出來運算符在運算數后面的表達式就是逆波蘭表達式。上述表達式如果采用逆波蘭表達式則如下:
1243-*+62/+//計算方式正好相反,也就是從左向右掃描
121*+62/+
12+62/+
362/+
33+
6
從中綴表達式轉換為逆波蘭(后綴)表達式
從中綴表達式轉換為后綴表達式的流程如下描述。需要注意的是,經過處理之后,中綴表達式中的括弧將被消除,也就是只剩下+-*/數學運算符。
- 從左至右掃描一中綴表達式。
- 若讀取的是操作數,則判斷該操作數的類型,并將該操作數存入操作數堆棧
- 若讀取的是運算符
- 該運算符為左括號"(",則直接存入運算符堆棧。
- 該運算符為右括號")",則輸出運算符堆棧中的運算符到操作數堆棧,直到遇到左括號為止。
- 該運算符為非括號運算符:
- -若運算符堆棧棧頂的運算符為括號,則直接存入運算符堆棧。
- -若比運算符堆棧棧頂的運算符優先級高,則直接存入運算符堆棧。
- -若比運算符堆棧棧頂的運算符優先級低或者相等,則輸出棧頂運算符到操作數堆棧,并將當前運算符壓入運算符堆棧。
4.當表達式讀取完成后運算符堆棧中尚有運算符時,則依序取出運算符到操作數堆棧,直到運算符堆棧為空。
將中綴表達式轉換成逆波蘭表達式過程中,特別要注意對于中綴標到式中括號的處理。
- 要注意的,如果算符是"(",無論入棧中棧頂級別(只看棧頂)為何直接入棧,所以,“(”的等級
- 只用于對其后入棧的算符進行優先級比較,在“(”入棧時是無視優先級的。
- 在遇到")"時候找到最后進入的"(",并把"("前面所有的符號都壓入出棧。不能僅憑運算符的級別來判斷。
注:逆波蘭用的優先級有以下幾種,等級從高到低分別是:
1.*\
2.+-
3.(
4.)
上面關于流程的表示文字比較多,看起來可能比較頭疼。為了便于理解上述流程,我們依然通過上面的實例(1+2*(4-3)+6/2)進行介紹。在實際操作過程中需要一個棧和一個隊列,分別存儲運算符和操作數。
通過上面整個過程的描述,并結合算法,相信大家對中綴表達式轉換為后綴表達式(波蘭表達式)已經非常清楚了。
逆波蘭表達式的計算
逆波蘭表達式的計算就比較簡單了。以上面結果中的隊列為輸入,同時再準備一個棧用于運算。具體流程如下:
- 將隊列中的數據依次出隊,然后壓棧;
- 在出隊的過程中如果遇到運算符,則從棧中彈出2個運算數,分別作為右運算數和左運算數,進行運算;
- 將步驟2的運算結果入棧;
- 跳入步驟1,繼續進行出隊操作。
- 依然以上述內容為例進行介紹。
如圖1中第一行左側為形成的隊列,右側是一個空棧。將隊列中操作數依次出隊,入棧。
在出隊的過程中遇到運算符(-),此時將操作數出棧進行運算(注意這里操作數的順序)。
重復上述操作,直到將隊列中所有內容出隊。
綜上,我們可以通過將我們常見表達式字符串轉換為逆波蘭表達式,然后就可以通過計算機程序計算了。