تقييم التعبير والمشي على الشجرة باستخدام تعدد الأشكال؟(علاء ستيف ييجي)
https://stackoverflow.com/questions/12516
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هذا الصباح كنت أقرأ ستيف ييجي:عندما يفشل تعدد الأشكال, ، عندما صادفت سؤالًا كان أحد زملائه في العمل يطرحه على الموظفين المحتملين عندما يأتون لإجراء المقابلة في أمازون.
كمثال على تعدد الأشكال في العمل ، دعونا نلقي نظرة على سؤال مقابلة "Eval" الكلاسيكي ، والذي تم إحضاره (بقدر ما أعرف) إلى Amazon بواسطة Ron Braunstein.السؤال غني تمامًا ، لأنه قادر على التحقيق في مجموعة واسعة من المهارات المهمة:تصميم OOP ، العودية ، الأشجار الثنائية ، تعدد الأشكال وكتابة وقت التشغيل ، مهارات الترميز العامة ، (إذا كنت ترغب في جعلها نظرية تحليلية للغاية).
في مرحلة ما ، نأمل أن يدرك المرشح أنه يمكنك تمثيل تعبير حسابي كشجرة ثنائية ، على افتراض أنك تستخدم فقط مشغلي ثنائي مثل "+" ، "-" ، "*" ، "/".العقد الأوراق كلها أرقام ، والعقد الداخلية كلها مشغليين.تقييم التعبير يعني المشي على الشجرة.إذا لم يدرك المرشح ذلك ، فيمكنك قيادتهم بلطف ، أو إذا لزم الأمر ، فما عليك سوى إخبارهم.
حتى لو أخبرتهم ، فإنها لا تزال مشكلة مثيرة للاهتمام.
إن النصف الأول من السؤال ، الذي يشعر به بعض الأشخاص (أسماؤهم سوف أحميهم في أنفاسي المحتضرة ، لكن الأحرف الأولى من أن ويلي لويس) يشعر بأنه متطلب عمل إذا كنت تريد أن تسمي نفسك مطورًا والعمل في Amazon. .السؤال هو:كيف تنتقل من تعبير حسابي (على سبيل المثالفي سلسلة) مثل "2 + (2)" إلى شجرة تعبير.قد نواجه تحديًا كبيرًا في هذا السؤال في مرحلة ما.
النصف الثاني هو :دعنا نقول أن هذا مشروع شخصين ، وشريكك ، الذي نسميه "ويلي" ، مسؤول عن تحويل تعبير السلسلة إلى شجرة.تحصل على الجزء السهل:تحتاج إلى أن تقرر الفصول التي سيقوم ببناء الشجرة بها.يمكنك القيام بذلك بأي لغة ، ولكن تأكد من اختيار واحدة ، أو سيسلم ويلي لغة التجميع.إذا كان يشعر بالزخرفة ، فسيكون ذلك لمعالجًا لم يعد يتم تصنيعه في الإنتاج.
ستندهش من عدد المرشحين هذا.
لن أتخلى عن الإجابة ، لكن الحل السيئ القياسي ينطوي على استخدام التبديل أو إحصاء الحالة (أو مجرد متتالية من الطراز القديم).يتضمن حل أفضل قليلاً استخدام جدول مؤشرات الوظيفة ، وربما يكون الحل الأفضل استخدام تعدد الأشكال.أشجعك على العمل من خلاله في وقت ما.متعة الاشياء!
لذا، دعونا نحاول معالجة المشكلة بالطرق الثلاث.كيف يمكنك الانتقال من تعبير حسابي (على سبيل المثال؟في سلسلة) مثل "2 + (2)" إلى شجرة تعبير باستخدام علامات if المتتالية و/أو جدول مؤشرات الوظائف و/أو تعدد الأشكال؟
لا تتردد في التعامل مع واحد أو اثنين أو الثلاثة.
[تحديث:تم تعديل العنوان ليتوافق بشكل أفضل مع معظم الإجابات.]
المحلول
المشي على شجرة متعددة الأشكال, نسخة بايثون
#!/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
- جميع العوامل الثنائية ترث من هذه الفئة
- تقوم طريقة العملية بتقييم التعبير وإرجاع النتيجة
فئات المشغل الثنائي:زائد، ناقص، مول، شعبة
- عقدتان فرعيتان، واحدة لكل من التعبيرات الفرعية للجانب الأيسر والأيمن
فئة الرقم:رقم
- يحمل قيمة رقمية للعقدة الورقية، على سبيل المثال.17 أو 42
نصائح أخرى
أعتقد أن المشكلة هي أننا بحاجة إلى تحليل الأقواس، ومع ذلك فهي ليست عاملًا ثنائيًا؟هل يجب أن نأخذ (2) كرمز واحد، والذي يساوي 2؟
لا يلزم ظهور الأقواس في شجرة التعبير، ولكنها تؤثر على شكلها.على سبيل المثال، شجرة (1+2)+3 تختلف عن 1+(2+3):
+
/ \
+ 3
/ \
1 2
عكس
+
/ \
1 +
/ \
2 3
الأقواس هي "تلميح" للمحلل اللغوي (على سبيل المثال، لكل superjoe30، "للنزول بشكل متكرر")
هذا يدخل في نظرية التحليل/المترجم، وهو نوع من حفرة الأرانب ... كتاب التنين هو النص القياسي لبناء المترجم، ويأخذ هذا إلى أقصى الحدود.في هذه الحالة بالذات، تريد بناء قواعد خالية من السياق بالنسبة للحسابات الأساسية، استخدم تلك القواعد لتحليل شجرة بناء الجملة مجردة.يمكنك بعد ذلك التكرار على الشجرة، وتقليلها من الأسفل إلى الأعلى (في هذه المرحلة يمكنك تطبيق عبارة تعدد الأشكال/مؤشرات الوظيفة/التبديل لتقليل الشجرة).
لقد وجدت هذه الملاحظات لتكون مفيدة بشكل لا يصدق في نظرية المترجم والتحليل.
تمثيل العقد
إذا أردنا تضمين الأقواس، فنحن بحاجة إلى 5 أنواع من العقد:
العقد الثنائية:إضافة ناقص Mul Div
هؤلاء لديهم طفلان، الجانب الأيسر والأيمن+ / \ node nodeعقدة للاحتفاظ بقيمة:فال
لا توجد عقد فرعية، مجرد قيمة رقميةعقدة لتتبع الأقواس:بارين
عقدة فرعية واحدة للتعبير الفرعي( ) | node
للحصول على حل متعدد الأشكال، نحتاج إلى هذا النوع من العلاقة الطبقية:
- العقدة
- العقدة الثنائية :ترث من العقدة
- بالإضافة إلى :ترث من العقدة الثنائية
- ناقص :ترث من العقدة الثنائية
- مول :ترث من العقدة الثنائية
- شعبة :ترث من العقدة الثنائية
- قيمة :ترث من العقدة
- الأب :ترث من العقدة
هناك وظيفة افتراضية لجميع العقد تسمى eval ().إذا قمت باستدعاء هذه الدالة، فسوف تُرجع قيمة هذا التعبير الفرعي.
String Tokenizer + LL(1) Parser سيعطيك شجرة تعبير...قد تتضمن طريقة تعدد الأشكال فئة حسابية مجردة مع وظيفة "تقييم (أ، ب)"، والتي يتم تجاوزها لكل عامل من العوامل المعنية (الجمع والطرح وما إلى ذلك) لإرجاع القيمة المناسبة، وتحتوي الشجرة على أعداد صحيحة وعوامل حسابية ، والتي يمكن تقييمها من خلال اجتياز الشجرة بعد (؟) أمر.
لن أتخلى عن الإجابة ، لكن الحل السيئ القياسي ينطوي على استخدام التبديل أو إحصاء الحالة (أو مجرد متتالية من الطراز القديم).يتضمن حل أفضل قليلاً استخدام جدول مؤشرات الوظيفة ، وربما يكون الحل الأفضل استخدام تعدد الأشكال.
يمكن رؤية العشرين عامًا الأخيرة من التطور في المترجمين الفوريين على أنها تسير في الاتجاه الآخر - تعدد الأشكال (على سبيل المثال، مترجمو Smalltalk metacircular البسيطون) لتشغيل المؤشرات (تطبيقات LISP الساذجة، التعليمات البرمجية المترابطة، C++) للتبديل (مترجمو كود البايت الساذجون)، ثم فصاعدًا إلى JITs وما إلى ذلك - والتي تتطلب إما فصولًا كبيرة جدًا، أو (في اللغات متعددة الأشكال الفردية) إرسال مزدوج، مما يقلل من تعدد الأشكال إلى حالة كتابة، وتعود إلى المرحلة الأولى.ما هو تعريف "الأفضل" المستخدم هنا؟
بالنسبة للأشياء البسيطة، الحل متعدد الأشكال مقبول - هنا واحدة قمت بها في وقت سابق, ، ولكن عادةً ما يكون استخدام المكدس والرمز الثانوي/التبديل أو استغلال مترجم وقت التشغيل أفضل إذا كنت، على سبيل المثال، ترسم دالة ببضعة آلاف من نقاط البيانات.
همم...لا أعتقد أنه يمكنك كتابة محلل من أعلى إلى أسفل لهذا دون التراجع، لذلك يجب أن يكون نوعًا من المحلل اللغوي لتقليل التحول.بالطبع ستعمل LR(1) أو حتى LALR بشكل جيد مع تعريف اللغة (المخصص) التالي:
ابدأ -> E1
E1 -> E1+E1 | E1-E1
E1 -> E2*E2 | E2/E2 | E2
ه2-> رقم | (E1)
من الضروري فصلها إلى E1 وE2 للحفاظ على أسبقية * و/over + و-.
ولكن هذه هي الطريقة التي سأفعل بها ذلك إذا اضطررت إلى كتابة المحلل اللغوي يدويًا:
- مكدسان، عقد تخزين واحد للشجرة كمعاملات وعامل تخزين واحد
- اقرأ الإدخال من اليسار إلى اليمين، وقم بإنشاء عقد ورقية من الأرقام وادفعها إلى مكدس المعامل.
- إذا كان لديك >= 2 معاملات على المكدس، فقم بإخراج 2، وادمجهم مع العامل العلوي في مكدس المشغل وادفع هذه البنية مرة أخرى إلى شجرة المعاملات، إلا إذا
- يتمتع عامل التشغيل التالي بأولوية أعلى من العامل الموجود حاليًا أعلى المكدس.
وهذا يترك لنا مشكلة التعامل مع الأقواس.أحد الحلول الأنيقة (على ما أعتقد) هو تخزين أسبقية كل عامل كرقم في متغير.لذا في البداية،
- كثافة العمليات زائد، ناقص = 1؛
- كثافة العمليات، div = 2؛
الآن في كل مرة ترى قوسًا أيسرًا قم بزيادة كل هذه المتغيرات بمقدار 2، وفي كل مرة ترى قوسًا أيمنًا، قم بإنقاص جميع المتغيرات بمقدار 2.
سيضمن هذا أن + في 3*(4+5) له أسبقية أعلى من *، ولن يتم دفع 3*4 إلى المكدس.بدلاً من ذلك، سينتظر 5، ثم يدفع 4+5، ثم يدفع 3*(4+5).
يكرر:جاستن
أعتقد أن الشجرة ستبدو هكذا:
+
/ \
2 ( )
|
2
في الأساس، سيكون لديك عقدة "تقييم"، والتي تقوم فقط بتقييم الشجرة الموجودة أسفلها.سيتم بعد ذلك تحسين ذلك ليصبح مجرد:
+
/ \
2 2
في هذه الحالة، الأقواس ليست مطلوبة ولا تضيف أي شيء.إنهم لا يضيفون أي شيء بشكل منطقي، لذا فهم يرحلون.
أعتقد أن السؤال يتعلق بكيفية كتابة المحلل اللغوي وليس المقيم.أو بالأحرى، كيفية إنشاء شجرة التعبير من سلسلة.
لا يتم احتساب عبارات الحالة التي تُرجع فئة أساسية تمامًا.
البنية الأساسية للحل "متعدد الأشكال" (وهي طريقة أخرى للقول، لا يهمني ما الذي تبني عليه هذا، أريد فقط توسيعه بإعادة كتابة أقل قدر ممكن من التعليمات البرمجية) هو إلغاء تسلسل التسلسل الهرمي للكائن من دفق مع مجموعة (ديناميكية) من الأنواع المعروفة.
جوهر تنفيذ الحل متعدد الأشكال هو أن يكون لديك طريقة لإنشاء كائن تعبير من مُطابق النمط، وهو على الأرجح متكرر.على سبيل المثال، قم بتعيين BNF أو بناء جملة مشابه لمصنع الكائنات.
أو ربما هذا هو السؤال الحقيقي:كيف يمكنك تمثيل (2) كـ BST؟هذا هو الجزء الذي يرفعني.
العودية.
@ جاستن:
انظر إلى ملاحظتي حول تمثيل العقد.إذا كنت تستخدم هذا المخطط، ثم
2 + (2)
يمكن تمثيلها على أنها
.
/ \
2 ( )
|
2
يجب استخدام لغة وظيفية imo.يصعب تمثيل الأشجار ومعالجتها بلغات OO.
كما ذكر الناس سابقًا، عند استخدام أشجار التعبير، لا تكون الأقواس ضرورية.يصبح ترتيب العمليات تافهًا وواضحًا عندما تنظر إلى شجرة التعبير.الأقواس هي تلميحات للمحلل اللغوي.
في حين أن الإجابة المقبولة هي الحل لنصف المشكلة، فإن النصف الآخر - في الواقع تحليل التعبير - لا يزال دون حل.عادة، يمكن حل هذا النوع من المشاكل باستخدام محلل النسب العودي.غالبًا ما تكون كتابة مثل هذا المحلل اللغوي تمرينًا ممتعًا، ولكن معظمها الأدوات الحديثة لتحليل اللغة سوف تجريد ذلك بعيدا بالنسبة لك.
المحلل اللغوي هو أيضا بشكل كبير أصعب إذا سمحت بأرقام الفاصلة العائمة في السلسلة الخاصة بك.اضطررت إلى إنشاء DFA لقبول أرقام الفاصلة العائمة في لغة C - لقد كانت مهمة شاقة ومفصلة للغاية.تذكر أن النقاط العائمة الصالحة تتضمن ما يلي:10، 10.، 10.123، 9.876e-5، 1.0f، .025، إلخ.أفترض أنه تم الإعفاء من هذا (لصالح البساطة والإيجاز) في المقابلة.
لقد كتبت مثل هذا المحلل مع بعض التقنيات الأساسية مثلإنفيكس -> RPN وساحة النقل واجتياز الأشجار.
هنا هو التنفيذ الذي توصلت إليه.
إنه مكتوب بلغة C++ ويتم تجميعه على كل من Linux و Windows.
نرحب بأي اقتراحات/أسئلة.
لذا، دعونا نحاول معالجة المشكلة بالطرق الثلاث.كيف يمكنك الانتقال من تعبير حسابي (على سبيل المثال؟في سلسلة) مثل "2 + (2)" إلى شجرة تعبير باستخدام علامات if المتتالية و/أو جدول مؤشرات الوظائف و/أو تعدد الأشكال؟
هذا مثير للاهتمام، لكنني لا أعتقد أن هذا ينتمي إلى عالم البرمجة الشيئية...أعتقد أن له علاقة أكبر بـ تقنيات التحليل.
لقد قمت بتجميع تطبيق وحدة التحكم 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()
