問題由來
在我做過的一個針對網絡設備和主機的數據采集系統中某些采集到的數據需要經過一定的計算後才保存入庫而不是僅僅保存其原始值為了提供給用戶最大的靈活性我設想提供一個用戶界面允許用戶輸入計算表達式（或者稱為計算公式）這樣除了需要遵從少量的規則用戶可以得到最大的靈活性
這樣的表達式具有什麼特點呢？它一般不是純的可立即計算的表達式（簡單的如+*）它含有我稱為變量的元素變量一般具有特殊的內定的語法例如可能用@totalmemory表示設備或主機（下面簡稱為設備）的物理內存總數那麼表達式(@totalmemory@freememory)/@totalmemory*就表示設備當前內存使用率百分比如果與告警系統聯系起來監測此值超過系統就發出Warning那麼這就成為一件有意義的事情不同種類的采集數據入庫前可能需要經過復雜度不同的計算但顯然最後求值的時候必須將那些特定的變量用具體數值（即采集到的具體數值）替換否則表達式是不可計算的這個過程是在運行時發生的
問題的一般性
我認為表達式計算是個一般性的話題並且也不是一個新的話題我們可能在多處碰到它我在讀書的時候編寫過一個表達式的轉換和計算程序當時作為課余作業我看到過一些報表系統不管它是單獨的還是包含在MIS系統財務軟件中很多都支持計算公式我認為這些系統中的計算公式和我所遇到的問題是大致相同的對我來說我在數據采集項目中遇到這個問題下次可能還會在其他項目中遇到它既然已經不止一次了我希望找到一個一般性的解決方案
一些已有的設計和實現不能滿足要求
在設計和實現出第一個版本之後我自己感覺不很滿意隨後我花點時間上網搜索了一下（關鍵字表達式 中綴 後綴 or Expression Infix Postfix）令人稍感失望的是所找到的一些關於表達式的轉換計算的程序不能滿足我的要求不少這樣的程序僅僅支持純的可立即計算的表達式不支持變量而且表達式解析和計算是耦合在一起的很難擴展增加新的運算符（或新的變量語法）幾乎必定要修改源代碼在我看來這是最大的缺陷了（實際上當年我編寫的表達式轉換和計算的程序雖然當時引以自豪但是現在看來也具有同樣的缺陷）但是表達式的轉換和計算本身有成熟的基於棧的的經典算法許多計算機書籍或教材上都有論述人們以自然方式書寫的表達式是中綴形式的先要把中綴表達式轉換為後綴表達式然後計算後綴表達式的值我打算仍然采用這個經典的過程和算法
我的設計想法和目標
既然表達式的轉換和計算的核心算法是成熟的我渴望把它們提取出來去除（與解析相關的）耦合性！試想如果事物具有相對完整的內涵和獨立性會產生這個需要並且也能夠通過形式上的分離和提取來把內涵給表現出來這個過程離不開抽象我不久意識到自己實際上在設計一個小規模的關於表達式計算的框架
表達式要支持加減乘除運算符這是基本的立即想到的或許還應該支持平方開方（sqrt）三角運算符如sincos等那麼如果還有其它怎麼辦包括自定義的運算符？你能確定考慮完備了嗎？像自定義的運算符是完全存在的合理的需求在數據采集系統中我一度考慮引入一個diff運算符表明同一個累加型的采集量在相距最近的兩次（即采集周期）采集的差值以上的思考促使我決定運算符的設計必須是開放的用戶（這裡指的是用戶程序員下同）可以擴展增加新的運算符
表達式中允許含有變量對於變量的支持貫穿到表達式解析轉換計算的全過程在解析階段應該允許用戶使用適合他/她自己的變量語法我不應該事先實現基於某種特定語法的變量識別
由於支持可擴展的運算符未知的變量語法甚至連基本的數值（象E）理論上也有多種類型和精度（Integer/Long/Float/Double/BigInteger/BigDecimal）這決定了無法提供一個固化的表達式解析方法表達式解析也是需要可擴展的最好的結果是提供一個容易使用和擴展的解析框架對於新的運算符新的變量語法用戶在這個框架上擴展以提供增強的解析能力從抽象的角度來看我打算支持的表達式僅由四種元素組成括號（包括左右括號）運算符數值和變量一個最終用戶給出的表達式字符串解析通過後可能生成了一個內部表示的便於後續處理的表達式組成這個表達式的每個元素只能是以上四種之一
數值
一開始我寫了一個表達數值的類叫做Numeral我為Numeral具體代表的是整數浮點數還是雙精度數而操心從比較模糊的意義上我希望它能表達以上任何一種類型和精度的數值但是我也希望它能夠明確表達出代表的具體是哪種類型和精度的數值如果需要的話甚至我想到Numeral最好也能表達BigInteger和BigDecimal（設想恰巧在某種場合下我們需要解析和計算一個這樣的表達式它允許的數值的精度和范圍很大以至於Long或Double容納不下）否則在特別的場合下我們將遇到麻煩在可擴展性上數值類不大像運算符類它應該是成熟的因而幾乎是不需要擴展的
經過反復嘗試的混亂（Numeral後來又經過修改甚至重寫）我找到了一個明智的辦法直接用javalangNumber作為數值類（實際上這是一個接口）我慶幸地看到在Java中IntegerLongFloatDouble甚至BigIntegerBigDecimal等數值類都實現了javalangNumber（下面簡稱Number）接口使用者把Number作為何種類型和精度來看待和使用權利掌握在他/她的手中我不應該提前確定數值的類型和精度選擇由Number類來表達數值這看來是最好的代價最小的選擇了並且保持了相當的靈活性作為一個順帶的結果Numeral類被廢棄了
括號
在表達式中括號扮演的角色是不可忽視的它能改變運算的自然優先級按照用戶所希望的順序進行計算我用Bracket類來表示括號這個類可以看作是final因為它不需要擴展括號分作括號和右括號我把它們作為Bracket類的兩個靜態實例變量（並且是Bracket類僅有的兩個實例變量）
public class Bracket
{
private String name;
private Bracket(String name) {
thisname = name;
}
public static final Bracket
LEFT_BRACKET = new Bracket(()
RIGHT_BRACKET = new Bracket());
public String toString() {
return name;
}
}
運算符
運算符的設計要求是開放的這幾乎立即意味著它必須是抽象的我一度猶豫運算符是作為接口還是抽象類定義最後我選擇的是抽象類
public abstract class Operator
{
private String name;
protected Operator(String name) {
thisname = name;
}
public abstract int getDimension();
public abstract Number eval(Number[] oprands int offset);
// throws ArithmeticException ?
public Number eval(Number[] oprands) {
return eval(oprands);
}
public String toString() {
return name;
}
}
這個運算符的設計包含二個主接口方法通過getDimention()接口它傳達這麼一個信息運算符是幾元的？即需要幾個操作數顯然最常見的是一元和二元運算符這個接口方法似乎也意味著允許有多於二元的運算符但是對於多於二元的運算符我沒有作更深入的考察我不能十分確定基於棧的表達式的轉換和計算算法是否完全支持二元以上的運算符盡管有這麼一點擔憂我還是保留目前的接口方法
運算符最主要的接口方法就是eval()這是運算符的計算接口反映了運算符的本質在這個接口方法中要把所有需要的操作數傳給它運算符是幾元的就需要幾個操作數這應該是一致的然後執行符合運算符含義的計算返回結果如果增加新的運算符用戶需要實現運算符的上述接口方法
變量
從某種意義上說變量就是待定的數值我是否應該設計一個Variable類（或接口）？我的確這樣做了變量什麼時候被什麼具體數值替代這些過程我不知道應該留給用戶來處理我對於變量的知識幾乎是零因此Variable類的意義就不大了如果繼續保留這個類/接口還給用戶帶來一個限制他/她必須繼承或實現Varibale類/接口因此不久之後我丟棄了Variable我只是聲明和堅持這麼一點在一個表達式中如果一個元素不是括號不是數值也不是運算符那麼我就把它作為變量看待
表達式解析接口
表達式解析所要解決的基本問題是對於用戶給出的表達式字符串要識別出其中的數值運算符括號和變量然後轉換成為內部的便於後續處理的表達式形式我提供了一個一般的表達式解析接口如下
public interface Parser
{
Object[] parse(String expr) throws IllegalExpressionException;
}
在這個解析接口中我只定義了一個方法parse()表達式串作為輸入參數方法返回一個數組Object[]作為解析結果如果解析通過的話可以肯定數組中的元素或者是Number或者Operator或者Bracket如果它不是以上三種之一就把它視為變量
也許這樣把表達式解析設計的過於一般了因為它回避了如何解析這個關鍵的問題而顯得對於用戶幫助不大表達式究竟如何解析在我看來是一個復雜的甚至困難的問題
主要困難在於無法提供一個現成的適用於各種表達式的解析實現請考慮用戶可能會增加新的運算符引入新的變量語法甚至支持不同類型和精度的數值處理如前面所提到的如果能設計出一個表達式解析框架就好了讓用戶能夠方便地在這個框架基礎上擴展但是我沒能完全做到這一點後面將提到已經實現的一個缺省的解析器（SimpleParser）這個缺省實現試圖建立這樣一個框架我覺得可能有一定的局限性
中綴表達式到後綴的轉換
這是通過一個轉換器類Converter來完成的我能夠把轉換算法（以及下面的計算算法）獨立出來讓它不依賴於運算符或變量的擴展這得益於先前所做的基礎工作對於表達式元素（數值括號運算符和變量）的分析和抽象算法的基本過程是這樣的（讀者可以從網上或相關書籍中查到我略作改動因為支持變量的緣故）創建一個工作棧和一個輸出隊列從左到右讀取表達式當讀到數值或變量時直接送至輸出隊列當讀到運算符t時將棧中所有優先級高於或等於t的運算符彈出送到輸出隊列中然後t進棧讀到左括號時總是將它壓入棧中讀到右括號時將靠近棧頂的第一個左括號上面的運算符全部依次彈出送至輸出隊列後再丟棄左括號在Converter類中核心方法convert()執行了上述的算法其輸入是中綴表達式輸出是後綴表達式完成了轉換的過程
public abstract class Converter
{
public abstract int precedenceCompare(Operator op Operator op)
throws UnknownOperatorException;
public Object[] convert(Object[] infixExpr)
throws IllegalExpressionException UnknownOperatorException
{
return convert(infixExpr infixExprlength);
}
public Object[] convert(Object[] infixExpr int offset int len)
throws IllegalExpressionException UnknownOperatorException
{
if (infixExprlength offset < len)
throw new IllegalArgumentException();
// 創建一個輸出表達式用來存放結果
ArrayList output = new ArrayList();
// 創建一個工作棧
Stack stack = new Stack();
int currInputPosition = offset; // 當前位置（於輸入隊列）
Systemoutprintln( Begin conversion procedure );//TEMP!
while (currInputPosition < offset + len)
{
Object currInputElement = infixExpr[currInputPosition++];
if (currInputElement instanceof Number) // 數值元素直接輸出
{
outputadd(currInputElement);
Systemoutprintln(NUMBER:+currInputElement);//TEMP!
} else if (currInputElement instanceof Bracket) // 遇到括號進棧或進行匹配
{
Bracket currInputBracket = (Bracket)currInputElement;
if (currInputBracketequals(BracketLEFT_BRACKET)) { // 左括號進棧
stackpush(currInputElement);
} else { // 右括號尋求匹配（左括號）
// 彈出所有的棧元素(運算符)直到遇到(左)括號
Object stackElement;
do
{
if (!stackempty())
stackElement = stackpop();
else
throw new IllegalExpressionException(bracket(s) mismatch);
if (stackElement instanceof Bracket)
break;
outputadd(stackElement);
Systemoutprintln(OPERATOR POPUP:+stackElement);//TEMP!
} while (true);
}
} else if (currInputElement instanceof Operator)
{
Operator currInputOperator = (Operator)currInputElement;
// 彈出所有優先級別高於或等於當前的所有運算符
// (直到把滿足條件的全部彈出或者遇到左括號)
while (!stackempty()) {
Object stackElement = stackpeek();
if (stackElement instanceof Bracket) {
break;// 這一定是左括號沒有可以彈出的了
} else {
Operator stackOperator = (Operator)stackElement;
if (precedenceCompare(stackOperator currInputOperator) >= ) {
// 優先級高於等於當前的彈出（至輸出隊列）
stackpop();
outputadd(stackElement);
Systemoutprintln(OPERATOR:+stackElement);//TEMP!
} else { // 優先級別低於當前的沒有可以彈出的了
break;
}
}
}
// 當前運算符進棧
stackpush(currInputElement);
} else //if (currInputElement instanceof Variable)
// 其它一律被認為變量變量也直接輸出
{
outputadd(currInputElement);
Systemoutprintln(VARIABLE:+currInputElement);//TEMP!
}
}
// 將棧中剩下的元素(運算符)彈出至輸出隊列
while (!stackempty())
{
Object stackElement = stackpop();
outputadd(stackElement);
Systemoutprintln(LEFT STACK OPERATOR:+stackElement);//TEMP!
}
Systemoutprintln( End conversion procedure );//TEMP!
return outputtoArray();
}
}
讀者可能很快注意到Converter類不是一個具體類既然算法是成熟穩定的並且我們也把它獨立出來了為什麼Converter類不是一個穩定的具體類呢？因為在轉換過程中我發覺必須要面對一個運算符優先級的問題這是一個不可忽視的問題按照慣例如果沒有使用括號顯式地確定計算的先後順序那麼計算的先後順序是通過比較運算符的優先級來確定的因為我無法確定用戶在具體使用時他/她的運算符的集合有多大其中任意兩個運算符之間的優先級順序是怎樣的這個知識只能由用戶來告訴我說錯了告訴給Converter類所以Converter類中提供了一個抽象的運算符比較接口precedenceCompare()由用戶來實現
在一段時間內我為如何檢驗表達式的有效性而困惑我意識到轉換通過了並不一定意味著表達式是必定合乎語法的有效的甚至接下來成功計算出後綴表達式的值也並不能證明原始表達式是有效的當然在某些轉換失敗或者計算失敗的情況下例如運算符的元數與操作數數量不匹配左右括號不匹配等則可以肯定原始表達式是無效的但是證明一個表達式是有效的條件要苛刻的多遺憾的是我沒能找到檢驗表達式有效性的理論根據
計算後綴表達式
這是通過一個計算器類Calculator來完成的Calculator類的核心方法是eval()傳給它的參數必須是後綴表達式在調用本方法之前如果表達式中含有變量那麼應該被相應的數值替換掉否則表達式是不可計算的將導致拋出IncalculableExpressionException異常算法的基本過程是這樣的創建一個工作棧從左到右讀取表達式讀到數值就壓入棧中讀到運算符就從棧中彈出N個數計算出結果再壓入棧中N是該運算符的元數重復上述過程最後輸出棧頂的數值作為計算結果結束
public class Calculator
{
public Number eval(Object[] postfixExpr) throws IncalculableExpressionException
{
return eval(postfixExpr postfixExprlength);
}
public Number eval(Object[] postfixExpr int offset int len)
throws IncalculableExpressionException
{
if (postfixExprlength offset < len)
throw new IllegalArgumentException();
Stack stack = new Stack();
int currPosition = offset;
while (currPosition < offset + len)
{
Object element = postfixExpr[currPosition++];
if (element instanceof Number) {
stackpush(element);
} else if (element instanceof Operator)
{
Operator op = (Operator)element;
int dimensions = opgetDimension();
if (dimensions < || stacksize() < dimensions)
throw new IncalculableExpressionException(
lack operand(s) for operator +op+);
Number[] operands = new Number [dimensions];
for (int j = dimensions ; j >= ; j)
{
operands[j] = (Number)stackpop();
}
stackpush(opeval(operands));
} else
throw new IncalculableExpressionException(Unknown element: +element);
}
if (stacksize() != )
throw new IncalculableExpressionException(redundant operand(s));
return (Number)stackpop();
}
}
缺省實現
前面我主要討論了關於表達式計算的設計一個好的設計和實現中常常包括某些缺省的實現在本案例中我提供了基本的四則運算符的實現和一個缺省的解析器實現（SimpleParser）
運算符
實現了加減乘除四種基本運算符
需要說明一點的是對於每種基本運算符當前缺省實現只支持Number是IntegerLongFloatDouble的情況並且需要關注一下不同類型和精度的數值相運算時結果數值的類型和精度如何確定缺省實現對此有一定的處理
解析器
這個缺省的解析器實現我認為它是簡單的故取名為SimpleParser其基本思想是把表達式看作是由括號數值運算符和變量組成每種表達式元素都可以相對獨立地進行解析為此提供一種表達式元素解析器（ElementParser）SimpleParser分別調用四種元素解析器完成所有的解析工作
ElementParser提供了表達式元素級的解析接口四種缺省的表達式元素解析器類BasicNumberParser BasicOperatorParser DefaultBracketParserDefaultVariableParser均實現這個接口
public interface ElementParser
{
Object[] parse(char[] expr int off);
}
解析方法parse()輸入參數指明待解析的串以及起始偏移返回結果中存放本次解析所得到的具體元素（NumberOperatorBracket或者Object）以及解析的截止偏移本次的截至偏移很可能就是下次解析的起始偏移如果不考慮空白符的話
那麼在整個解析過程中每種元素解析器何時被SimpleParser所調用？我的解決辦法是它依次調用每種元素解析器可以說這是一個嘗試的策略嘗試的先後次序是有講究的依次是變量解析器〉運算符解析器〉數值解析器〉括號解析器
為什麼執行這麼一種次序？從深層次上反映了我的一種憂慮這就是表達式的解析可能是相當復雜的可能有這樣的表達式對於它不能完全執行分而治之的解析方式因為存在需要整體解析的地方例如考慮diff(@TotalBytesReceived)這樣的一個子串用戶可能用它可能表達這樣的含義取采集量TotalBytesReceived的前後兩次采集的差值diff在這裡甚至不能理解成傳統意義上的運算符最終合理的選擇很可能是把diff(@TotalBytesReceived)整個視為一個變量來解析和處理在這樣的情況下拆開成diff(@bytereceived)分別來解析是無意義的錯誤的
這就是為什麼變量解析器被最先調用這樣做允許用戶能夠截獲重新定義超越常規的解析方式以滿足實際需要實際上我安排讓變化可能性最大的部分（如變量）其解析器被最先調用最小的部分（如括號）其解析器被最後調用在每一步上如果解析成功那麼後續的解析器就不會被調用如果在表達式串的某個位置上經過所有的元素解析器都不能解析那麼該表達式就是不可解析的將拋出IllegalExpressionException異常
擴展實現
由於篇幅的關系不在此通過例子討論擴展實現這並不意味著目前沒有一個擴展實現在前面提到的數據采集項目中由於基本初衷就是支持特別語法的變量結果我實現了一個支持變量的擴展實現並且支持了一些其他運算符除四則運算符之外相信讀者能夠看出我所做的工作體現和滿足了可擴展性而擴展性主要體現在運算符和變量上
總結
對於表達式計算我提出的要求有一定挑戰性但也並不是太高然而為了接近或達到這個目標在設計上我頗費了一番功夫數易其稿前面提到我丟棄了Numeral類Variable類實際上還不止這些我還曾經設計了Element類表達式在內部就表示成一個數組Element[]在Element類中通過一個枚舉變量指明它包含的到底是什麼類型的元素（數值括號運算符還是變量）但是我嗅出這個做法不夠清晰自然（如果追根究底可以說不夠面向對象化）而最後丟棄了這個類相應地Element[]被更直接的Object[]所代替
我的不斷改進的動力就是力求讓設計在追求其它目標的同時保持簡潔注意這並不等於追求過於簡單！我希望我的努力讓我基本達到了這個目標我除去了主要的耦合性讓相對不變的部分表達式轉換和計算部分獨立出來並把變化的部分運算符和變量開放出來雖然在表達式解析上我還留有遺憾表達式的一般解析接口過於寬泛了未能為用戶的擴展帶來實質性的幫助所幸缺省解析器的實現多少有所彌補
最後我希望這個關於表達式計算的設計和實現能夠為他人所用和擴展我願意看到它能經受住考驗
作者簡介
劉源男軟件工程師您可以通過和作者取得聯系
From:http://tw.wingwit.com/Article/program/Java/hx/201311/26721.html
