問題由來

在我做過的一個針對網絡設備和主機的數據采集系統中，某些采集到的數據需要經過一定的計算后才保存入庫，而不是僅僅保存其原始值。為了提供給 用戶最大的靈活性，我設想提供一個用戶界面，允許用戶輸入計算表達式（或者稱為計算公式）。這樣，除了需要遵從少量的規則，用戶可以得到最大的靈活性。

這樣的表達式具有什么特點呢？它一般不是純的可立即計算的表達式（簡單的如：1+2*3-4）。它含有我稱為變量的元素。變量一般具有特殊的 內定的語法，例如可能用"@totalmemory"表示設備或主機（下面簡稱為設備）的物理內存總數，那么表達式"(@totalmemory- @freememory)/@totalmemory*100"就表示設備當前內存使用率百分比。如果與告警系統聯系起來，監測此值超過 80 系統就發出 Warning，那么這就成為一件有意義的事情。不同種類的采集數據入庫前可能需要經過復雜度不同的計算。但顯然，最后求值的時候，必須將那些特定的變量 用具體數值（即采集到的具體數值）替換，否則表達式是不可計算的。這個過程是在運行時發生的。

回頁首

問題的一般性

我認為表達式計算是個一般性的話題，并且也不是一個新的話題。我們可能在多處碰到它。我在讀書的時候編寫過一個表達式的轉換和計算程序，當時 作為課余作業。我看到過一些報表系統，不管它是單獨的，還是包含在 MIS 系統、財務軟件中，很多都支持計算公式。我認為這些系統中的計算公式和我所遇到的問題是大致相同的。對我來說，我在數據采集項目中遇到這個問題，下次可能 還會在其他項目中遇到它。既然已經不止一次了，我希望找到一個一般性的解決方案。

回頁首

一些已有的設計和實現不能滿足要求

在設計和實現出第一個版本之后，我自己感覺不很滿意。隨后我花點時間上網搜索了一下（關鍵字：表達式 中綴 后綴 or Expression Infix Postfix）。令人稍感失望的是，所找到的一些關于表達式的轉換、計算的程序不能滿足我的要求。不少這樣的程序僅僅支持純的可立即計算的表達式，不支 持變量。而且，表達式解析和計算是耦合在一起的，很難擴展。增加新的運算符（或新的變量語法）幾乎必定要修改源代碼。在我看來，這是最大的缺陷了（實際 上，當年我編寫的表達式轉換和計算的程序，雖然當時引以自豪，但是現在看來也具有同樣的缺陷）。但是，表達式的轉換和計算本身有成熟的、基于棧的的經典算 法，許多計算機書籍或教材上都有論述。人們以自然方式書寫的表達式是中綴形式的，先要把中綴表達式轉換為后綴表達式，然后計算后綴表達式的值。我打算仍然 采用這個經典的過程和算法。

回頁首

我的設計想法和目標

既然表達式的轉換和計算的核心算法是成熟的，我渴望把它們提取出來，去除（與解析相關的）耦合性！試想，如果事物具有相對完整的內涵和獨立 性，會產生這個需要，并且也能夠通過形式上的分離和提取來把內涵給表現出來，這個過程離不開抽象。我不久意識到自己實際上在設計一個小規模的關于表達式計 算的框架。

表達式要支持加減乘除運算符，這是基本的、立即想到的。或許還應該支持平方，開方（sqrt），三角運算符如 sin，cos 等。那么如果還有其它怎么辦，包括自定義的運算符？你能確定考慮完備了嗎？像自定義的運算符，是完全存在的、合理的需求。在數據采集系統中，我一度考慮引 入一個 diff 運算符，表明同一個累加型的采集量，在相距最近的兩次（即采集周期）采集的差值。以上的思考促使我決定，運算符的設計必須是開放的。用戶（這里指的是用戶 程序員，下同）可以擴展，增加新的運算符。

表達式中允許含有變量。對于變量的支持貫穿到表達式解析，轉換，計算的全過程。在解析階段，應該允許用戶使用適合他 / 她自己的變量語法，我不應該事先實現基于某種特定語法的變量識別。

由于支持可擴展的運算符，未知的變量語法，甚至連基本的數值（象 123，12.3456，1.21E17）理論上也有多種類型和精度（Integer/Long/Float/Double/BigInteger /BigDecimal），這決定了無法提供一個固化的表達式解析方法。表達式解析也是需要可擴展的。最好的結果是提供一個容易使用和擴展的解析框架。對 于新的運算符，新的變量語法，用戶在這個框架上擴展，以提供增強的解析能力。

從抽象的角度來看，我打算支持的表達式僅由四種元素組成：括號（包括左右括號），運算符，數值和變量。一個最終用戶給出的表達式字符串，解析通過后，可能生成了一個內部表示的、便于后續處理的表達式，組成這個表達式的每個元素只能是以上四種之一。

回頁首

數值

一開始我寫了一個表達數值的類，叫做 Numeral。我為 Numeral 具體代表的是整數、浮點數還是雙精度數而操心。從比較模糊的意義上，我希望它能表達以上任何一種類型和精度的數值。但是我也希望，它能夠明確表達出代表的 具體是哪種類型和精度的數值，如果需要的話。甚至我想到 Numeral 最好也能表達 BigInteger 和 BigDecimal（設想恰巧在某種場合下，我們需要解析和計算一個這樣的表達式，它允許的數值的精度和范圍很大，以至于 Long 或 Double 容納不下），否則在特別的場合下我們將遇到麻煩。在可擴展性上，數值類不大像運算符類，它應該是成熟的，因而幾乎是不需要擴展的。

經過反復嘗試的混亂（Numeral 后來又經過修改甚至重寫），我找到了一個明智的辦法。直接用 java.lang.Number 作為數值類（實際上這是一個接口）。我慶幸地看到，在 Java 中，Integer，Long，Float，Double 甚至 BigInteger，BigDecimal 等數值類都實現了 java.lang.Number（下面簡稱 Number）接口，使用者把 Number 作為何種類型和精度來看待和使用，權利掌握在他 / 她的手中，我不應該提前確定數值的類型和精度。選擇由 Number 類來表達數值，這看來是最好的、代價最小的選擇了，并且保持了相當的靈活性。作為一個順帶的結果，Numeral 類被廢棄了。

回頁首

括號

在表達式中，括號扮演的角色是不可忽視的。它能改變運算的自然優先級，按照用戶所希望的順序進行計算。我用 Bracket 類來表示括號，這個類可以看作是 final，因為它不需要擴展。括號分作括號和右括號，我把它們作為 Bracket 類的兩個靜態實例變量（并且是 Bracket 類僅有的兩個實例變量）。

 public class Bracket   {      private String name;      private Bracket(String name) {          this.name = 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) {          this.name = name;      }      public abstract int getDimension();           // throws ArithmeticException ?     public abstract Number eval(Number[] oprands, int offset);           public Number eval(Number[] oprands) {      	 return eval(oprands,0);      }      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 op1, Operator op2)              throws UnknownOperatorException;      public Object[] convert(Object[] infixExpr)              throws IllegalExpressionException, UnknownOperatorException      {          return convert(infixExpr, 0, infixExpr.length);      }      public Object[] convert(Object[] infixExpr, int offset, int len)              throws IllegalExpressionException, UnknownOperatorException      {           if (infixExpr.length - offset < len)               throw new IllegalArgumentException();          // 創建一個輸出表達式，用來存放結果         ArrayList output = new ArrayList();          // 創建一個工作棧         Stack stack = new Stack();          int currInputPosition = offset;  // 當前位置（于輸入隊列）         System.out.println(" ----------- Begin conversion procedure --------------");         while (currInputPosition < offset + len)          {              Object currInputElement = infixExpr[currInputPosition++];              if (currInputElement instanceof Number) // 數值元素直接輸出             {                  output.add(currInputElement);                  System.out.println("NUMBER:"+currInputElement);//TEMP!              } else if (currInputElement instanceof Bracket) // 遇到括號，進棧或進行匹配             {                  Bracket currInputBracket = (Bracket)currInputElement;                  if (currInputBracket.equals(Bracket.LEFT_BRACKET)) { // 左括號進棧                     stack.push(currInputElement);                  } else { // 右括號，尋求匹配（左括號）                     // 彈出所有的棧元素 ( 運算符 ) 直到遇到 ( 左 ) 括號                     Object stackElement;                      do                      {                           if (!stack.empty())                             stackElement = stack.pop();                           else                             throw new IllegalExpressionException("bracket(s) mismatch");                          if (stackElement instanceof Bracket)                             break;                          output.add(stackElement);                          System.out.println("OPERATOR POPUP:"+stackElement);//TEMP!                     } while (true);                  }              } else if (currInputElement instanceof Operator)              {                  Operator currInputOperator = (Operator)currInputElement;                  // 彈出所有優先級別高于或等于當前的所有運算符                 // ( 直到把滿足條件的全部彈出或者遇到左括號 )                  while (!stack.empty()) {                      Object stackElement = stack.peek();                      if (stackElement instanceof Bracket) {                          break;// 這一定是左括號，沒有可以彈出的了                     } else {                          Operator stackOperator = (Operator)stackElement;                          if (precedenceCompare(stackOperator, currInputOperator) >= 0)                         {                             // 優先級高于等于當前的，彈出（至輸出隊列）                             stack.pop();                              output.add(stackElement);                              System.out.println("OPERATOR:"+stackElement);//TEMP!                          } else {    // 優先級別低于當前的，沒有可以彈出的了                             break;                          }                      }                  }                  // 當前運算符進棧                 stack.push(currInputElement);              } else //if (currInputElement instanceof Variable)                  // 其它一律被認為變量，變量也直接輸出             {                  output.add(currInputElement);                  System.out.println("VARIABLE:"+currInputElement);//TEMP!              }          }          // 將棧中剩下的元素 ( 運算符 ) 彈出至輸出隊列         while (!stack.empty())          {              Object stackElement = stack.pop();              output.add(stackElement);              System.out.println("LEFT STACK OPERATOR:"+stackElement);//TEMP!          }          System.out.println("------------ End conversion procedure --------------");         return output.toArray();      }  }  

讀者可能很快注意到，Converter 類不是一個具體類。既然算法是成熟穩定的，并且我們也把它獨立出來了，為什么 Converter 類不是一個穩定的具體類呢？因為在轉換過程中我發覺必須要面對一個運算符優先級的問題，這是一個不可忽視的問題。按照慣例，如果沒有使用括號顯式地確定計 算的先后順序，那么計算的先后順序是通過比較運算符的優先級來確定的。因為我無法確定用戶在具體使用時，他 / 她的運算符的集合有多大，其中任意兩個運算符之間的優先級順序是怎樣的。這個知識只能由用戶來告訴我。說錯了，告訴給 Converter 類，所以 Converter 類中提供了一個抽象的運算符比較接口 precedenceCompare() 由用戶來實現。

在一段時間內，我為如何檢驗表達式的有效性而困惑。我意識到，轉換通過了并不一定意味著表達式是必定合乎語法的、有效的。甚至接下來成功計算 出后綴表達式的值，也并不能證明原始表達式是有效的。當然，在某些轉換失敗或者計算失敗的情況下，例如運算符的元數與操作數數量不匹配，左右括號不匹配 等，則可以肯定原始表達式是無效的。但是，證明一個表達式是有效的，條件要苛刻的多。遺憾的是，我沒能找到檢驗表達式有效性的理論根據。

回頁首

計算后綴表達式

這是通過一個計算器類 Calculator 來完成的。Calculator 類的核心方法是 eval()，傳給它的參數必須是后綴表達式。在調用本方法之前，如果表達式中含有變量，那么應該被相應的數值替換掉，否則表達式是不可計算的，將導致拋 出 IncalculableExpressionException 異常。算法的基本過程是這樣的：創建一個工作棧，從左到右讀取表達式，讀到數值就壓入棧中；讀到運算符就從棧中彈出 N 個數，計算出結果，再壓入棧中，N 是該運算符的元數；重復上述過程，最后輸出棧頂的數值作為計算結果，結束。

public class Calculator  {       public Number eval(Object[] postfixExpr) throws IncalculableExpressionException      {           return eval(postfixExpr, 0, postfixExpr.length);       }            public Number eval(Object[] postfixExpr, int offset, int len)              throws IncalculableExpressionException       {           if (postfixExpr.length - offset < len)               throw new IllegalArgumentException();                       Stack stack = new Stack();          int currPosition = offset;          while (currPosition < offset + len)          {              Object element = postfixExpr[currPosition++];              if (element instanceof Number) {                  stack.push(element);              } else if (element instanceof Operator)              {                  Operator op = (Operator)element;                  int dimensions = op.getDimension();                  if (dimensions < 1 || stack.size() < dimensions)                     throw new IncalculableExpressionException(                     "lack operand(s) for operator '"+op+"'");                                       Number[] operands = new Number [dimensions];                  for (int j = dimensions - 1; j >= 0; j--)                  {                      operands[j] = (Number)stack.pop();                  }                  stack.push(op.eval(operands));              } else                   throw new IncalculableExpressionException("Unknown element: "                  +element);         }          if (stack.size() != 1)              throw new IncalculableExpressionException("redundant operand(s)");                      return (Number)stack.pop();       }  }  

回頁首

缺省實現

前面我主要討論了關于表達式計算的設計。一個好的設計和實現中常常包括某些缺省的實現。在本案例中，我提供了基本的四則運算符的實現和一個缺省的解析器實現（SimpleParser）。

運算符

實現了加減乘除四種基本運算符。 需要說明一點的是，對于每種基本運算符，當前缺省實現只支持 Number 是 Integer，Long，Float，Double 的情況。并且，需要關注一下不同類型和精度的數值相運算時，結果數值的類型和精度如何確定。缺省實現對此有一定的處理。

解析器

這個缺省的解析器實現，我認為它是簡單的，故取名為 SimpleParser。其基本思想是：把表達式看作是由括號、數值、運算符和變量組成，每種表達式元素都可以相對獨立地進行解析，為此提供一種表達式 元素解析器（ElementParser）。SimpleParser 分別調用四種元素解析器，完成所有的解析工作。

ElementParser 提供了表達式元素級的解析接口。四種缺省的表達式元素解析器類 BasicNumberParser, BasicOperatorParser, DefaultBracketParser，DefaultVariableParser 均實現這個接口。

 public interface ElementParser   {      Object[] parse(char[] expr, int off);   }  

解析方法 parse() 輸入參數指明待解析的串，以及起始偏移。返回結果中存放本次解析所得到的具體元素（Number、Operator、Bracket 或者 Object），以及解析的截止偏移。本次的截至偏移很可能就是下次解析的起始偏移，如果不考慮空白符的話。

那么在整個解析過程中，每種元素解析器何時被 SimpleParser 所調用？我的解決辦法是：它依次調用每種元素解析器。可以說這是一個嘗試的策略。嘗試的先后次序是有講究的，依次是：變量解析器 - 〉運算符解析器 - 〉數值解析器 - 〉括號解析器。

為什么執行這么一種次序？從深層次上反映了我的一種憂慮。這就是：表達式的解析可能是相當復雜的。可能有這樣的表達式，對于它不能完全執行" 分而治之"的解析方式，因為存在需要"整體解析"的地方。例如：考慮"diff(@TotalBytesReceived)"這樣的一個子串。用戶可能用 它可能表達這樣的含義：取采集量 TotalBytesReceived 的前后兩次采集的差值。diff 在這里甚至不能理解成傳統意義上的運算符。最終合理的選擇很可能是，把"diff(@TotalBytesReceived)"整個視為一個變量來解析和 處理。在這樣的情況下，拆開成"diff","(","@bytereceived",")"分別來解析是無意義的、錯誤的。

這就是為什么變量解析器被最先調用，這樣做允許用戶能夠截獲、重新定義超越常規的解析方式以滿足實際需要。實際上，我安排讓變化可能性最大的 部分（如變量）其解析器被最先調用，最小的部分（如括號）其解析器被最后調用。在每一步上，如果解析成功，那么后續的解析器就不會被調用。如果在表達式串 的某個位置上，經過所有的元素解析器都不能解析，那么該表達式就是不可解析的，將拋出 IllegalExpressionException 異常。

回頁首

擴展實現

由于篇幅的關系，不在此通過例子討論擴展實現。這并不意味著目前沒有一個擴展實現。在前面提到的數據采集項目中，由于基本初衷就是支持特別語 法的變量，結果我實現了一個支持變量的擴展實現，并且支持了一些其他運算符，除四則運算符之外。相信讀者能夠看出，我所做的工作體現和滿足了可擴展性。而 擴展性主要體現在運算符和變量上。

回頁首

總結

對于表達式計算，我提出的要求有一定挑戰性，但也并不是太高。然而為了接近或達到這個目標，在設計上我頗費了一番功夫，數易其稿。前面提到， 我丟棄了 Numeral 類，Variable 類。實際上，還不止這些。我還曾經設計了 Element 類，表達式在內部就表示成一個數組 Element[]。在 Element 類中，通過一個枚舉變量指明它包含的到底是什么類型的元素（數值，括號，運算符還是變量）。但是我嗅出這個做法不夠清晰、自然（如果追根究底，可以說不夠 面向對象化），而最后丟棄了這個類。相應地，Element[] 被更直接的 Object[] 所代替。

我的不斷改進的動力，就是力求讓設計在追求其它目標的同時保持簡潔。注意，這并不等于追求過于簡單！我希望我的努力讓我基本達到了這個目標。 我除去了主要的耦合性，讓相對不變的部分 - 表達式轉換和計算部分獨立出來，并把變化的部分 - 運算符和變量，開放出來。雖然在表達式解析上我還留有遺憾，表達式的一般解析接口過于寬泛了，未能為用戶的擴展帶來實質性的幫助。所幸缺省解析器的實現多 少有所彌補。

最后，我希望這個關于表達式計算的設計和實現能夠為他人所用和擴展。我愿意看到它能經受住考驗。

關于作者