２ｏ１０年２月電腦學習第１期
司慶福』
程書偉摘要：論述了表示式求值相關暮法的實現過程及分析。關鍵詞：表示式求值計算機敦值適算中圖分類號：ｔｐ３１２
文獻標識碼：ａ文章編號
ｓｌｑｉｎｇ￣
１表示式求值介紹
示。目前常用的表示式種類主要包括中綴表示式與字尾表中綴表示
字尾表示
達式兩種。中綴表示式即平常使用的數學表示式，如：ｌｘ３ｘａｂ＋
ａｂ＋（５＋２）一７，特點是符合人類的思維習慣，使用者使用起來很
順手。字尾表示式又稱為逆波蘭式，是波蘭邏輯學家
於１９２９年提出的另一種表示表示式的方法，按從上面的例子可以看出：
此方法，每一運算子都置於其運算物件之後，故稱為字尾表（１）在兩種表示中，運算物件出現的順序相同．
示。這種表示法的乙個特點是，表示式中各個運算是按運算
（２）在字尾表示中，運算子按實際計算順序從左到右符出現的順序進行的，故無須使用括號來指示運算順序，因排列，且每一運算子總是跟在其運算物件之後。
而又稱為無括號式。下面對照地給出一些表示式的兩種表由於原來提出的是字首表示，即把每一
沒有音軌。在實際使用過程中，有時會出現無法儲存為ｍｐｖ格式的情況，這時可先將其轉換為ｍｐｇ格式，再用超級解霸３５００開啟ｍｐｇ檔案，重新利用上述方法將其轉換為ｍｐｖ格式。
值得注意的是，該步轉出的**最終格式必須為ｍｐｖ格式，因為ｍｐｇ格式無法被ｐｒｅｍｉｅｒｅ正確載入進行**格式編輯與匯出
在ｐｒｅｍｉｅｒｅ中載入已擷取的ｍｐｖ檔案，將其依次拖到時間線上，即可實現多**編輯。關於更多的資訊，可參考
ｐｒｅｍｉｅｒｅ的幫助檔案及相關書籍，本文不再過多介紹。
多**檔案在ｐｒｅｍｉｅｒｅ中編輯後，可用ｅｘｐｏｒｔ進行**檔案匯出。值得注意的是匯出要選擇而
圖１ｅｎｃｏｄｉｎｇ中ｃｕｓｔｏｍ的詳細設定
不是匯出預設為ａｖｉ格式**，轉換速度慢且
插入到ｐｐｔ頁面中去。ｍｐｖ格式的主要優點是可隨意改變會嚴重影響**檔案清晰度中選擇ｆｏｌｄｅｒ，**的橫縱比而不像ａｖｉ等多**格式無法改變橫縱比。
ｅｎｃｏｄｉｎｇ中選擇ｃｕｓｔｏｍ，詳細的設定如圖ｌ所示。經實際使
３結束語
用比較，兩種匯出方案在轉換速度上相差至少６ｏ倍。
本文應用超級解霸３５００和兩款圖ｌ中要勾選否則可能會出現無法導
軟體實現了將ｄｖｄ高畫質素材應用到ｐｐｔ中的無損轉換。推出的情況。匯出的檔案格式為ｖｏｂ，存放在匯出資料夾的
薦使用。
ｖｔｄｅｏ
＿ｔｓ資料夾內。
參考文獻
２．３超級解霸３５００檔案格式轉換及匯入ｐｐｔ中
【１１超級解霸３５００幫助文件．】
利用２。１中的方法，將ｒｏｂ格式轉換成ｍｐｖ格式。在幫助文件．ｐｐｔ中應用插入一影片一檔案中的影片，即可將多**素材
ｆ３】ｍｉ凹幫助文件．
收稿日期：２００９一ｌｌ—ｌ９
司慶福大慶師範學院計算機系本科生（黑龍江，大慶ｌ６３７ｌ２）。
１２７運算子置於其運算物件之前。例如，中綴式ａ＋ｂ和相應的字首表示分別為因此，為了區分字首和字尾表示，通常將字尾表示稱為逆波蘭表示。
根據以上兩種常用表示式的表示方法，可以得到兩種表示式求值的演算法。為了簡化問題，便於理解，這裡只進行加、減、乘、除以及加括號的表示式求解。
２中綴表示式求值
首先，四則運算的規則如下：（１）先乘除，後加減；（２）從左到右算：（３）先括號內，後括號外。
任何乙個表示式都由如下三部分組成：運算元（ｏｐｅｒａｎｄ）和操作符以及界限符一）。
一般運算元可以是常數，也可以是變數，運算子包括算術運
算符和邏輯運算子，本文只討論算術運算子。界限符包括左右括號以及表示式結束符等。在這裡將運算子和界限符統
稱為算符，並將他們的集合命名為ｏｐ。根據四則運算的規則，在每一步運算中，任意兩個出現的算符ｘ，ｙ之間有如下關係：ｘ＜ｙｘ的優先順序低於ｙｘ＝ｙｘ的優先順序等於ｙｘ＞ｙ
ｘ的優先順序大於ｙ
假設輸入的表示式沒有錯誤，則實現中綴表示式求值的演算法如下：
定義兩個棧ｏｐｎｄ，０ｐｍ，分別存放運算子和運算數。
基本思想是：一次讀入表示式的每個字元，若是運算元則進棧（ｓｔａｃｋ２），若為操作符則與棧ｓｔａｃｋｌ中的棧項運算子比較，此處設表示式中當前掃瞄到的操作符為ｘ，ｓｔａｃｋｌ中棧頂操作符為ｙ．則有如下兩種情況：
（１）ｘ＜ｙ或ｘ＝ｙ運算元棧出棧兩次，得到兩個運算元
ａ、ｂ，運算子棧出棧一次，得到操作符ｍ，對ａ、ｂ進行ｍ運算，將結果入運算元棧（ｓｍｃｋ１）。
（２）ｘ＞ｙ此時操作符入棧。
重複進行，一直掃瞄到表示式尾部為止．
（３）針對四則運算的第三條規則，定義「（的優先順序最低，「）」的優先順序最高，並且當掃瞄到「）」時一直計算到運算子棧中的「（」出棧為止。
（４）由於按照演算法最後總有一步運算沒有計算，如３（５＋２）一１５最後運算子棧中有乙個「×」，運算數棧中為２１、５，所以在表示式的頭和尾各新增乙個輔助運算子「＃」，
從而輔助演算法計算。
演算法實現如下：
ｃｏｍｐｕｔｅ（）ｉ）：
囂 ）｛
｛不是運算子則進棧
ｌｅｌｓｅ
ｃ８８ｅ，＜∥棧頂元素優先權低
ｃｂｒｅａｋ；
ｃａ８ｅ，－
脫括號並接受下乙個字元ｐ叩ｉ
ｃａｓｅ ，：∥退棧並將運算結果入棧
叩（ｏｐｎｄ￣）；
ｐｉｌ量
ｂｒｅａｋ；）｝
１．ｐｒｅｃｅｄｅ：判定運算子棧的棧項運算子ｘ與讀入的運算子０之間的優先關係的函式進行二元運算ｘ０ｙ的函式。一
例如求解３（７－５）＋３的運算過程如下：
一表示式字串處理後為：檔ｌｉ（７—５）＋
表１步驟 ｏｐｉｒ棧 ｏｐｎｄ棧掃瞄字元
操作乙 （）３＃（３７
一７）４撐
＃（．一＃６
＋ｐｕｓｈ（ｏｐｔ凡，＋ ）８桴＋
６３群９
群ｒｅｔｕｒｎ ９
３字尾表示式求值
字尾表示式值分為兩步，首先將中綴表示式轉化為字尾表示式，然後對字尾表示式求值。
把中綴表示式轉換為字尾表示式演算法的基本思路是從頭到尾地掃瞄中綴表示式中的每個字元，對於不同型別的字元按不情況進行處理。
將加減運算子的優先順序設定為１，乘除運算子的優先順序
（６）當掃瞄到８ｌ中的，＠ 字元時，ｓ２和ｒ為：
ｒ：１０
ｓ：＠一
（７）當整個處理過程結束後，ｒ棧為空，ｓ２為一＃，字尾表示式中每個元素都用空格隔開。
設定為２，在棧中儲存的特殊運算子和 （的優先順序設定
為０。則運算過程如下：
（ｉ）若遇到的是空格則認為是分隔符，不需要進行處
理。字尾表示式求值的演算法相對於中綴表示式要簡單，其演算法思想為：
（２）若遇到的是數字或小數點，則直接寫入到ｓ２中，並（１）若表示式是運算數，則入棧。
在每個數值的最後寫入乙個空格。
（３）若遇到的是左括號，則應把它壓入到運算子棧中，待以它開始的括號內的表示式轉換完畢後再出棧。
（４）若遇到的是右括號，則表明括號內的中綴表示式已
經掃瞄完畢，把從棧頂直到儲存著的對應左括號之間的運算子依次退棧並寫入ｓ２串中．
（５）若遇到的是運算子，則有：
①當該運算子的優先順序大於棧項運算子的優先順序時，表明該運算子的後乙個運算物件還沒有被掃瞄也沒有被放入到８２串中，應把它暫存於運算子棧中，待它的後乙個運算
物件從ｓｌ串中讀出並寫入到８２串中後，再令其出棧並寫入８２串中。
②若遇到的運算子的優先順序小於或等於棧頂運算子的優先順序，表明棧頂運算子的兩個運算物件已被儲存到ｂ２串中，應將棧頂運算子退棧並寫入到８２串中，對於新的棧頂運算子仍繼續進行比較和處理，直到被處理的運算子的優先順序大於棧項運算子的優先順序為止，然後讓該運算子進棧即可。
按照以上過程掃瞄到中綴表示式結束符，群時，把棧中剩餘的運算子依次退棧並寫入到字尾表示式中，再向８２寫入表示式結束符鋒和字串結束符整個轉換過程就處理完畢，在８２中就得到了轉換成的字尾表示式。
例如，設中綴算術表示式８１為使用的運算子棧用ｒ表示，則轉換過程如下：
（１）開始時存放字尾表示式的字串ｂ２為空，ｒ中壓
入有算符，它具有最低的優先順序０。
ｓ；ｒ：＠
（２）當掃瞄到ｓ１中的左括號時，ｓ２和ｒ中的資料變化如下：
ｓ：ｌ ｏ
ｒ：＠＋（
（３）當掃瞄到８１中的數值３時，ｓ２和ｒ中的資料變化為：
ｓ：ｌ ｏ
（４）當掃瞄到８ｌ中的右括號時，ｓ２和ｒ變為：
ｓ：ｌ ０
ｉ８ ９ ３
＋ｒ：＠＋
（５）當掃瞄到８１中的數值１５時，ｓ２和ｒ又變為：
（２）若表示式是運算子，則出棧兩個數並對這兩個數進
行運算，將結果入棧。
演算法描述為：
ｃｏｍｐｕｔｅ（）
（廝籠初始化
麒入乙個運算數或運算子審）（
ｆ砌果ｃ是運算數，則將其轉換為數值**棧
ｊｅｌｓｅ
｛叩礎棧兩個運算
數，並且進行運算
腐運算結果入棧ｌｌ｝
４結束語
這兩種方法各有優缺點。中綴表示式的特點是符合人類的思維習慣，而字尾表示式卻更有利於計算機求值，便於進行程式設計。但是讓使用者直接輸入字尾表示式也不現實．所以通常的折衷方案是將中綴表示式轉化為字尾表示式後求值。
對於非互動系統（即輸入是事先設計好的，儲存起來的系統）來說，更是可以將轉化後的字尾表示式儲存在儲存器
中，從而提高系統效能，又能給使用者提供高效的使用者體驗。
參考文獻
【ｉ嚴蔚敏，ｌ】吳偉民，著．資料結構（ｃ語言版）【北京：清華大學出版社，１９９７－０４．
等，著．演算法導論【ｍ】．北京；機械工業出版社，
２００６－￣．
【３】高德納，著．計算機程式設計藝術町．北京：國防工業出版社，
２００２．
等，著．資料結構與演算法．北京：清華大學出
版社，２００３一ｌ２．１２９
表示式求值
課程設計報告 課程名稱資料結構 課題名稱表示式求值 專業電腦科學與技術 班級0901 學號 200903010102 姓名覃宇星 指導教師李珍輝鄧作傑郭芳 2011年7月7日 湖南工程學院 課程設計任務書 課程名稱 c語言程式設計 課題表示式求值 專業班級計算機0901 學生姓名 學號指導老師周鐵山...
實驗四算術表示式求值
源 include include include define plus 0 define minus 1 define power 2 define divide 3 define leftp 4 define righp 5 define startend 6 define digit 7 d...
算術表示式求值課設報告
資料結構課程設計 設計說明書 數學與電腦科學學院 2012年 9月 7日 資料結構課程設計評閱書 注 指導教師成績60 答辯成績40 總成績合成後按五級制記入 課程設計任務書 2011 2012學年第2學期 專業學號姓名 課程設計名稱資料結構課程設計 設計題目表示式求值演算法的實現 完成期限 自 2...