使用多态性表达评估和树行走？ （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()