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

目錄(?)[+]

前言

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

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

一個(gè)良好的表達(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)然，實(shí)際的應(yīng)用里，表達(dá)式中要支持變量的綁定，比如：

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

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

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

表達(dá)式的定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）如果data是運(yùn)算符，就從堆棧stack中彈出此運(yùn)算符需要用到的表達(dá)式的個(gè)數(shù)(二元運(yùn)算符需要2個(gè))，創(chuàng)建一個(gè)新二元表達(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á)式對(duì)象樹(shù)如下：

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á)式對(duì)象樹(shù)，輸出結(jié)果。