天天看點

逆波蘭式與表達式求值

何為波蘭式?何為逆波蘭式?

如何與表達式求值聯系起來?

波蘭式、逆波蘭式是資料結構和編譯原理裡面提到的知識點,我們平時的運算式都是這樣的 <code>2 + 3 * (5 - 1)-10(中綴表達式),這樣表達式易于閱讀和計算,但是對于計算機這樣就有點懵逼了。</code>

字首表達式: 比如<code>2 + 3 * (5 - 1)</code>這個表達式的字首表達式為<code>+ 2 * 3 - 5 1</code>來表示  波蘭表達式

中綴序表達式:比如 2 + 3 * (5 - 1)-10

字尾表達式:比如<code>2 + 3 * (5 - 1)</code>用逆波蘭式來表示則是:<code>2 3 5 1 - * +  逆波蘭表達式</code>

求表達式值:

  

問題可以轉換為周遊表達式用一個堆來存數字,當遇見操作符的時候,彈出兩個數字執行相應的運算,再壓入堆裡面,最後傳回出來的就是運算表達式的結果。

逆波蘭式與表達式求值

參考:http://www.programcreek.com/2012/12/leetcode-evaluate-reverse-polish-notation/