oop - 使用多态性的表达式评估和树行走？（阿拉史蒂夫耶格）

Question

今天早上，我在阅读Steve Yegge 的《当多态性失败时》时，遇到了一个问题，他的一位同事曾经在潜在员工来亚马逊面试时问他们这个问题。

作为多态性的一个例子，让我们看一下经典的“eval”面试问题，（据我所知）是由 Ron Braunstein 带到亚马逊的。这个问题非常丰富，因为它设法探讨了各种各样的重要技能：OOP 设计、递归、二叉树、多态性和运行时类型、一般编码技能，以及（如果你想让它更难的话）解析理论.

在某些时候，候选人希望意识到您可以将算术表达式表示为二叉树，假设您只使用诸如“+”、“-”、“*”、“/”之类的二元运算符。叶节点都是数字，内部节点都是算子。评估表达式意味着遍历树。如果应聘者没有意识到这一点，你可以温和地引导他们，或者如果有必要，直接告诉他们。

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

问题的前半部分，有些人（我将保护他们的名字直到我垂死的呼吸，但他们的名字首字母是威利刘易斯）觉得如果你想称自己为开发人员并在亚马逊工作，这是一个工作要求，实际上有点难. 问题是：如何从诸如“2 + (2)”之类的算术表达式（例如在字符串中）到表达式树。在某个时候，我们可能会在这个问题上遇到 ADJ 挑战。

后半部分是：假设这是一个 2 人项目，你的搭档，我们称之为“Willie”，负责将字符串表达式转换为树。你得到了简单的部分：你需要决定 Willie 用什么类来构造树。你可以用任何一种语言来做，但一定要选择一种，否则威利会把汇编语言交给你。如果他感到不耐烦，那将是针对不再生产的处理器。

你会惊讶于有多少候选人喜欢这个。

我不会给出答案，但标准错误解决方案涉及使用 switch 或 case 语句（或只是好的老式级联 ifs）。稍微好一点的解决方案涉及使用函数指针表，而可能最好的解决方案涉及使用多态性。我鼓励你在某个时候完成它。好玩的东西！

所以，让我们尝试通过三种方式来解决这个问题。如何使用级联-if、函数指针表和/或多态性从算术表达式（例如在字符串中）如“2 + (2)”到表达式树？

随意解决一个，两个或所有三个。

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

score 12 · Accepted Answer

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

score 4 · Accepted Answer

我认为问题在于我们需要解析括号，但它们不是二元运算符？我们是否应该将 (2) 作为单个标记，计算结果为 2？

括号不需要出现在表达式树中，但它们确实会影响其形状。例如，(1+2)+3 的树不同于 1+(2+3)：

相对

括号是对解析器的“提示”（例如，根据 superjoe30，“递归下降”）

score 4 · Accepted Answer

这涉及到解析/编译器理论，这有点像兔子洞…… Dragon Book是编译器构造的标准文本，并将其发挥到了极致。在这种特殊情况下，您想为基本算术构造一个上下文无关文法，然后使用该文法解析出抽象语法树。然后，您可以遍历树，从下往上减少它（此时您将应用多态性/函数指针/switch 语句来减少树）。

我发现这些注释对编译器和解析理论非常有帮助。

score 4 · Accepted Answer

表示节点

如果我们想包含括号，我们需要 5 种节点：

二元节点： Add Minus Mul Div
这些有两个孩子，一个左侧和右侧
```
     +
    / \
node   node
```
保存值的节点： Val
没有子节点，只是一个数值
跟踪括号的节点：
为子表达式Paren单个子节点
```
    ( )
     |
    node
```

对于多态解决方案，我们需要有这种类关系：

节点
BinaryNode : 从 Node 继承
加：从二进制节点继承
减号：从二进制节点继承
Mul : 从二进制节点继承
div : 从二进制节点继承
值：从节点继承
Paren : 从节点继承

所有节点都有一个名为 eval() 的虚函数。如果您调用该函数，它将返回该子表达式的值。

score 2 · Accepted Answer

String Tokenizer + LL(1) Parser 会给你一个表达式树......多态方式可能涉及一个带有“evaluate(a,b)”函数的抽象算术类，该函数被涉及的每个运算符覆盖（另外，减法等）以返回适当的值，并且树包含整数和算术运算符，它们可以通过树的后（？）顺序遍历来评估。

score 2 · Accepted Answer

我不会给出答案，但标准错误解决方案涉及使用 switch 或 case 语句（或只是好的老式级联 ifs）。稍微好一点的解决方案涉及使用函数指针表，而可能最好的解决方案涉及使用多态性。

解释器过去 20 年的演变可以看作是另一种方式——多态性（例如朴素的 Smalltalk 元循环解释器）到函数指针（朴素的 lisp 实现、线程代码、C++）到切换（朴素的字节码解释器），然后再往前走到 JIT 等等——它们要么需要非常大的类，要么（在单一多态语言中）双重调度，这将多态性减少到类型案例，你又回到了第一阶段。这里使用的“最佳”定义是什么？

对于简单的东西，多态解决方案是可以的——这是我之前做的一个，但是如果你要绘制一个包含几千个数据点的函数，那么堆栈和字节码/切换或利用运行时的编译器通常会更好。

score 2 · Accepted Answer

嗯...我认为您不能为此编写自上而下的解析器而无需回溯，因此它必须是某种移位减少解析器。LR(1) 甚至 LALR 当然可以很好地使用以下（临时）语言定义：

开始 -> E1
E1 -> E1+E1 | E1-E1
E1 -> E2*E2 | E2/E2 | E2
E2 ->数字| (E1)

将它分成 E1 和 E2 是必要的，以保持 * 和 / 高于 + 和 - 的优先级。

但是，如果我必须手动编写解析器，我会这样做：

两个栈，一个存储树的节点作为操作数，一个存储操作符
从左到右读取输入，制作数字的叶节点并将它们推入操作数堆栈。
如果堆栈上有 >= 2 个操作数，则弹出 2，将它们与操作符堆栈中最顶部的操作符组合并将此结构推回操作数树，除非
下一个运算符的优先级高于当前位于堆栈顶部的运算符。

这给我们留下了处理括号的问题。一种优雅的（我认为）解决方案是将每个运算符的优先级存储为变量中的数字。所以一开始，

整数加，减 = 1；
int mul, div = 2;

现在，每次看到左括号时，所有这些变量都增加 2，每次看到右括号时，所有变量都减少 2。

这将确保 3*(4+5) 中的 + 比 * 具有更高的优先级，并且 3*4 不会被压入堆栈。相反，它将等待 5，按 4+5，然后按 3*(4+5)。

score 1 · Accepted Answer

回复：贾斯汀

我认为这棵树看起来像这样：

  +
 / \
2  ( )
    |
    2

基本上，你会有一个“eval”节点，它只是评估它下面的树。然后将其优化为：

  +
 / \
2   2

在这种情况下，不需要括号，也不添加任何内容。他们没有在逻辑上添加任何东西，所以他们就会离开。

score 1 · Accepted Answer

我认为问题在于如何编写解析器，而不是评估器。或者更确切地说，如何从字符串创建表达式树。

返回基类的 case 语句不完全计数。

“多态”解决方案的基本结构（这是另一种说法，我不在乎你用什么构建它，我只想通过重写尽可能少的代码来扩展它）是从一个反序列化对象层次结构具有一组（动态）已知类型的流。

实现多态解决方案的关键是有一种方法可以从模式匹配器创建表达式对象，可能是递归的。即，将 BNF 或类似语法映射到对象工厂。

score 0 · Accepted Answer

0

应该使用功能语言imo。树在面向对象语言中更难表示和操作。

于 2008-08-15T19:28:32.513 回答

score 0 · Accepted Answer

或者这可能是真正的问题：你如何将 (2) 表示为 BST？那是让我绊倒的部分。

递归。

score 0 · Accepted Answer

@贾斯汀：

查看我关于表示节点的注释。如果您使用该方案，那么

2 + (2)

可以表示为

score 0 · Accepted Answer

正如人们之前提到的，当您使用表达式树时，不需要括号。当您查看表达式树时，操作顺序变得微不足道且显而易见。括号是对解析器的提示。

虽然公认的答案是解决问题的一半，但另一半——实际上是解析表达式——仍未解决。通常，这些问题可以使用递归下降解析器来解决。编写这样的解析器通常是一个有趣的练习，但是大多数现代的语言解析工具都会为您抽象出它。

如果您在字符串中允许浮点数，解析器也会变得更加困难。我必须创建一个 DFA 来接受 C 中的浮点数——这是一项非常艰苦和详细的任务。请记住，有效的浮点数包括：10, 10., 10.123, 9.876e-5, 1.0f, .025 等。我假设在采访中对此有所豁免（有利于简单和简洁）。

score 0 · Accepted Answer

我用一些基本技术编写了这样的解析器，例如 Infix -> RPN和 Shutting Yard and Tree Traversals。这是我想出的实现。
它是用 C++ 编写的，可以在 Linux 和 Windows 上编译。
欢迎任何建议/问题。

所以，让我们尝试通过三种方式来解决这个问题。如何使用级联-if、函数指针表和/或多态性从算术表达式（例如在字符串中）如“2 + (2)”到表达式树？

这很有趣，但我认为这不属于面向对象编程的领域......我认为它更多地与解析技术有关。

score 0 · Accepted Answer

我有点把这个 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;
            }
        }
    }
}

score 0 · Accepted Answer

好的，这是我的幼稚实现。抱歉，我不觉得为那个使用对象，但它很容易转换。我觉得有点像邪恶的威利（来自史蒂夫的故事）。

#!/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()

oop - 使用多态性的表达式评估和树行走？（阿拉史蒂夫耶格）

16 回答 16

Related

Reference