使用多態性表達評估和樹行走？ （ala Steve Yegge）

Question

今天早上，我在讀Steve Yegge's: When Polymorphism Fails，當時我遇到了一個問題，那就是他的同事在亞馬遜來採訪時曾經問過潛在的員工。

正如 行動的多態性的例子，讓我們來看看經典的 「EVAL」面試問題，這（如 據我所知）是由羅恩布朗斯坦帶到亞馬遜 。現在的問題是 相當豐富的一個，因爲它設法 探頭各種各樣的重要 技能：面向對象設計，遞歸，二進制 樹木，多態性和運行時 打字，一般編碼技能，（如果 你想它特別難） 解析理論。

在某些時候，候選希望 意識到，你可以代表一個 算術表達式爲二進制 樹，假設你只使用 二進制運算符，如「+」，「 - 」， 「*」 ，「/」。葉節點全部爲 號碼，內部節點全部爲運營商 。評估 表達意味着走樹。如果 的候選人沒有意識到這一點，你可以輕輕地引導他們，或者如果 必要的，只要告訴他們。

即使你告訴他們，它仍然是一個有趣的問題。

的問題，這 一些人（他們的名字，我會 保護我奄奄一息，但他們的 縮寫是威利·劉易斯）的前半部分感覺是 職位要求如果你想調用 自己一個開發者而在亞馬遜 工作實際上很艱難。 的問題是：如何從 算術表達式（如 字符串）（如「2 +（2）」）到 表達式樹。在這個問題上我們可能有一個ADJ 挑戰，在 點。

下半年是：讓我們說這是 2人的項目，和你的伴侶， 誰我們稱之爲「威利」，是 負責轉換 字符串表達式成了一棵樹。你很容易得到 ：你需要決定什麼樣的 類Willie構造 樹。您可以在任何 語言中執行此操作，但請確保您選擇一個， 或威利將爲您提供程序集 語言。如果他感到興奮，那麼 將用於處理器，而不是 在生產中加長。

你會驚訝於有多少候選人 boff這一個。

我不會放棄的答案，但 標準壞的解決方案包括一個開關或情況statment（或只是 老式的級聯IFS）的使用 。一個 稍微好一點的解決方案涉及 使用函數指針， 的表和也許最好的解決方案 涉及使用多態。我鼓勵你在某個時間通過 。好玩的東西！

所以，我們試着用三種方法來解決問題。你如何從算術表達式（如字符串），如「2 +（2）」，到使用級聯的if，表的函數指針表和/或多態的表達式樹？

隨意對付一個，兩個或三個。

[更新：標題修改爲更好地滿足了大多數問題的答案一直]

Answer 1

多態樹走，Python版本

#!/usr/bin/python 

class Node: 
    """base class, you should not process one of these""" 
    def process(self): 
     raise('you should not be processing a node') 

class BinaryNode(Node): 
    """base class for binary nodes""" 
    def __init__(self, _left, _right): 
     self.left = _left 
     self.right = _right 
    def process(self): 
     raise('you should not be processing a binarynode') 

class Plus(BinaryNode): 
    def process(self): 
     return self.left.process() + self.right.process() 

class Minus(BinaryNode): 
    def process(self): 
     return self.left.process() - self.right.process() 

class Mul(BinaryNode): 
    def process(self): 
     return self.left.process() * self.right.process() 

class Div(BinaryNode): 
    def process(self): 
     return self.left.process()/self.right.process() 

class Num(Node): 
    def __init__(self, _value): 
     self.value = _value 
    def process(self): 
     return self.value 

def demo(n): 
    print n.process() 

demo(Num(2))          # 2 
demo(Plus(Num(2),Num(5)))       # 2 + 3 
demo(Plus(Mul(Num(2),Num(3)),Div(Num(10),Num(5)))) # (2 * 3) + (10/2) 

測試只是通過構造建立二叉樹。

程序結構：

抽象基類：節點

• 所有節點從這個類

抽象基類繼承：BinaryNode

• 所有二進制運算符從繼承這個類別
• 處理方法做evaluting表達和返回結果

二元運算符類的工作：加，減，德穆爾，分區

• 兩個子節點，分別爲左側和右側子表達式

數類：貨號

• 保持葉節點數值，例如17或42

Answer 2

字符串標記+ LL（1）語法分析器會給你一個表達式樹...多態性的方式可能涉及一個抽象的算術有「評估（A，b）」函數，其被重寫爲所涉及的每個操作符的類（加，減等），以返回適當的值，並且所述樹包含整數和算術運算符，其可通過柱進行評價（？） - 遍歷樹的順序。

Answer 3

應該海事組織使用函數式語言。樹在OO語言中很難表現和操縱。

Answer 4

或者，也許這是真正的問題： 你怎麼能代表（2）作爲BST？ 這就是讓我絆倒 的部分。

遞歸。

Answer 5

我認爲問題在於我們需要解析perentheses，但它們不是二元運算符？我們是否應該將（2）作爲一個單一的標記，評估結果爲2？

parens不需要顯示在表達式樹中，但它們會影響它的形狀。例如，樹（1 + 2）3從不同1+（2 + 3）：

+ 
/\ 
    + 3 
/\ 
1 2 

與

+ 
/\ 
    1 + 
    /\ 
    2 3 

括號是一個 「提示」 給解析器（例如每superjoe30，以 「遞歸下降」）

Answer 6

回覆：賈斯汀

我覺得樹會是這個樣子：

+ 
/\ 
2 () 
    | 
    2 

基本上，你有一個「EVAL」節點，這只是評估其下方的樹。那將是優化出來擺明：

+ 
/\ 
2 2 

在這種情況下不需要的括號和不添加任何東西。他們不會在邏輯上添加任何東西，所以他們會消失。

Answer 7

這進入解析/編譯器理論，這是一種兔子洞... The Dragon Book是編譯器構造的標準文本，並將其用於極端。在這個特殊情況下，你想爲基本算術構造一個context-free grammar，然後用這個語法解析出一個abstract syntax tree。然後你可以在樹上迭代，從底部開始減少它（此時你會應用多態/函數指針/開關語句來減少樹）。

我發現these notes在編譯器和解析理論上非常有幫助。

Answer 8

@Justin：

看看我的筆記上代表的節點。如果您使用的方案，然後

2 + (2) 

可以表示爲

  . 
     /\ 
     2 () 
      | 
      2 

Answer 9

代表的節點

如果我們要包括括號，我們需要5個不同的節點：

• 二進制節點：添加減去多部分
  這些有兩個孩子，左和鑽機HT側

   + 
      /\ 
  node node 
  

• 舉行值的節點：瓦爾
  沒有孩子節點，只是一個數值

• 來跟蹤括號的節點：括號
  的子表達式一個子節點

  () 
      | 
      node 
  

對於多態的解決方案，我們需要有這種階級關係：

• 節點
• BinaryNode：從節點
• 繼承加：二進制節點繼承
• 減：從二進制節點繼承
• 德穆爾：從二進制節點
繼承
• 事業部：從二進制繼承節點
• 值：從節點繼承
• Paren：繼承節點

所有稱爲eval（）的節點都有一個虛擬函數。如果您調用該函數，它將返回該子表達式的值。

Answer 10

我不會放棄的答案，但 標準壞的解決方案包括一個開關或情況statment（或只是 老式的級聯IFS）的使用 。 A 略好的解決方案涉及 使用功能指針表 和可能的最佳解決方案 涉及使用多態性。

在過去的二十多年的口譯的演變可以看作是走另一條路 - 多態性（如幼稚的Smalltalk metacircular口譯），以函數指針（幼稚Lisp的實現，線程代碼，C++）切換（天真的字節碼解釋器），然後再轉發給JIT等 - 這要麼需要非常大的類，要麼（以單獨的多態語言）雙重調度，這會將多態性降至類型，並且您又回到了第一階段。這裏使用了什麼「最好」的定義？

對於簡單的東西，一個多態的解決方案是好的 - 但是無論是堆棧和字節碼/開關還是利用運行時的編譯器通常都會更好，例如，繪製具有幾千個數據點的函數。

Answer 11

我認爲這個問題是關於如何編寫解析器而不是評估器。或者說，如何從一個字符串創建表達式樹。

返回基類的case語句不完全計數。 「多態」解決方案的基本結構（這是另一種說法，我不在乎你用什麼來構建它，我只是想通過重寫最少量的代碼來擴展它）的反向串行化從具有（動態）一組已知類型的流中獲取對象層次結構。

實現多態解決方案的關鍵是要有一種方法來從模式匹配器創建表達式對象，這可能是遞歸的。即，將BNF或類似語法映射到對象工廠。

Answer 12

以前人們已經提到過，當你使用表達樹時，parens是不必要的。當您查看錶達式樹時，操作順序變得微不足道。該parens是解析器的提示。

雖然接受的答案是解決問題的一半，但另一半 - 實際解析表達式 - 仍未解決。通常，這些問題可以通過使用recursive descent parser來解決。編寫這樣一個解析器通常是一個有趣的練習，但大多數modern tools for language parsing將爲您抽象。

解析器也是顯着如果允許字符串中包含浮點數，則會更難。我必須創建一個DFA來接受C中的浮點數 - 這是一項非常艱苦細緻的任務。請記住，有效的浮點數包括：10,10,10.123,9.876e-5,1.0f，.025等等。我在採訪中假設有一些免除（有利於簡單和簡潔）。

Answer 13

嗯...我不認爲你可以寫一個自頂向下的解析器，沒有回溯，所以它必須是某種類型的shift-reduce解析器。 LR（1）甚至LALR當然可以用以下（ad-hoc）語言定義很好地工作：

開始 - > E1
E1-> E1 + E1 | E1-E1
E1→E2 * E2 | E2/E2 | E2
E2 - >number | （E1）

將它分離爲E1和E2是維持*和/ over +和 - 的優先級所必需的。

但是，這是我會怎麼做，如果我不得不手工編寫解析器：

• 兩個堆棧，一個存儲運營商
• 樹作爲操作數的一個存儲節點和讀取輸入左向右移動數字的葉節點並將它們推入操作數堆棧。
• 如果您有堆棧，彈出2> = 2點的操作數，在操作堆棧中的最頂端的運營商將它們結合起來，推動這種結構回到操作樹，除非
• 下一個經營者有更高的優先級是當前在堆棧頂上的那個。

這給我們留下了處理括號的問題。一個優雅的（我認爲）解決方案是將每個運算符的優先級作爲一個數字存儲在一個變量中。所以最初，

• int plus，minus = 1;
• int mul，div = 2;

現在，每次你看到AA左括號加2所有這些變量，每次你看到一個右括號時，由2

遞減所有的變量時這將確保在+ 3 * （4 + 5）優先於*，3 * 4不會被壓入堆棧。相反，它會等待5，按下4 + 5，然後按下3 *（4 + 5）。

Answer 14

我寫這樣一個解析器的一些基本技術，如 Infix -> RPN和 Shunting Yard和 Tree Traversals。 Here is the implementation I've came up with。它用C++編寫，並在Linux和Windows上編譯。
歡迎任何建議/問題。

所以，我們試着用三種方法來解決這個問題。你如何從算術表達式（如字符串），如「2 +（2）」，到使用級聯的if，表的函數指針表和/或多態性的表達式樹？

這很有趣，但我不認爲這屬於面向對象編程領域......我認爲它更多的與parsing techniques有關。

Answer 15

我一直喜歡這個c＃控制檯應用程序一起作爲一個概念證明位。有一種感覺，它可能會好得多（在GetNode中的switch語句有點笨拙（這是因爲我試圖將類名映射到運算符）。任何關於如何改進的建議都非常受歡迎。

using System; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     string expression = "(((3.5 * 4.5)/(1 + 2)) + 5)"; 
     Console.WriteLine(string.Format("{0} = {1}", expression, new Expression.ExpressionTree(expression).Value)); 
     Console.WriteLine("\nShow's over folks, press a key to exit"); 
     Console.ReadKey(false); 
    } 
} 

namespace Expression 
{ 
    // ------------------------------------------------------- 

    abstract class NodeBase 
    { 
     public abstract double Value { get; } 
    } 

    // ------------------------------------------------------- 

    class ValueNode : NodeBase 
    { 
     public ValueNode(double value) 
     { 
      _double = value; 
     } 

     private double _double; 
     public override double Value 
     { 
      get 
      { 
       return _double; 
      } 
     } 
    } 

    // ------------------------------------------------------- 

    abstract class ExpressionNodeBase : NodeBase 
    { 
     protected NodeBase GetNode(string expression) 
     { 
      // Remove parenthesis 
      expression = RemoveParenthesis(expression); 

      // Is expression just a number? 
      double value = 0; 
      if (double.TryParse(expression, out value)) 
      { 
       return new ValueNode(value); 
      } 
      else 
      { 
       int pos = ParseExpression(expression); 
       if (pos > 0) 
       { 
        string leftExpression = expression.Substring(0, pos - 1).Trim(); 
        string rightExpression = expression.Substring(pos).Trim(); 

        switch (expression.Substring(pos - 1, 1)) 
        { 
         case "+": 
          return new Add(leftExpression, rightExpression); 
         case "-": 
          return new Subtract(leftExpression, rightExpression); 
         case "*": 
          return new Multiply(leftExpression, rightExpression); 
         case "/": 
          return new Divide(leftExpression, rightExpression); 
         default: 
          throw new Exception("Unknown operator"); 
        } 
       } 
       else 
       { 
        throw new Exception("Unable to parse expression"); 
       } 
      } 
     } 

     private string RemoveParenthesis(string expression) 
     { 
      if (expression.Contains("(")) 
      { 
       expression = expression.Trim(); 

       int level = 0; 
       int pos = 0; 

       foreach (char token in expression.ToCharArray()) 
       { 
        pos++; 
        switch (token) 
        { 
         case '(': 
          level++; 
          break; 
         case ')': 
          level--; 
          break; 
        } 

        if (level == 0) 
        { 
         break; 
        } 
       } 

       if (level == 0 && pos == expression.Length) 
       { 
        expression = expression.Substring(1, expression.Length - 2); 
        expression = RemoveParenthesis(expression); 
       } 
      } 
      return expression; 
     } 

     private int ParseExpression(string expression) 
     { 
      int winningLevel = 0; 
      byte winningTokenWeight = 0; 
      int winningPos = 0; 

      int level = 0; 
      int pos = 0; 

      foreach (char token in expression.ToCharArray()) 
      { 
       pos++; 

       switch (token) 
       { 
        case '(': 
         level++; 
         break; 
        case ')': 
         level--; 
         break; 
       } 

       if (level <= winningLevel) 
       { 
        if (OperatorWeight(token) > winningTokenWeight) 
        { 
         winningLevel = level; 
         winningTokenWeight = OperatorWeight(token); 
         winningPos = pos; 
        } 
       } 
      } 
      return winningPos; 
     } 

     private byte OperatorWeight(char value) 
     { 
      switch (value) 
      { 
       case '+': 
       case '-': 
        return 3; 
       case '*': 
        return 2; 
       case '/': 
        return 1; 
       default: 
        return 0; 
      } 
     } 
    } 

    // ------------------------------------------------------- 

    class ExpressionTree : ExpressionNodeBase 
    { 
     protected NodeBase _rootNode; 

     public ExpressionTree(string expression) 
     { 
      _rootNode = GetNode(expression); 
     } 

     public override double Value 
     { 
      get 
      { 
       return _rootNode.Value; 
      } 
     } 
    } 

    // ------------------------------------------------------- 

    abstract class OperatorNodeBase : ExpressionNodeBase 
    { 
     protected NodeBase _leftNode; 
     protected NodeBase _rightNode; 

     public OperatorNodeBase(string leftExpression, string rightExpression) 
     { 
      _leftNode = GetNode(leftExpression); 
      _rightNode = GetNode(rightExpression); 

     } 
    } 

    // ------------------------------------------------------- 

    class Add : OperatorNodeBase 
    { 
     public Add(string leftExpression, string rightExpression) 
      : base(leftExpression, rightExpression) 
     { 
     } 

     public override double Value 
     { 
      get 
      { 
       return _leftNode.Value + _rightNode.Value; 
      } 
     } 
    } 

    // ------------------------------------------------------- 

    class Subtract : OperatorNodeBase 
    { 
     public Subtract(string leftExpression, string rightExpression) 
      : base(leftExpression, rightExpression) 
     { 
     } 

     public override double Value 
     { 
      get 
      { 
       return _leftNode.Value - _rightNode.Value; 
      } 
     } 
    } 

    // ------------------------------------------------------- 

    class Divide : OperatorNodeBase 
    { 
     public Divide(string leftExpression, string rightExpression) 
      : base(leftExpression, rightExpression) 
     { 
     } 

     public override double Value 
     { 
      get 
      { 
       return _leftNode.Value/_rightNode.Value; 
      } 
     } 
    } 

    // ------------------------------------------------------- 

    class Multiply : OperatorNodeBase 
    { 
     public Multiply(string leftExpression, string rightExpression) 
      : base(leftExpression, rightExpression) 
     { 
     } 

     public override double Value 
     { 
      get 
      { 
       return _leftNode.Value * _rightNode.Value; 
      } 
     } 
    } 
} 

Answer 16

好的，這是我的天真實施。對不起，我不覺得使用那個對象，但它很容易轉換。我感覺有點像威利（來自史蒂夫的故事）。

#!/usr/bin/env python 

#tree structure [left argument, operator, right argument, priority level] 
tree_root = [None, None, None, None] 
#count of parethesis nesting 
parenthesis_level = 0 
#current node with empty right argument 
current_node = tree_root 

#indices in tree_root nodes Left, Operator, Right, PRiority 
L, O, R, PR = 0, 1, 2, 3 

#functions that realise operators 
def sum(a, b): 
    return a + b 

def diff(a, b): 
    return a - b 

def mul(a, b): 
    return a * b 

def div(a, b): 
    return a/b 

#tree evaluator 
def process_node(n): 
    try: 
     len(n) 
    except TypeError: 
     return n 
    left = process_node(n[L]) 
    right = process_node(n[R]) 
    return n[O](left, right) 

#mapping operators to relevant functions 
o2f = {'+': sum, '-': diff, '*': mul, '/': div, '(': None, ')': None} 

#converts token to a node in tree 
def convert_token(t): 
    global current_node, tree_root, parenthesis_level 
    if t == '(': 
     parenthesis_level += 2 
     return 
    if t == ')': 
     parenthesis_level -= 2 
     return 
    try: #assumption that we have just an integer 
     l = int(t) 
    except (ValueError, TypeError): 
     pass #if not, no problem 
    else: 
     if tree_root[L] is None: #if it is first number, put it on the left of root node 
      tree_root[L] = l 
     else: #put on the right of current_node 
      current_node[R] = l 
     return 

    priority = (1 if t in '+-' else 2) + parenthesis_level 

    #if tree_root does not have operator put it there 
    if tree_root[O] is None and t in o2f: 
      tree_root[O] = o2f[t] 
      tree_root[PR] = priority 
      return 

    #if new node has less or equals priority, put it on the top of tree 
    if tree_root[PR] >= priority: 
     temp = [tree_root, o2f[t], None, priority] 
     tree_root = current_node = temp 
     return 

    #starting from root search for a place with higher priority in hierarchy 
    current_node = tree_root 
    while type(current_node[R]) != type(1) and priority > current_node[R][PR]: 
     current_node = current_node[R] 
    #insert new node 
    temp = [current_node[R], o2f[t], None, priority] 
    current_node[R] = temp 
    current_node = temp 



def parse(e): 
    token = '' 
    for c in e: 
     if c <= '9' and c >='0': 
      token += c 
      continue 
     if c == ' ': 
      if token != '': 
       convert_token(token) 
       token = '' 
      continue 
     if c in o2f: 
      if token != '': 
       convert_token(token) 
      convert_token(c) 
      token = '' 
      continue 
     print "Unrecognized character:", c 
    if token != '': 
     convert_token(token) 


def main(): 
    parse('(((3 * 4)/(1 + 2)) + 5)') 
    print tree_root 
    print process_node(tree_root) 

if __name__ == '__main__': 
    main()