發行項
10/09/2015

2015 年 10 月

第 30 卷，第 10 期

本文章是由機器翻譯。

C# - C# 的分割/合併運算式剖析器

由 Vassili Kaplan |2015 年 10 月 |取得程式碼： C#VB

我已發行新的演算法來剖析的數學運算式在 c + + 中的月和年 7 月 2015年問題 CVu 筆記本 (請參閱項目 1 和 2 中 [參考])。因為一個精明的讀者，Silas S 棕色 bug 中找到的第一個演算法實作，因此我必須對它進行一些修改大約需要兩個發行項。由於該讀取器，演算法也變得更成熟。我也已經修正此後的幾個較小的 bug。現在我們即將提供的 C# 中已修正的演算法實作。

您不太可能您不需要撰寫程式碼剖析的數學運算式，但演算法中使用的技巧可以套用至其他案例，以及，例如剖析非標準的字串。使用此演算法也很容易可以定義執行任何您想要的新函式 (例如，請以訂購比薩的 Web 要求)。稍微調整與您也可以建立您自己的 C# 編譯器為您新的自訂指令碼語言。此外，您會發現演算法有趣係依其本身。

發行前在 1961，50 年以上的 Edsger Dijkstra 演算法通常用於剖析 (請參閱「參考資料」中的項目 3) 的數學運算式。但您最好能擁有的替代方法，雖然它有相同的時間複雜性，在我看來更容易實作和擴充。

請注意，我要使用「虛擬建構函式"慣用語函式處理站實作的。這個慣用語引入 c + + 中 James Coplien (請參閱「參考資料」中的項目 4)。我希望您會發現它的使用有趣在 C# 世界中也。

分割合併演算法

中的示範程式 [圖 1 說明分割合併演算法進行剖析的數學運算式。

[圖 1] 示範執行的分割合併演算法

此演算法是由兩個步驟所組成。第一個步驟中包含運算式的字串分割成一份每個資料格如下定義的資料格物件:

class Cell
{
  internal Cell(double value, char action)
  {
    Value = value;
    Action = action;
  }
  internal double Value  { get; set; }
  internal char   Action { get; set; }
}

動作是可以是任何數學運算子的單一字元: '*' (乘法) '/' (除法)，'+' (加號)、 '-' (減法) 或' ^' (power) 或特殊字元表示運算式的我的結尾硬式編碼為 ')。 ' 要合併的資料格的清單中的最後一個項目永遠會特別的動作 ')，' 也就是採取任何動作，但是您可以改用任何其他符號或括號。

在第一個步驟中，運算式會分割為然後轉換為資料格的語彙基元。所有語彙基元是以其中一個數學運算式或括號分隔。可以實際數字或字串中使用的函式名稱的權杖。定義稍後 ParserFunction 類別會負責所有函式中要剖析的字串或剖析的數字的字串。它也可能會呼叫剖析遞迴演算法的整個字串。如果沒有函式和字串中的沒有括號剖析，會有任何遞迴。

在第二個步驟中，所有資料格合併在一起。我們來看第二步先因為它是第一個比較簡單。

合併資料格清單

資料格的清單是合併的一一根據優先順序的動作。也就是數學運算子。這些優先順序計算方式如下:

static int GetPriority(char action)
{
  switch (action) {
    case '^': return 4;
    case '*':
    case '/': return 3;
    case '+':
    case '-': return 2;
  }
  return 0;
}

如果且只有在左邊的資料格動作的優先順序並不比它旁邊的資料格動作的優先順序較低可以合併兩個資料格：

static bool CanMergeCells(Cell leftCell, Cell rightCell)
{
  return GetPriority(leftCell.Action) >= GetPriority(rightCell.Action);
}

合併儲存格表示將左上資料格的動作套用至左上資料格和正確的資料格的值。新的資料格會有相同的動作為正確的資料格，您可以看到在 [圖 2。

[圖 2 合併資料格方法

static void MergeCells(Cell leftCell, Cell rightCell)
{
  switch (leftCell.Action)
  {
    case '^': leftCell.Value = Math.Pow(leftCell.Value, rightCell.Value);
      break;
    case '*': leftCell.Value *= rightCell.Value;
      break;
    case '/': leftCell.Value /= rightCell.Value;
      break;
    case '+': leftCell.Value += rightCell.Value;
      break;
    case '-': leftCell.Value -= rightCell.Value;
      break;
  }
  leftCell.Action = rightCell.Action;
}

例如合併資料格 (8，'-') 和資料格 (5，'+') 會導致新的儲存格 (8 – 5 '+') = 資料格 (3，'+')。

但是如果因為左上資料格的優先順序低於右邊的資料格而無法合併兩個資料格會發生什麼事？然後會發生什麼事是暫時移至下一步，對吧資料格，才能重試合併資料格旁邊，等等，以遞迴方式。已與它旁邊的資料格合併方儲存格，因為我回到原始、左儲存格，並嘗試 remerge 新建的正確儲存格中, 所示 [圖 3。

[圖 3 合併資料格清單

static double Merge(Cell current, ref int index, List<Cell> listToMerge,
                    bool mergeOneOnly = false)
{
  while (index < listToMerge.Count)
  {
    Cell next = listToMerge[index++];
    while (!CanMergeCells(current, next))
    {
      Merge(next, ref index, listToMerge, true /* mergeOneOnly */);
    }
    MergeCells(current, next);
    if (mergeOneOnly)
    {
      return current.Value;
    }
  }
  return current.Value;
}

請注意，從外部、使用 mergeOneOnly 參數設定為 false，所以它不會傳回在完成整個合併之前呼叫這個方法。相較之下，merge 方法呼叫時以遞迴方式 (在左邊和右邊的資料格無法合併因為它們的優先權) 時，mergeOneOnly 會設定為 true，因為我想要返回我已為我完成實際的合併 MergeCells 方法中。

也請注意從 Merge 方法傳回的值是運算式的實際結果。

分割成的資料格清單的運算式

演算法的第一個部分會分割成清單的資料格的運算式。數學運算子優先順序並不在此步驟中考量。首先，運算式會分割為語彙基元清單。任何數學運算子或開啟或關閉的括號分隔的所有權杖。括號可能，但不一定要有相關聯的函式。例如"1 sin(1-2)"都有一個相關聯的函數，但"1-(1-2) 」不會。

首先，讓我們看看當沒有任何函式或括號、只包含實際數字和兩者之間的數學運算子的運算式會發生什麼事。在此情況下，只要建立實際數字及後續的動作所組成的資料格。例如，分割"3-2 * 4" 導致三個資料格所組成的清單:

Split (“3-2*4”) = { Cell(3, ‘-’), Cell(2, ‘*‘), Cell(3, ‘)’) }

最後一個資料格永遠會定義為特殊 END_ARG 動作:

const char END_ARG = ')';

您可加以變更為任何其他帳戶，但在此情況下對應的左括號 START_ARG 必須加以考量的帳號，我定義為：

const char START_ARG = '(';

如果其中一個語彙基元是函式或括號括住的運算式，會將整個分割和-合併演算法套用至使用遞迴。例如，如果運算式是"(3-1)-1"的括號中的整個演算法會先套用到運算式:

Split(“(3-1)-1”) = Split( “[SplitAndMerge(“3-1”)] - 1”) = { Cell(2, ‘-’), Cell(1, ‘)’) }

執行分割函式是 LoadAndCalculate，示 [圖 4。

[圖 4 LoadAndCalculate 方法

public static double LoadAndCalculate(string data, ref int from, char to = END_LINE)
{
  if (from >= data.Length || data[from] == to)
  {
    throw new ArgumentException("Loaded invalid data: " + data);
  }
  List<Cell> listToMerge = new List<Cell>(16);
  StringBuilder item = new StringBuilder();
  do // Main processing cycle of the first part.
  {
    char ch = data[from++];
    if (StillCollecting(item.ToString(), ch, to))
    { // The char still belongs to the previous operand.
      item.Append(ch);
      if (from < data.Length && data[from] != to)
      {
        continue;
      }
    }
    // I am done getting the next token. The getValue() call below may
    // recursively call loadAndCalculate(). This will happen if extracted
    // item is a function or if the next item is starting with a START_ARG '(.'
    ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
    double value = func.GetValue(data, ref from);
    char action = ValidAction(ch) ? ch
                                  : UpdateAction(data, ref from, ch, to);
    listToMerge.Add(new Cell(value, action));
    item.Clear();
  } while (from < data.Length && data[from] != to);
  if (from < data.Length && (data[from] == END_ARG || data[from] == to))
  { // This happens when called recursively: move one char forward.
  from++;
  }
  Cell baseCell = listToMerge[0];
  int index = 1;
  return Merge(baseCell, ref index, listToMerge);
}

LoadAndCalculate 方法會將所有的資料格加入至 listToMerge 清單，然後呼叫 [剖析演算法 merge 函式的第二個部分。StringBuilder 項目會保留目前的權杖，將字元加入至它的其中一個為正在讀取的運算式字串。

StillCollecting 方法會檢查是否仍然收集目前的語彙基元的字元。這並不是這樣如果目前的字元是 END_ARG 或任何其他特殊"to (例如逗號如果剖析引數以逗號; 分隔字元"我會提供這個範例使用 power 函式後續)。此外，如果目前的字元是有效的動作或 START_ARG，不是所不再收集語彙基元:

static bool StillCollecting(string item, char ch, char to)
{
  char stopCollecting = (to == END_ARG || to == END_LINE) ?
                         END_ARG : to;
  return (item.Length == 0 && (ch == '-' || ch == END_ARG)) ||
        !(ValidAction(ch) || ch == START_ARG || ch == stopCollecting);
}
static bool ValidAction(char ch)
{
  return ch == '*' || ch == '/' || ch == '+' || ch == '-' || ch == '^';
}

我知道我已經儘速取得 ValidAction 方法中所述的數學運算子或括號所 START_ARG 或 END_ARG 常數定義收集目前的權杖。另外還有一種特殊情況涉及"-"語彙基元，這用來表示數字開頭負號。

在此分割步驟結束時，括號括住子運算式與所有函式呼叫會透過對整個演算法評估的遞迴呼叫刪除。但這些遞迴呼叫結果動作一定會有 END_ARG 動作，就不會正確全域運算式範圍中如果導出的運算式不是要評估運算式的結尾。這就是為什麼需要在每個遞迴呼叫之後更新動作就像這樣：

char action = ValidAction(ch) ? ch
                                : UpdateAction(data, ref from, ch);

UpdateAction 方法的程式碼位於 [圖 5。

[圖 5 Update 動作方法

static char UpdateAction(string item, ref int from, char ch, char to)
{
  if (from >= item.Length || item[from] == END_ARG || item[from] == to)
  {
    return END_ARG;
  }
  int index = from;
  char res = ch;
  while (!ValidAction(res) && index < item.Length)
  { // Look to the next character in string until finding a valid action.
    res = item[index++];
  }
  from = ValidAction(res) ? index
                          : index > from ? index - 1
                                         : from;
  return res;
}

中的下列程式碼會擷取語彙基元的實際剖析 [圖 4:

ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);

如果已擷取的語彙基元不是函式，此程式碼會嘗試將它轉換為雙精度浮點數。否則適當、先前註冊的函式會呼叫，這也可以依序以遞迴方式呼叫 LoadAndCalculate 方法。

使用者定義和標準函式

我決定實作虛擬建構函式方法第一次所發佈的 James Coplien 誤用函式處理站 (請參閱「參考資料」中的項目 4)。在 C# 中，這通常實作使用 factory 方法 (請參閱「參考資料」中的項目 5)，它會使用額外的處理站類別產生所需的物件。但是 Coplien 的較舊的設計模式不需要額外的處理站外觀類別並改為只會建構新的物件使用衍生自相同的類別實作成員 m_impl 即時:

private ParserFunction m_impl;

特殊的內部建構函式會初始化此成員與適當的類別。建立的實作物件 m_impl 的實際類別取決於輸入參數中所示 [圖 6。

[圖 6 虛擬建構函式

internal ParserFunction(string data, ref int from, string item, char ch)
{
  if (item.Length == 0 && ch == Parser.START_ARG)
  {
    // There is no function, just an expression in parentheses.
    m_impl = s_idFunction;
    return;
  }
  if (m_functions.TryGetValue(item, out m_impl))
  {
    // Function exists and is registered (e.g. pi, exp, etc.).
    return;
  }
  // Function not found, will try to parse this as a number.
  s_strtodFunction.Item = item;
  m_impl = s_strtodFunction;
}

字典用來保存所有剖析器函式。此字典會對應到實作此函式的實際物件的字串函數的名稱 (例如"sin"):

private static Dictionary<string, ParserFunction> m_functions =
      new Dictionary<string, ParserFunction>();

剖析器的使用者可以加入多函式為他們想藉由在基底 ParserFunction 類別上呼叫下列方法:

public static void AddFunction(string name, ParserFunction function)
{
  m_functions[name] = function;
}

GetValue 方法呼叫上建立 ParserFunction，但實際的工作是在實作函式將會覆寫基底類別的評估方法:

public double GetValue(string data, ref int from)
{
  return m_impl.Evaluate(data, ref from);
}
protected virtual double Evaluate(string data, ref int from)
{
  // The real implementation will be in the derived classes.
  return 0;
}

函式實作類別衍生自 ParserFunction 類別，將不會使用內部建構函式中的 [圖 6。相反地，他們會使用基底類別的下列建構函式：

public ParserFunction()
{
  m_impl = this;
}

中 ParserFunction 建構函式中使用兩個特殊的「標準」函數 [圖 6:

private static IdentityFunction s_idFunction = new IdentityFunction();
private static StrtodFunction s_strtodFunction = new StrtodFunction();

第一個是 identity 函數。它會呼叫以剖析括號中沒有相關聯的函式的任何運算式:

class IdentityFunction : ParserFunction
{
  protected override double Evaluate(string data, ref int from)
  {
    return Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
  }
}

第二個函式是一個"catchall"時發現沒有函式呼叫對應至最後一個擷取語彙基元。這會擷取語彙基元時實際數字都已實作的函式。在後者的情況下，將會擲回例外狀況:

class StrtodFunction : ParserFunction
{
  protected override double Evaluate(string data, ref int from)
  {
    double num;
    if (!Double.TryParse(Item, out num)) {
      throw new ArgumentException("Could not parse token [" + Item + "]");
    }
    return num;
  }
  public string Item { private get; set; }
}

所有其他函式可以實作使用者資訊。最簡單的 pi 函式：

class PiFunction : ParserFunction
{
  protected override double Evaluate(string data, ref int from)
  {
    return 3.141592653589793;
  }
}

更典型的實作是 exp 函式：

class ExpFunction : ParserFunction
{
  protected override double Evaluate(string data, ref int from)
  {
    double arg = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
    return Math.Exp(arg);
  }
}

先前我說過我會提供使用需要用逗號分隔的兩個引數的電源函式的範例。這是如何撰寫需要自訂分隔符號分隔的多個引數的函式：

class PowFunction : ParserFunction
{
  protected override double Evaluate(string data, ref int from)
  {
    double arg1 = Parser.LoadAndCalculate(data, ref from, ',');
    double arg2 = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
    return Math.Pow(arg1, arg2);
  }
}

任何數量的功能可以從使用者程式碼加入至演算法就像這樣：

ParserFunction.AddFunction("pi",  new PiFunction());
ParserFunction.AddFunction("exp", new ExpFunction());
ParserFunction.AddFunction("pow", new PowFunction());

總結

此處所呈現的分割合併演算法有 o (n) 複雜性如果 n 為運算式字串中的字元數目。這是因為每個語彙基元將只能讀取一次在分割步驟期間，然後在最糟的情況就不會在大部分的 2 (m-1 –) 1 比較在合併的步驟中，其中: m 是在第一個步驟中建立的資料格數目。

讓演算法都具有相同時間複雜性做為 Dijkstra 演算法 (請參閱「參考資料」中的項目 3)。它可能會因為它會使用遞迴 Dijkstra 演算法比較小缺點。相反地，我相信分割合併演算法是容易實作，正是因為遞迴時，而且也易於擴充與自訂的語法、函數和運算子。

參考資料

V.Kaplan"分割及合併演算法來剖析數學運算式" CVu, 、 27-2、 5 2015年 bit.ly/1Jb470l
V.Kaplan"分割及合併 Revisited，" CVu, 、 27-3、 7 月 2015年 bit.ly/1UYHmE9
E.Dijkstra，Shunting 院子演算法 bit.ly/1fEvvLI
J.Coplien，"進階 c + + 程式設計樣式和慣例」 (p 140) Addison Wesley，1992年
E.Gamma、頭盔 R、 R Johnson 和 J.Vlissides"設計模式：可重複使用物件導向的軟體項目」運算系列 1995 Addison Wesley Professional

Vassili Kaplan是先前的 Microsoft Lync 開發人員。他是熱衷於在 C# 和 c + + 程式設計。他目前住在蘇黎世，瑞士並針對各種銀行 freelancer 擔任。您可以透過他的連絡網址 iLanguage.ch。

感謝以下的微軟技術專家對本文的審閱: James McCaffrey