使用多态性进行表达评估和树木行走？(ala Steve Yegge)

今天早上,我正在阅读Steve Yegge的文章:当多态性失败时,当我遇到一个问题时,他的同事在他们来亚马逊采访时曾经问过潜在的员工.

作为多态行动的一个例子,让我们来看看经典的"eval"面试问题,据我所知,这个问题是由Ron Braunstein带到亚马逊的.这个问题非常丰富,因为它设法探究各种重要技能:OOP设计,递归,二叉树,多态和运行时输入,一般编码技巧,以及(如果你想更加努力)解析理论.

在某些时候,候选人希望你能够将算术表达式表示为二叉树,假设你只使用二进制运算符,如"+"," - ","*","/".叶节点都是数字,内部节点都是运算符.评估表达意味着走树.如果候选人没有意识到这一点,你可以轻轻地引导他们,或者如果有必要,告诉他们.

即使你告诉他们,这仍然是一个有趣的问题.

问题的前半部分,一些人(他的名字我将保护我的垂死气息,但他们的姓名首字母是威利刘易斯)感觉是工作要求,如果你想打电话给自己一个开发人员和工作在亚马逊,实际上是有点难.问题是:你如何从算术表达式(例如字符串),如"2 +(2)"到表达式树.在某些时候,我们可能会对此问题进行ADJ挑战.

下半部分是:假设这是一个2人的项目,你的合作伙伴,我们称之为"Willie",负责将字符串表达式转换为树.你可以轻松获得:你需要决定Willie用什么类构建树.您可以使用任何语言进行操作,但请确保选择一种语言,否则Willie将为您提供汇编语言.如果他感觉不舒服,那将是一个不再生产的处理器.

你会对有多少候选人感到惊讶.

我不会泄露答案,但标准不良解决方案涉及使用开关或案例陈述(或只是好老式的级联ifs).一个稍微好一点的解决方案涉及使用函数指针表,而可能最佳解决方案涉及使用多态.我鼓励你在某个时候完成它.好玩的东西!

所以,让我们尝试以三种方式解决问题.你如何使用cascaded-if,一个函数指针表和/或多态来从算术表达式(例如字符串中)如"2 +(2)"到表达式树？

随意解决一个,两个或所有三个问题.

[更新:修改标题以更好地匹配大多数答案.]

1> Mark Harriso..：

---

多态树行走,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

所有二元运算符都继承自此类

process方法执行evaluting表达式并返回结果的工作

二元运算符类:Plus,Minus,Mul,Div

两个子节点,每个子节点用于左侧和右侧子表达式

数字等级:Num

保存叶节点数值,例如17或42

---

问题是算术计算SUCH AS 2 +(2),而不是2 +(2)的计算.因此,它不是过度设计,而是按预期回答问题.

---

"你得到了简单的部分:你需要决定Willie用什么类构建树."