摘  要： 運用逆波蘭記號和堆棧技術，基于ANSIC/C++開發(fā)環(huán)境，設計了計費預處理的話單過濾系統(tǒng)，給出了過濾表達式的形式定義、物理存儲形式和語義定義以及表達式形式定義和物理存儲的轉換算法。

　　網計費賬系統(tǒng)是電信重要系統(tǒng)之一，系統(tǒng)設計運行準確性和操作簡單方便至極關心運營商的利益，為計費準確性在設計系統(tǒng)是必須要多加幾個環(huán)節(jié)來保障系統(tǒng)安全無誤。

　　計費的原始數據要經歷話單采集、分撿、預處理、劃價、入庫、合賬等系列過程，最終形成客戶繳費賬單。其中，預處理環(huán)節(jié)是對話單準確性進行校驗最重要的步驟。該環(huán)節(jié)的主要功能是對各種錯誤識別并進行異常處理，同時生成標準化帳單數據作為計費的依據。因此設計一個高效、靈活的話單過濾算法是計費預處理系統(tǒng)的一項重要工作。

　　1  功能需求分析

　　算法的實現必須要考慮到特定業(yè)務需求的邏輯性和相關性。電信計費話單過濾的功能需求有以下幾個方面：（1）可以分別根據通話記錄各信息要素以及其組合實現過濾。如主叫和被叫電話以及主被叫電話組合的號碼段，通話開始、結束時間及通話時長，出中繼和入中繼號碼等；（2）可以根據通話記錄信息要素的業(yè)務邏輯和相關性實現過濾。（3）可以通過圖形界面向導配置話單過濾條件。

　　2  現行方法的弊端

　　目前，話單過濾功能的實現主要采用以下幾種方式：

　　（1）將話單文件導入數據庫系統(tǒng)中進行手工SQL命令過濾。該方法人工干預較多，難以避免人為錯誤。該方法難以應用。（2）根據需要手工修改應用程序。該方法直接在程序中修改過濾判斷條件，程序工作量大、改動頻繁，而且不能表述話單的業(yè)務邏輯關系。（3）根據簡單表格形成過濾條件。該方法避免了手工出錯的可能性，但表格中表達式之間僅存在簡單的“與”“或”的關系，條件優(yōu)先級無法實現，因而也不能完全表述復雜的邏輯關系。

　　3  基于逆波蘭記號的過濾算法設計

　　3.1 過濾條件的形式定義

　　過濾條件是一個記號系統(tǒng)，其定義應當符合程序設計語言的需要，包括一組完整的文法規(guī)則?，F將話單過濾條件定義為文法G={Vn，Vt，P，S}，Vn為非終結符號集；Vt為終結符號集；P為產生式（規(guī)則）集；S為識別符號或開始符號。

　　過濾算法成為非線性規(guī)劃領域研究的熱點。過濾算法的特點是不需要罰因子和效益函數，它利用一種稱之為“濾子”的集合來協(xié)調可行性和最優(yōu)性，從而保證全局收斂性。過濾算法是一種迭代算法。該算法將非線性優(yōu)化問題轉化為一個雙目標優(yōu)化問題，即分別最小化可行性違法度和目標函數值。其中又偏重于改善可行性。在每一個迭代點都通過某種方法（信賴域，SQP等）獲得一個嘗試步，若該嘗試步至少能改善可行性和最優(yōu)性兩者之一，則判定該嘗試步能被濾子接受，接下來再考察其充分下降性。

　　3.2 過濾條件的物理存儲表示

　　物理存儲器是指實際存在的具體的存儲器芯片。如主板上裝插的內存條和裝載有系統(tǒng)BIOS的ROM芯片，顯示卡上的顯示RAM芯片和裝載顯示BIOS的ROM芯片，以及各種適配卡上的RAM芯片和ROM芯片等都是物理存儲器。

　　話單過濾條件形式定義為一個中綴邏輯表達式，這種方式對最終用戶來說是個易于理解和符合閱讀或操作習慣的表達方式，但在算法處理中需要進行算符優(yōu)先級的判定工作。逆波蘭記號又叫后綴表示法，這種表示方法將運算對象寫在前面，把運算符寫在后面，只需要利用一個堆棧就可完全對輸入串進行解析。3.1節(jié)中的示例表達式用逆波蘭記號可表示為：A，字串，>，E，字串，≤，∩，M，字串，=，∪。通過采用逆波蘭記號，合理規(guī)避了算符優(yōu)先級別的判別功能，有利于程序設計的簡化。[!--empirenews.page--]

　　3.3 過濾條件語義的定義

　　語義定義是和功能需求緊密聯(lián)系的，并可以根據需求的變化進行調整和擴充。文法G中各終結符號語義見表1。

　　例如話單過濾表達式（（（A>4224000）∩（A≤6899123））∪（N=1）），其語義為主叫號碼段在4224000和6899123之間，或者主被叫歸屬相同計費區(qū)。

　　3.4 過濾條件形式定義和物理存儲的相互轉換

　　話單過濾條件的形式定義和物理表述分別采用中綴法和后綴法，前者直接面向最終用戶，后者是針對設計人員算法實現的需要，因此必須采用合理的機制進行相互轉換。這里需要解決兩個問題：一是要設計一個最終用戶可理解的圖形界面向導、采用中綴法來配置過濾表達式；二是設計一個依據中綴式形成后綴式的算法。在本文中作如下定義：

　　3.4.1 過濾表達式的用戶配置

　　這里預定義關系表T_EXPRESS，其結構見表2。該表用于存儲所有話單過濾條件的原子表達式和組合表達式?；谠摫恚O計相關的圖形配置界面向導是很容易達到用戶配置過濾表達式要求的。

　　3.3節(jié)中話單過濾表達式在表中存儲方式見表3，記錄序號5指示的組合表達式就是該過濾條件表達式的入口。

　　3.4.2 中綴式向后綴式轉換算法

　　實現中綴表達式向后綴表達式的轉換可采用遞歸算法，偽C語言代碼如下：

　　String GetSuffixExpress（int seq） {

　　Billing_Record_Express=GetBillingRecordExpress（seq）；

　　If Billing_Record_Express.ftype=原子表達式

　　Return Billing_Record_Express.felement + ″，″+

　　Billing_Record_Express.fvalue +″，″+ Billing_Record_Express.foperate；

　　Else //組合表達式

　　Return  GetSuffixExpress（int（Billing_Record_

　　Express.felement）） + ″，″+ GetSuffixExpress（int

　　（Billing_Record_Express.fvalue）） + ″，″+

　　Billing_Record_Express.foperate；

　　}[!--empirenews.page--]

　　3.5 話單過濾表達式運算算法的實現

　　話單過濾表達式最終將形成布爾值結果真或假，由此來判定該張話單是否被系統(tǒng)過濾。算法分為語法分析、業(yè)務邏輯處理兩個部分。語法分析是利用堆棧運算分解出原子表達式的過程；業(yè)務邏輯處理是針對原子表達式的語義作出相應的業(yè)務處理并求得該原子表達式的布爾值。以下是算法的偽C語言代碼：

　　STACK stack；

　　Bool result；

　　String suffixexpress；

　　Bool SyntaxAnlysis（suffixexpress）{

　　SETNULL（stack）；

　　Terminalsymb=GetNextTerminalsymb（suffixexpress）；

　　While （！IsNull（Terminalsymb）） {

　　Switch（Terminalsymb）{

　　Case A to N     PUSH（stack，Terminalsymbol）；

　　Case > to =

　　POP（stack，value）；

　　POP（stack，factor_code）；

　　Comparesymb=Terminalsymb；

　　Result=LogicProcess（factor_code,Com

　　paresymbol，value）；

　　PUSH（stack，result）

　　Case  ∪，∩

　　POP（stack，result1）；

　　POP（stack，result2）；

　　Logicalsymb=Terminalsymb；

　　Result=BoolProcess（result1，Logicalsymbol，result2）；

　　PUSH（stack，result）；

　　}

　　Terminalsymbol=GetNextTerminalsymbol（suffixexpress）；

　　}

　　return TOP（stack）；

　　}

　　在設計和開發(fā)湖南電信本地網計費系統(tǒng)過程中，運用逆波蘭記號和堆棧技術，基于ANSI C/C++開發(fā)環(huán)境成功完成了計費預處理的話單過濾系統(tǒng)。本算法稍加修改和擴充就可以應用到大部分涉及格式化文本和數據庫記錄過濾的應用中。