oop - 使用多态性进行表达式评估和树遍历？ (阿拉史蒂夫耶格)

Question

今天早上，我正在阅读Steve Yegge's: When Polymorphism Fails ，当我遇到一个问题时，他的一位同事曾经在潜在员工来亚马逊面试时询问他们。

As an example of polymorphism in action, let's look at the classic "eval" interview question, which (as far as I know) was brought to Amazon by Ron Braunstein. The question is quite a rich one, as it manages to probe a wide variety of important skills: OOP design, recursion, binary trees, polymorphism and runtime typing, general coding skills, and (if you want to make it extra hard) parsing theory.

At some point, the candidate hopefully realizes that you can represent an arithmetic expression as a binary tree, assuming you're only using binary operators such as "+", "-", "*", "/". The leaf nodes are all numbers, and the internal nodes are all operators. Evaluating the expression means walking the tree. If the candidate doesn't realize this, you can gently lead them to it, or if necessary, just tell them.

Even if you tell them, it's still an interesting problem.

The first half of the question, which some people (whose names I will protect to my dying breath, but their initials are Willie Lewis) feel is a Job Requirement If You Want To Call Yourself A Developer And Work At Amazon, is actually kinda hard. The question is: how do you go from an arithmetic expression (e.g. in a string) such as "2 + (2)" to an expression tree. We may have an ADJ challenge on this question at some point.

The second half is: let's say this is a 2-person project, and your partner, who we'll call "Willie", is responsible for transforming the string expression into a tree. You get the easy part: you need to decide what classes Willie is to construct the tree with. You can do it in any language, but make sure you pick one, or Willie will hand you assembly language. If he's feeling ornery, it will be for a processor that is no longer manufactured in production.

You'd be amazed at how many candidates boff this one.

I won't give away the answer, but a Standard Bad Solution involves the use of a switch or case statment (or just good old-fashioned cascaded-ifs). A Slightly Better Solution involves using a table of function pointers, and the Probably Best Solution involves using polymorphism. I encourage you to work through it sometime. Fun stuff!

所以，让我们尝试用所有三种方式来解决这个问题。您如何从算术表达式(例如在字符串中)(例如“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

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

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

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

两个子节点，左侧和右侧子表达式各一个

数字类: Num

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