表達式求值及符號推導

英昌盛

(吉林師范大學 計算機學院，吉林 四平 136000)

0 引言

表達式的分析、求值等運算是編譯程序中的一個關鍵部分。研究翻譯程序的工作原理和工作流程，對于教師的教學和研究，對于學生理論聯系實際都具有較為實用的意義和價值。

1 系統設計及概要設計

1.1 運算符和數據類型的支持

系統支持算術運算、關系運算和邏輯運算。算術運算符有包括:()、+、-、*、/、^(乘方)，其中^為新增運算符。邏輯運算符包括:!、＆(邏輯與為化簡運算符)、|(邏輯或為化簡運算符)。關系運算符包括:＞、＞=、==、_(負號)。

系統支持整數及浮點數。在進行算術運算、關系運算、邏輯運算時運算規則和結合性基本同C語言中相應的規則一致。

1.2 數據結構

用戶輸入的數據是隨機的，同時程序處理數據時用棧這種結構實現較好，所以系統采用兩個鏈棧［1］來保存運算量和運算符。因輸入的變量個數無法確定，系統采用動態生成鏈表［2］來存儲。

2 系統實現

2.1 算符優先級及數據結構

系統使用結構體數組charindex［］和OPTable［］保存運算符及其對應的優先級。charindex［］用來存放運算符和該運算符的棧外、內優先級在OPTable［］中的下標。charindex［］結構體數組的op域用來保存第i個運算符，index域用來存放第i個運算符在OPTable［］結構體數組相應元素中的下標，如表1［3］所示。

表1 運算符及其棧內、外優先級

OPTable［］的opri域和ipri域分別表示charindex［］數組中第i個運算符對應的棧外、棧內優先級。為方便運算和節省棧的域，OPTable［］的元素個數較charindex［］的元素個數多三項。系統只用一個整數表示一個運算符，而＞=，==，＜=等運算符都是兩個字符組成的字符串，不便于統一處理，經研究發現完全可以用＜、=、＞三個運算符的在OPTable［］中的下標值分別加1來表示＜=、==、＞=在OPTable［］中的下標值，因而＜、=、＞三者之間的索引值按2遞增。具體定義如下:

2.2 處理規則

(1)初始化時在運算棧內壓入一個#;同時#作為表達式結束標記。

(2)若棧外運算符的棧外優先級比棧頂運算符的棧內優先級高，則棧外運算符入棧;否則棧頂運算符退棧，并取出相應個數的運算量進行運算，把運算結果壓回運算量棧，直到棧外運算符的棧外優先級比棧頂運算符的棧內優先級高為止，將棧外運算符入棧;若棧外運算符的棧外優先級和棧頂運算符的棧內優先級相等，則棧頂運算符一定為’(’，此時為()的情況，作出錯處理。

(3)運算符退棧時，若遇到棧外運算符的棧外優先級和棧頂運算符的棧內優先級相等情況(此時一定是括號)，則彈出棧頂運算符，拋棄棧外運算符。

(4)若運算完畢運算量棧只剩一個運算量、符號棧空，則運算結果正確，其他情況則為錯誤。

(5)若 a＞0，則 -a=a*(-1)。

(6)程序中不支持在表達式中有賦值運算。即若遇到‘=’而其后的第一個字符不是‘=’則認為出錯。

2.3 核心實現

函數evaluate用于求解經過規范化的用戶輸入表達式，有四個參數:s為經過規范化后的用戶輸入表達式;s1為運算量棧指針;s2為運算符棧指針;s3為變量鏈表指針。程序中首先定義了一些臨時變量，然后在運算符棧內壓入#的索引及其棧外、棧內優先級作為標記如下:

s2=pushstack(s2，0，1，1);/*#的索引、棧內外級入棧*/

在表達式未結束且已掃描過的部分表達式合法的情況下循環處理。若是數字或小數點則進入數值處理分支并繼續讀取，并將運算量壓入運算量棧中。若讀到的是字母，則進入變量分支，并在變量表中進行查找變量值并壓入運算量棧之中。

對于運算符首先查找運算符表，然后在OPTable［］表中找到其對應的棧內、外優先級，并對棧外運算符的棧外優先級和棧頂運算符的棧內優先級作相應的比較，根據比較結果進行相應的運算。

［1］嚴蔚敏.數據結構［M］.北京:清華大學出版社出版，2009.

［2］譚浩強.C語言程序設計教程［M］.4版.北京:清華大學出版社出版，2010.

［3］唐策善.數據結構—用C語言描述.［M］.北京:高等教育出版社，2003.