表達(dá)式解析引擎的設(shè)計

目錄(?)[+]

前言

表達(dá)式的計算是一個一般性的問題。在報表領(lǐng)域，經(jīng)常會出現(xiàn)支持計算公式的需求。MS Office Excel中的函數(shù)計算就是一個很好的參考例子。

本文提供一個表達(dá)式引擎的設(shè)計方案，能夠滿足報表領(lǐng)域的復(fù)雜計算要求。

一個良好的表達(dá)式引擎應(yīng)該支持基本的二元運(yùn)算和函數(shù)調(diào)用，而且二元運(yùn)算能夠嵌套函數(shù)調(diào)用，函數(shù)調(diào)用也能夠嵌套二元運(yùn)算，比如：

例子1：=2>1&&((Num(1)+2*Num((Num(2)+2)*3/Num(2)))/2>0||2>1)&&0>1，執(zhí)行結(jié)果：0

例子2：=Switch(Num(1),是, Num(0),否)，執(zhí)行結(jié)果：是

例子3：=Switch(20<10,1 ,20>=10, 20 + 20*0.1)，執(zhí)行結(jié)果：22

當(dāng)然，實際的應(yīng)用里，表達(dá)式中要支持變量的綁定，比如：

例子1(計算稅后金額)：=Fields!數(shù)量.Value * Fields!單價.Value*(1 + Fields!稅率.Value / 100)

例子2(不同價格不同稅后金額)：=Fields!數(shù)量.Value*Fields!單價.Value*Switch(Fields!單價.Value<100, 1.1, Fields!單價.Value<500, 1.08, Fields!單價.Value<800, 1.07)

至于常用的一元運(yùn)算，能夠通過函數(shù)調(diào)用就很方便的實現(xiàn)，例如：取非，Not(exp1)。

表達(dá)式的定義

要支持二元運(yùn)算能夠嵌套函數(shù)調(diào)用，函數(shù)調(diào)用也能夠嵌套二元運(yùn)算，需要采用解析器設(shè)計模式，定義數(shù)個表達(dá)式對象，用表達(dá)式對象樹來描述表達(dá)式字符串。

值表達(dá)式：用來描述一個常量或變量，例如：1.1，F(xiàn)ields!數(shù)量.Value，Parameters!經(jīng)手人.Value，字符串

二元表達(dá)式：用來描述一個二元運(yùn)算，例如：exp1 + exp2，exp1

函數(shù)表達(dá)式：用來描述一個函數(shù)調(diào)用，例如：Num(exp1)，Sum(exp1)， Switch(cond1, proc1, cond2, proc2…)

運(yùn)算符優(yōu)先級

運(yùn)算符優(yōu)先級很重要，決定了運(yùn)算的順序，特別是括號，能夠改變表達(dá)式的運(yùn)算順序。

表達(dá)式引擎的工作流程

二元運(yùn)算解析生成后綴表達(dá)式數(shù)組的過程

中綴表達(dá)式解析成后綴表達(dá)式的方法如下，要借用一個臨時堆棧stack，輸出是后綴表達(dá)式數(shù)組output：

（1）從右向左依次讀取表達(dá)式字符串str。

（2）如果str是操作數(shù)(常量或變量)，輸出到output。

（3）如果str是運(yùn)算符（含左右括號），則做以下判斷：

    a） 如果str = '('，放入堆棧stack。

    b）如果str = ')'，依次彈出堆棧stack中的運(yùn)算符輸出到output，直到遇到'('為止。

    c）如果str不是')'或者'('，那么就和堆棧stack頂點(diǎn)位置的運(yùn)算符top做優(yōu)先級比較。

      1）如果top是'('或者str優(yōu)先級比top高，那么將str放入堆棧stack。

      2）如果str優(yōu)先級低于或者等于top，那么輸出top到output，然后將str放入堆棧stack。

（4）如果表達(dá)式字符串已經(jīng)讀取完成，而堆棧stack中還有運(yùn)算符時，依次由頂端輸出到output。

后綴表達(dá)式數(shù)組生成表達(dá)式對象樹的過程

計算后綴表達(dá)式的方法如下，要借用一個臨時堆棧stack：

（1）從左向右掃描后綴表達(dá)式數(shù)組，依次取出一個數(shù)組元素data。

（2）如果data是表達(dá)式，就壓入堆棧stack。

（3）如果data是運(yùn)算符，就從堆棧stack中彈出此運(yùn)算符需要用到的表達(dá)式的個數(shù)(二元運(yùn)算符需要2個)，創(chuàng)建一個新二元表達(dá)式，然后把二元表達(dá)式壓入堆棧stack。

（4）如果數(shù)組處理完畢，堆棧stack中最后剩余的表達(dá)式就是最終結(jié)果。

例如，表達(dá)式=(Num(1)+2*Num(Num(2)+2*3/Num(2)))/2，生成的后綴表達(dá)式數(shù)組如下：

0:    Method{num, [Const(1)]}

1:    Const(2)

2:    Method{num, [Binary{+, Method{num, [Const(2)]}, Binary{/, Binary{*, Const(2), Const(3)}, Method{num, [Const(2)]}}}]}

3:    *

4:    +

5:    Const(2)

6:    /

該后綴表達(dá)式數(shù)組生成的表達(dá)式對象樹如下：

Binary{/, Binary{+, Method{num, [Const(1)]}, Binary{*, Const(2), Method{num, [Binary{+, Method{num, [Const(2)]}, Binary{/, Binary{*, Const(2), Const(3)}, Method{num, [Const(2)]}}}]}}}, Const(2)}

剩下的工作就是執(zhí)行表達(dá)式對象樹，輸出結(jié)果。