基于逆波兰记号电信计费话单过滤算法设计

很容易达到用户配置过滤表达式要求的。

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++开发环境成功完成了计费预处理的话单过滤系统。本算法稍加修改和扩充就可以应用到大部分涉及格式化文本和数据库记录过滤的应用中。