摘  要： 运用逆波兰记号和堆栈技术，基于ANSIC/C++开发环境，设计了计费预处理的话单过滤系统，给出了过滤表达式的形式定义、物理存储形式和语义定义以及表达式形式定义和物理存储的转换算法。
关键词： 电信计费  预处理  过滤  堆栈  逆波兰记号

　　本地网计费账务系统是电信最重要的业务支撑系统之一。该系统设计运行的准确性直接关系到电信运营商及广大电信客户的利益。为了保证话单的准确性，必须在计费系统的各个环节加以保障和分析处理。
　　计费的原始数据要经历话单采集、分捡、预处理、划价、入库、合账等系列过程，最终形成客户缴费账单。其中，预处理环节是对话单准确性进行校验最重要的步骤。该环节的主要功能是对各种错误识别并进行异常处理，同时生成标准化帐单数据作为计费的依据。交换机形成的计费原始数据往往由于多种原因，出现计费不准确现象。如电信部门出于安全考虑，在不同交换机上形成通话数据备份，使计费原始数据重复采集。该部分重复话单必须在计费系统中予以剔除，否则将直接影响到数据的准确性。因此设计一个高效、灵活的话单过滤算法是计费预处理系统的一项重要工作。
1  功能需求分析
　　算法的实现必须要考虑到特定业务需求的逻辑性和相关性。电信计费话单过滤的功能需求有以下几个方面：(1)可以分别根据通话记录各信息要素以及其组合实现过滤。如主叫和被叫电话以及主被叫电话组合的号码段，通话开始、结束时间及通话时长，出中继和入中继号码等；(2)可以根据通话记录信息要素的业务逻辑和相关性实现过滤。如主叫和被叫电话计费区、主叫和被叫是否归属同一计费区，是否长途、区间话单，是否拨打特服号码、移动电话号码等。(3)可以通过图形界面向导配置话单过滤条件。
2  现行方法的弊端
　　目前，话单过滤功能的实现主要采用以下几种方式：
　　(1)将话单文件导入数据库系统中进行手工SQL命令过滤。该方法人工干预较多，难以避免人为错误。当单个计费文件容量过大时，文件和数据库之间的导入导出会耗费过多的处理时间和资源。该方法难以应用。(2)根据需要手工修改应用程序。该方法直接在程序中修改过滤判断条件，程序工作量大、改动频繁，而且不能表述话单的业务逻辑关系。(3)根据简单表格形成过滤条件。该方法避免了手工出错的可能性，但表格中表达式之间仅存在简单的“与”“或”的关系，条件优先级无法实现，因而也不能完全表述复杂的逻辑关系。
3  基于逆波兰记号的过滤算法设计
3.1 过滤条件的形式定义
　　过滤条件是一个记号系统，其定义应当符合程序设计语言的需要，包括一组完整的文法规则。现将话单过滤条件定义为文法G={Vn，Vt，P，S}，Vn为非终结符号集；Vt为终结符号集；P为产生式（规则）集；S为识别符号或开始符号。

3.2 过滤条件的物理存储表示
　　话单过滤条件形式定义为一个中缀逻辑表达式，这种方式对最终用户来说是个易于理解和符合阅读或操作习惯的表达方式，但在算法处理中需要进行算符优先级的判定工作。为了简化处理，可采用逆波兰记号方法对其进行转换存储。逆波兰记号又叫后缀表示法，这种表示方法将运算对象写在前面，把运算符写在后面，只需要利用一个堆栈就可完全对输入串进行解析。3.1节中的示例表达式用逆波兰记号可表示为：A，字串，>，E，字串，≤，∩，M，字串，=，∪。通过采用逆波兰记号，合理规避了算符优先级别的判别功能，有利于程序设计的简化。
3.3 过滤条件语义的定义
　　语义定义是和功能需求紧密联系的，并可以根据需求的变化进行调整和扩充。文法G中各终结符号语义见表1。

　　例如话单过滤表达式(((A>4224000)∩(A≤6899123))∪（N=1）），其语义为主叫号码段在4224000和6899123之间，或者主被叫归属相同计费区。
3.4 过滤条件形式定义和物理存储的相互转换
　　话单过滤条件的形式定义和物理表述分别采用中缀法和后缀法，前者直接面向最终用户，后者是针对设计人员算法实现的需要，因此必须采用合理的机制进行相互转换。这里需要解决两个问题：一是要设计一个最终用户可理解的图形界面向导、采用中缀法来配置过滤表达式；二是设计一个依据中缀式形成后缀式的算法。在本文中作如下定义：
　　原子表达式：仅含一个二目比较算符和两个运算对象的表达式；组合表达式：由若干个原子表达式通过二目逻辑连接符号连接的表达式。
3.4.1 过滤表达式的用户配置
　　这里预定义关系表T_EXPRESS，其结构见表2。该表用于存储所有话单过滤条件的原子表达式和组合表达式。基于该表，设计相关的图形配置界面向导是很容易达到用户配置过滤表达式要求的。

　　3.3节中话单过滤表达式在表中存储方式见表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；
　　}
3.5 话单过滤表达式运算算法的实现
　　话单过滤表达式最终将形成布尔值结果真或假，由此来判定该张话单是否被系统过滤。算法分为语法分析、业务逻辑处理两个部分。语法分析是利用堆栈运算分解出原子表达式的过程；业务逻辑处理是针对原子表达式的语义作出相应的业务处理并求得该原子表达式的布尔值。以下是算法的伪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)；
　　}
　　在设计和开发湖南电信本地网计费系统过程中，运用逆波兰记号和堆栈技术，基于ANSI C/C++开发环境成功完成了计费预处理的话单过滤系统。本算法稍加修改和扩充就可以应用到大部分涉及格式化文本和数据库记录过滤的应用中。
参考文献
1   陈火旺，钱家晔，孙永强.程序设计语言编译原理.长沙：国防工业出版社，1983
2   严蔚敏，吴伟民.数据结构.北京：清华大学出版社，1988
3   Valley J著，周立译.Unix环境下的C语言程序设计.北京：学苑出版社，1994
4   Stevens W R.UNIX Network Programming Volume Ⅰ2nd ed影印版.北京：清华大学出版社，1998