식 평가 및 트리 산책을 사용하여 다형성?(ala 스티브 Yegge)
https://stackoverflow.com/questions/12516
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
아침,저는 읽기 스티브 Yegge 의:을 때 실패 다형성, 을 때,내가 나가는 질문을 공동 작업자의 자신의 요청하는 데 사용되는 잠재적인 직원을 때 그들은 그들의 인터뷰에서는 아마존이다.
의 예로서 다형성 작업자 보 classic "eval"면접 질문(로 직까지)가 Amazon 론습니다.질문 아주 부유 한,그것 관리 프로브는 다양한 중요한 기술:OOP 디자인,재귀,바이너리 나무,다형성 및 런타임 입력하면,일반적인 코딩 기술,그리고(는 경우 당신이 그것을 만들고 싶어 하드 추가) 분석 이론이다.
어떤 시점에서,후보자는 희망 을 실현할 수 있는 대표 산술식으로 바이너리 트리 가정하면,당신은 단지 사용 바이너리 사업자와 같은"+","-", "*","/".리프 노드들은 모든 숫자,내부 노드가 모든 연산자입니다.평가 식 걷는 의미합니다.는 경우 후보지 않는 이것을 깨닫 할 수 있는 부드럽게 그들을 인도하는 경우,또는 필요 단지 그들에게 말한다.
는 경우에도 당신은 그들에게 말해,그것은 아직도 흥미로운 문제입니다.
상반기 질문 어떤 사람(그의 이름을 내가 을 보호하기 위해 내 죽어가는 숨,그러나 그들의 이니셜는 윌리 Lewis)느낌입니다 작업 요구 사항을 호출하려는 경우 자신이 개발자와 작업 아마존은 실제로 좀 어렵습니다.이 질문:당신은 어떻게서 산술 식(예:에 문)같은"2+(2)"하는 식 나무입니다.우리는 할 수 있습 ADJ 도전에 이 질문에 일부 점이다.
하반기:말하자이 2-사람이 프로젝트 파트너 누가는"윌리",가 에 대한 책임을 변화 문자열 표현으로 나무입니다.당신 쉬운 부분이다:당신은 무엇인지를 결정해야 클래스 윌리를 건설하는 것입 트리니다.당신은 그것을 할 수 있습에서 모든 언어 확인,하지만 당신은 하나를 선택, 또는 윌리 손 것입니다 당신이 어셈블리 언어입니다.는 경우에는 그 느낌의 비열,그것은 에 대한 것입니다 프로세서는 아 더 이상 제조되는 생산.
당신이 깜짝 놀라게 할 것이 얼마나 많은 후보자 boff 이 하나입니다.
나는 멀리 주지 않을 것이 대답하지만, 표준 나쁜 솔루션 사용을 포함 의 스위치는 경우 문(나 좋은 옛날 계단식-ifs).A 약간 더 나은 솔루션 포함 테이블을 사용하의 함수 포인터 그리고 아마 최고의 솔루션 를 사용하여 포함한 다형성이다.나 당신을 격려를 통해 작업 그 습니다.재미있는!
그렇게 하려고 문제를 해결하기 위해 세 가지 방법이 있다.어떻게 당신이 표현식(예:문)같은"2+(2)"을 표현이 나무를 사용하여 계단식-의 경우,함수 포인터의 테이블 및/또는 다형성?
료를 연결하는,두 개 또는 세 개의 모든.
[업데이트:제목 수정치는 무엇 대부분의 답이 있습니다.]
해결책
다형 트리킹, Python version
#!/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 표현하고 그 결과를 반환한
바이너리 운영자 클래스:Plus,Minus,Mul,Div
- 두 자녀의 노드에 대해 각각 하나씩 왼쪽과 오른쪽 부분식
수 클래스:Num
- 을 보유하고 잎 노드의 숫자 값이,예를 들어,17 42
다른 팁
문제,내 생각,우리가 필요로 하는 구문 분석하 perentheses,그럼에도 불구하고 그들은하지 않는 이진 operator?을 해야 하는(2)하나로 토큰으로 평가되는 2?
에 괄호를 보여줄 필요가 없에서 식 트리,하지만 그들은 영향을 미치는 그것의 모양입니다.E.g., 을 위해 나무(1+2)+3 에서 다른 1+(2+3):
+
/ \
+ 3
/ \
1 2
대
+
/ \
1 +
/ \
2 3
괄호는"힌트"을 파서(예를 들어,당 superjoe30,하"재귀적으로 내려")
이 얻으로 구문 분석/이론 컴파일러,어떤 종류의 토끼 구멍... 드래곤 예약 은 표준에 대한 텍스트를 컴파일러를 건설하고,이를 극단입니다.이 특정한 경우,당신이 원하는 구성 context-free grammar 에 대한 기본적인 연산,다음 사용하는 문법을 분석하는 니.할 수 있습을 반복하여 나무,그것을 줄이 아래에서 위로(그 이 시점에서 적용할텐데 다형성/함수 포인터 스위치/스 문을 줄일 수리).
내가 찾았 이러한 노트 용할 수 있에 컴파일러 및 구문 분석 이론이다.
을 대표하는 노드가
우리가 원하는 경우를 포함 괄호,우리가 필요한은 5 종류의 노드:
바이너리 노드:추가 마이너스 Mul Div
이러한 두 아이가 있고,왼쪽과 오른쪽+ / \ node node노드를 개최하는 값:Val
아니 아이들이 노드 그냥 숫자 값노드를 추적하 괄호:괄
단 하나 아동 노드를 위한 부분식( ) | node
에 대한 다형 솔루션을,우리는 이런 종류의 등 관계:
- 노드
- BinaryNode:에서 상속 노드
- 스:바이너리에서 상속 노드
- 마이너스:바이너리에서 상속 노드
- Mul:바이너리에서 상속 노드
- Div:바이너리에서 상속 노드
- 값:에서 상속 노드
- 괄:에서 상속 노드
가상 기능을 위해 모든 노드 라는 eval().를 호출하는 경우는 기능,그것은이의 값을 반환하는 부분식.
문자열한 토+LL(1)파서를 줄 것이다 당신은 식 트리...다형성 방법이 포함될 수 있습니다 추상적인 연산 등으로"평가(a,b)"기능을 재정의 각 사업자의 참여(또한 빼기 등)의 적절한 값을 반환,그리고 나무 포함하는 정수 연산자,수에 의해 평가되는 게시(?)-기 위해 탐색의 나무입니다.
나는 멀리 주지 않을 것이 대답하지만, 표준 나쁜 솔루션 사용을 포함 의 스위치는 경우 문(나 좋은 옛날 계단식-ifs).A 약간 더 나은 솔루션 포함 테이블을 사용하의 함수 포인터 그리고 아마 최고의 솔루션 를 사용하여 포함한 다형성이다.
마지막 이십년의 진화에서 통역사로 볼 수있다 가 다른 방법-다형성(예를 들어 순진 Smalltalk metacircular 통역)함수 포인터(순진 lisp 구현,스레드 코드,C++)하 스위치(순진 바이트 코드를 통역),및 다음 이후 JITs 에는가 필요 하거나 매우 큰 종류,또는(에서 단독으로 다형 언어)두 번 파견을 감소시키는 다형성을 유형 케이스,그리고 당신 뒤에서 단 하나입니다.What 의 정의는'최적의'에서 사용할까요?
에 대한 간단한 물건을 다형 솔루션은 좋습니다- 여기에 내가 만들어가 이전, 지 스택과 바이트 코드 스위치/스 또는 이용 런타임의 컴파일러는 일반적으로 더 나은 당신이 말한 음모를 꾸미고,함수와 함께 몇 천 데이터 포인트입니다.
Hm...나는 생각하지 않을 작성할 수 있습향 파서를 이 역추적을 사용하지 않는다,그래서 그것을 일종의 변화를 감소 parser.LR(1)또는 LALR 것입니다 물론 잘 작동과 다음(ad-hoc)어의 정의:
시작->E1
E1->E1+E1|E1-E1
E1->E2*E2|E2/E2|E2
E2-> 번호 |(E1)
분리하여 그것을 밖으로 E1 및 E2 을 유지하기 위해 필요한의 우선 순위*과/전+고.
그러나 이것은 어떻게 할 지에 대해서는 경우에 그것을 쓰는 파서에 의해 손:
- 두 가지 스택 중 하나는 저장하는 노드의 트리 피연산자로하고 하나는 저장하는 운영자
- 을 읽을 입력을 왼쪽이,리프 노드의 숫자와 밀로의 연산자 스택입니다.
- 이 있는 경우>=2 피연산자 스택에 팝 2,그들을 결합으로 최상위자에서 운영자 스택 및 이 구조는 백을 피연산자,나무 지
- 다음 연산자는 더 높은 우선 순위는 현재의 상부에 쌓입니다.
이것은 우리에게 문제를 처리하는 부류입니다.하나는 우아한(I thought)솔루션은 저장소의 우선 순위는 각 연산자로 숫자를 변수입니다.그래서 처음에,
- int 플러스,마이너스=1;
- int mul,div=2;
지금를 볼 때마다 왼쪽에 부류 증가는 이러한 모든 변수에 의해 2,과를 볼 때마다 오른쪽 부류의 감소한 모든 변수에 의 2.
이지 확인+3*(4+5)보다 높은 우선 순위*및 3*4 되지 않습 밀어 스택에.대신하는 것이 기다릴 것이 5 밀어 4+5,다음 밀어 3*(4+5).
Re:Justin
나는 생각한 나무는 다음과 같이 보일 것이다:
+
/ \
2 ( )
|
2
기본적으로,당신은 당신이"eval"노드는 그냥 평가하고 나무 아래에 있습니다.는 것이 최적화되고:
+
/ \
2 2
이 경우 괄호는 필요하지 않습과하지 않는 아무것도 추가.그들은하지 않는 아무것도 추가 논리적으로,그래서 그들은 그냥 멀리 이동합니다.
나는 생각한 질문은 대를 작성하는 방법을 파서,지 평가자.거나 오히려,을 만드는 방법 식 트리에서 문자열입니다.
경우 문장 반환하는 기본 클래스지 않는 정확하게 계산합니다.
의 기본적인 구조를"다형"솔루션(는 또 다른 방법을 말하는 내가 무슨 상관 없 당신은 건축이 함께 나는 단지 확장하려는 그것을 다시 쓰기도 양의 코드를 가능)deserialize 개체 계층구조에서 스트림(동적)설정의 로 알려진 유형입니다.
의 핵심 구현한 다형 솔루션을 만들 수 있는 방법 식 객체에서 패턴을 정합 가능성,재귀적입니다.I.e., 지도 BNF 또는 이와 유사한 구문을 개체 공장도 있습니다.
나 어쩌면 이것은 진짜 문제는:할 수 있는 방법을 나타냅(2)BST?는 부분이 나를 넘어지 니다.
재귀.
@저스틴:
볼트에서 나타내는 노드입니다.당신이 사용하는 경우 그 계획,다음
2 + (2)
로 표시될 수 있습니다
.
/ \
2 ( )
|
2
를 사용해야 한능한 언어 imo.나무들은 열심히 나타내고 조작에 OO 언어입니다.
으로 사람들이 언급은 이전에 사용하는 경우,식 트 괄호는 필요하지 않습니다.주문 작업의 사소한된다고 명백하면 당신이 찾고있는 표현이 나무입니다.에 괄호 힌트를 parser.
하는 동안 허용된 응답은 솔루션의 절반 문제가 다른 절반이 실제로 구문 분석하는 표현은 아직도 미해결.일반적으로 이러한 종류의 문제를 해결할 수 있을 사용하여 재귀 출신 파서.쓰고 그러한 분석은 자주 재미있는 운동이지만,대부분의 현대적인 도구를 사용하여 언어에 대한 구문 분석 을 추상화하는 멀리습니다.
Parser 도 크 열심히도록 허용하면 실수로서 귀하의 문자열입니다.을 만들 수 있었다 DFA 을 받아들이 부동 소수점의 숫자에서는 C-그것은 매우 힘든 상세한 작업입니다.기억,유효한 부동 소수점은 다음과 같습니다:10,10., 10.123,9.876e-5,1.0f,.025,etc.나는 가정부 경륜의 시대에서 이러(의 찬성 simplicty 과 간결)에서 만들어졌다.
내가 작성한 파서 몇 가지 기본적인 기술
중위->RPN 고
Shunting Yard 고
트리 순회.
여기에는 구현에 나가 함께 했.
그것의 서면에서는 C++컴파일하고 모두에서 리눅스와 Windows.
어떤 제안/질문을 환영합니다.
그렇게 하려고 문제를 해결하기 위해 세 가지 방법이 있다.어떻게 당신이 표현식(예:문)같은"2+(2)"을 표현이 나무를 사용하여 계단식-의 경우,함수 포인터의 테이블 및/또는 다형성?
이것은 재미있지만,나는 생각하지 않는 이 영역에 속의 객체-지향 프로그래밍...나는 생각은 그것을 함께 할 수 분석 기법.
나는 종류의 척이 c#콘솔 응용 프로그램으로 함께 비트의 개념의 증명입니다.있는 느낌을 수 많은(스위치의 문 GetNode 은 종류의 투박한(그것은 거기에도중 빈도하지도 클래스 이름을 운영자에게)).어떤 제안에 그것을 개선 할 수있는 방법에 대한 매우 환영합니다.
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()
