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

　　本地網(wǎng)計費賬務系統(tǒng)是電信最重要的業(yè)務支撐系統(tǒng)之一。該系統(tǒng)設計運行的準確性直接關(guān)系到電信運營商及廣大電信客戶的利益。為了保證話單的準確性，必須在計費系統(tǒng)的各個環(huán)節(jié)加以保障和分析處理。
　　計費的原始數(shù)據(jù)要經(jīng)歷話單采集、分撿、預處理、劃價、入庫、合賬等系列過程，最終形成客戶繳費賬單。其中，預處理環(huán)節(jié)是對話單準確性進行校驗最重要的步驟。該環(huán)節(jié)的主要功能是對各種錯誤識別并進行異常處理，同時生成標準化帳單數(shù)據(jù)作為計費的依據(jù)。交換機形成的計費原始數(shù)據(jù)往往由于多種原因，出現(xiàn)計費不準確現(xiàn)象。如電信部門出于安全考慮，在不同交換機上形成通話數(shù)據(jù)備份，使計費原始數(shù)據(jù)重復采集。該部分重復話單必須在計費系統(tǒng)中予以剔除，否則將直接影響到數(shù)據(jù)的準確性。因此設計一個高效、靈活的話單過濾算法是計費預處理系統(tǒng)的一項重要工作。
1  功能需求分析
　　算法的實現(xiàn)必須要考慮到特定業(yè)務需求的邏輯性和相關(guān)性。電信計費話單過濾的功能需求有以下幾個方面：(1)可以分別根據(jù)通話記錄各信息要素以及其組合實現(xiàn)過濾。如主叫和被叫電話以及主被叫電話組合的號碼段，通話開始、結(jié)束時間及通話時長，出中繼和入中繼號碼等；(2)可以根據(jù)通話記錄信息要素的業(yè)務邏輯和相關(guān)性實現(xiàn)過濾。如主叫和被叫電話計費區(qū)、主叫和被叫是否歸屬同一計費區(qū)，是否長途、區(qū)間話單，是否撥打特服號碼、移動電話號碼等。(3)可以通過圖形界面向?qū)渲迷拞芜^濾條件。
2  現(xiàn)行方法的弊端
　　目前，話單過濾功能的實現(xiàn)主要采用以下幾種方式：
　　(1)將話單文件導入數(shù)據(jù)庫系統(tǒng)中進行手工SQL命令過濾。該方法人工干預較多，難以避免人為錯誤。當單個計費文件容量過大時，文件和數(shù)據(jù)庫之間的導入導出會耗費過多的處理時間和資源。該方法難以應用。(2)根據(jù)需要手工修改應用程序。該方法直接在程序中修改過濾判斷條件，程序工作量大、改動頻繁，而且不能表述話單的業(yè)務邏輯關(guān)系。(3)根據(jù)簡單表格形成過濾條件。該方法避免了手工出錯的可能性，但表格中表達式之間僅存在簡單的“與”“或”的關(guān)系，條件優(yōu)先級無法實現(xiàn)，因而也不能完全表述復雜的邏輯關(guān)系。
3  基于逆波蘭記號的過濾算法設計
3.1 過濾條件的形式定義
　　過濾條件是一個記號系統(tǒng)，其定義應當符合程序設計語言的需要，包括一組完整的文法規(guī)則。現(xiàn)將話單過濾條件定義為文法G={Vn，Vt，P，S}，Vn為非終結(jié)符號集；Vt為終結(jié)符號集；P為產(chǎn)生式（規(guī)則）集；S為識別符號或開始符號。

3.2 過濾條件的物理存儲表示
　　話單過濾條件形式定義為一個中綴邏輯表達式，這種方式對最終用戶來說是個易于理解和符合閱讀或操作習慣的表達方式，但在算法處理中需要進行算符優(yōu)先級的判定工作。為了簡化處理，可采用逆波蘭記號方法對其進行轉(zhuǎn)換存儲。逆波蘭記號又叫后綴表示法，這種表示方法將運算對象寫在前面，把運算符寫在后面，只需要利用一個堆棧就可完全對輸入串進行解析。3.1節(jié)中的示例表達式用逆波蘭記號可表示為：A，字串，>，E，字串，≤，∩，M，字串，=，∪。通過采用逆波蘭記號，合理規(guī)避了算符優(yōu)先級別的判別功能，有利于程序設計的簡化。
3.3 過濾條件語義的定義
　　語義定義是和功能需求緊密聯(lián)系的，并可以根據(jù)需求的變化進行調(diào)整和擴充。文法G中各終結(jié)符號語義見表1。

　　例如話單過濾表達式(((A>4224000)∩(A≤6899123))∪（N=1）），其語義為主叫號碼段在4224000和6899123之間，或者主被叫歸屬相同計費區(qū)。
3.4 過濾條件形式定義和物理存儲的相互轉(zhuǎn)換
　　話單過濾條件的形式定義和物理表述分別采用中綴法和后綴法，前者直接面向最終用戶，后者是針對設計人員算法實現(xiàn)的需要，因此必須采用合理的機制進行相互轉(zhuǎn)換。這里需要解決兩個問題：一是要設計一個最終用戶可理解的圖形界面向?qū)?、采用中綴法來配置過濾表達式；二是設計一個依據(jù)中綴式形成后綴式的算法。在本文中作如下定義：
　　原子表達式：僅含一個二目比較算符和兩個運算對象的表達式；組合表達式：由若干個原子表達式通過二目邏輯連接符號連接的表達式。
3.4.1 過濾表達式的用戶配置
　　這里預定義關(guān)系表T_EXPRESS，其結(jié)構(gòu)見表2。該表用于存儲所有話單過濾條件的原子表達式和組合表達式。基于該表，設計相關(guān)的圖形配置界面向?qū)呛苋菀走_到用戶配置過濾表達式要求的。

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

3.4.2 中綴式向后綴式轉(zhuǎn)換算法
　　實現(xiàn)中綴表達式向后綴表達式的轉(zhuǎn)換可采用遞歸算法，偽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
　　　　　　　　?。˙illing_Record_Express.fvalue）） + ″，″+
　　　　　　　　　　　 Billing_Record_Express.foperate；
　　}
3.5 話單過濾表達式運算算法的實現(xiàn)
　　話單過濾表達式最終將形成布爾值結(jié)果真或假，由此來判定該張話單是否被系統(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ā)湖南電信本地網(wǎng)計費系統(tǒng)過程中，運用逆波蘭記號和堆棧技術(shù)，基于ANSI C/C++開發(fā)環(huán)境成功完成了計費預處理的話單過濾系統(tǒng)。本算法稍加修改和擴充就可以應用到大部分涉及格式化文本和數(shù)據(jù)庫記錄過濾的應用中。
參考文獻
1   陳火旺，錢家曄，孫永強.程序設計語言編譯原理.長沙：國防工業(yè)出版社，1983
2   嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).北京：清華大學出版社，1988
3   Valley J著，周立譯.Unix環(huán)境下的C語言程序設計.北京：學苑出版社，1994
4   Stevens W R.UNIX Network Programming Volume Ⅰ2nd ed影印版.北京：清華大學出版社，1998