使用多态性进行表达评估和树行走？（阿拉·史蒂夫·叶格）
https://stackoverflow.com/questions/12516
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
今天早上，我正在读书 史蒂夫·叶格：当多态性失败时, ，当我遇到他的一位同事在潜在员工来亚马逊面试时经常问的一个问题时。
作为行动中多态性的一个例子，让我们看一下经典的“评估”访谈问题，据我所知，罗恩·布劳恩斯坦（Ron Braunstein）将其带到了亚马逊。这个问题是一个很丰富的问题，因为它设法探究了各种重要技能：OOP设计，递归，二进制树，多态性和运行时键入，一般编码技能，以及（如果您想使其更加困难）解析理论。
在某个时候，候选人有望意识到您可以将算术表达式表示为二进制树，假设您只使用诸如“+”，“”，“”，“*”，“/”之类的二进制运算符。叶节点都是数字，并且内部节点都是运算符。评估表达方式意味着漫步树。如果候选人没有意识到这一点，您可以轻轻地引导他们去，或者在必要时告诉他们。
即使您告诉他们，这仍然是一个有趣的问题。
问题的前半部分，有些人（我将在垂死的呼吸中保护他们的名字，但他们的首字母是威利·刘易斯（Willie Lewis）），如果您想称自己为开发人员并在亚马逊工作，这是一个工作要求。问题是：您如何从算术表达式（例如在字符串中），例如表达树的“ 2 +（2）”。在某个时候，我们可能会在这个问题上面临挑战。
下半场是：假设这是一个2人的项目，您称为“ Willie”的伴侣负责将字符串表达式转换为树。您得到的简单部分：您需要确定Willie是哪个类来构造树。您可以用任何语言做到这一点，但是请确保您选择一种语言，或者威利将递给您的汇编语言。如果他感觉很奇怪，那将是一个不再在生产中生产的处理器。
您会惊讶于有多少候选人这个人。
我不会给出答案，但是标准的不良解决方案涉及使用开关或案例陈述（或者只是好老式的级联 - ifs）。一个更好的解决方案涉及使用功能指针表，并且可能最佳的解决方案涉及使用多态性。我鼓励您在某个时候进行工作。好玩的东西！
因此，让我们尝试用三种方法来解决这个问题。你如何从算术表达式（例如在字符串中）（例如“2 + (2)”）到使用级联 if 的表达式树、函数指针表和/或多态性？
随意解决一个、两个或全部三个问题。
[更新：标题已修改，以更好地匹配大多数答案。]
解决方案
多态树行走,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)
测试只是使用构造函数构建二叉树。
程序结构：
抽象基类：节点
- 所有节点都继承自该类
抽象基类：二进制节点
- 所有二元运算符都继承自此类
- process 方法执行计算表达式并返回结果的工作
二元运算符类：加、减、乘、除
- 两个子节点，左侧和右侧子表达式各一个
号码类别：数量
- 保存叶节点数值，例如17 或 42
其他提示
我认为问题是我们需要解析括号，但它们不是二元运算符？我们是否应该将 (2) 作为单个标记，其计算结果为 2？
括号不需要出现在表达式树中，但它们确实会影响其形状。例如，(1+2)+3 的树与 1+(2+3) 不同：
+
/ \
+ 3
/ \
1 2
相对
+
/ \
1 +
/ \
2 3
括号是对解析器的“提示”（例如，per superjoe30，“递归下降”）
代表节点
如果我们想要包含括号，我们需要 5 种节点：
二进制节点：加减乘除
他们有两个孩子，一个左边，一个右边+ / \ node node保存值的节点：瓦尔
没有子节点，只有一个数值一个跟踪括号的节点：帕伦
子表达式的单个子节点( ) | node
对于多态解决方案，我们需要具有这种类关系：
- 节点
- 二进制节点：继承自节点
- 加：从二元节点继承
- 减 ：从二元节点继承
- 穆尔：从二元节点继承
- 部门：从二元节点继承
- 价值 ：继承自节点
- 帕伦：从节点继承
所有节点都有一个名为 eval() 的虚函数。如果调用该函数，它将返回该子表达式的值。
String Tokenizer + LL(1) Parser 将为您提供一个表达式树...多态性方式可能涉及一个带有“evaluate(a,b)”函数的抽象算术类，该函数会被所涉及的每个运算符（加法、减法等）覆盖以返回适当的值，并且树包含整数和算术运算符，可以通过树的后（？）序遍历来评估。
我不会给出答案，但是标准的不良解决方案涉及使用开关或案例陈述（或者只是好老式的级联 - ifs）。一个更好的解决方案涉及使用功能指针表，并且可能最佳的解决方案涉及使用多态性。
解释器最近 20 年的发展可以被看作是在走另一条路——多态性（例如朴素的 Smalltalk 元循环解释器）到函数指针（朴素的 lisp 实现、线程代码、C++）到切换（朴素的字节码解释器），然后向前发展。 JIT 等 - 要么需要非常大的类，要么（在单多态语言中）双分派，这将多态性减少到类型情况，然后您又回到了第一阶段。这里使用的“最佳”的定义是什么？
对于简单的东西，多态解决方案就可以了 - 这是我之前做的一个, ，但是如果您要绘制具有几千个数据点的函数，那么堆栈和字节码/开关或利用运行时的编译器通常会更好。
嗯...我认为你不能为此编写一个自上而下的解析器而不进行回溯，因此它必须是某种移位归约解析器。LR(1) 甚至 LALR 当然可以很好地使用以下（临时）语言定义：
开始 -> E1
E1-> E1+E1 | E1-E1
E1-> E2*E2 | E2/E2 | E2
E2-> 数字 | （E1）
将其分成 E1 和 E2 对于保持 * 和 / 相对于 + 和 - 的优先级是必要的。
但如果我必须手动编写解析器，我会这样做：
- 两个堆栈，一个将树的节点存储为操作数，一个存储运算符
- 从左到右读取输入，生成数字的叶节点并将它们推入操作数堆栈。
- 如果堆栈上有 >= 2 个操作数，则弹出 2 个，将它们与运算符堆栈中最顶层的运算符组合起来，并将该结构推回操作数树， 除非
- 下一个运算符的优先级高于当前位于堆栈顶部的运算符。
这给我们留下了处理括号的问题。一种优雅的（我认为）解决方案是将每个运算符的优先级作为数字存储在变量中。所以最初，
- int 加、减 = 1；
- int mul, div = 2;
现在，每次看到左括号时，所有这些变量都会增加 2，每次看到右括号时，所有变量都会减少 2。
这将确保3*(4+5)中的+比*具有更高的优先级，并且3*4不会被压入堆栈。相反，它会等待 5，推送 4+5，然后推送 3*(4+5)。
关于：贾斯汀
我认为这棵树看起来像这样：
+
/ \
2 ( )
|
2
基本上，您有一个“eval”节点，它只评估它下面的树。然后将其优化为：
+
/ \
2 2
在这种情况下，不需要括号，也不添加任何内容。他们没有逻辑地添加任何东西，所以他们就会消失。
我认为问题在于如何编写解析器，而不是评估器。或者更确切地说，如何从字符串创建表达式树。
返回基类的 Case 语句并不完全有效。
“多态”解决方案的基本结构（换句话说，我不在乎你用什么来构建它，我只想通过重写尽可能少的代码来扩展它）是从具有一组（动态）已知类型的流。
多态解决方案实现的关键是有一种方法从模式匹配器（可能是递归的）创建表达式对象。即，将 BNF 或类似语法映射到对象工厂。
或者也许这才是真正的问题：如何将 (2) 表示为 BST？那是绊倒我的部分。
递归。
@贾斯汀：
看看我关于表示节点的注释。如果您使用该方案，那么
2 + (2)
可以表示为
.
/ \
2 ( )
|
2
我认为应该使用函数式语言。树在面向对象语言中更难表示和操作。
正如人们之前提到的，当您使用表达式树时，不需要括号。当您查看表达式树时，操作顺序变得微不足道且显而易见。括号是对解析器的提示。
虽然公认的答案是问题一半的解决方案，但另一半（实际上解析表达式）仍未解决。通常，可以使用以下方法解决此类问题 递归下降解析器. 。编写这样的解析器通常是一个有趣的练习，但大多数 现代语言分析工具 将为您抽象出来。
解析器也是 显著地 如果字符串中允许浮点数，则难度更大。我必须创建一个 DFA 来接受 C 中的浮点数——这是一项非常艰苦且详细的任务。请记住，有效的浮点数包括：10、10.、10.123、9.876e-5、1.0f、0.025 等我认为采访中对此进行了一些豁免（为了简单和简洁）。
我有点把这个 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;
}
}
}
}
好的，这是我的幼稚实现。抱歉，我不喜欢使用对象，但它很容易转换。我觉得有点像邪恶的威利（来自史蒂夫的故事）。
#!/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()
