अभिव्यक्ति मूल्यांकन और वृक्ष polymorphism का उपयोग कर चलना? (एला स्टीव Yegge)

आज सुबह, मैं स्टीव येगेज: जब पॉलीमोर्फिज्म विफल रहता है पढ़ रहा था, जब मैं पार आया एक सवाल यह है कि जब उनके अमेज़ॅन में साक्षात्कार के लिए आए तो उनके एक सहकर्मी संभावित कर्मचारियों से पूछने के लिए इस्तेमाल करते थे।

में polymorphism का एक उदाहरण के रूप में   कार्रवाई, चलो क्लासिक देखें   साक्षात्कार प्रश्न "eval", जो (जैसा   जहां तक ​​मुझे पता है) अमेज़ॅन लाया गया था   रॉन ब्रुनस्टीन द्वारा। प्रश्न है   काफी समृद्ध है, क्योंकि यह प्रबंधन करता है   एक विस्तृत विविधता की जांच करें   कौशल: ओओपी डिजाइन, रिकर्सन, बाइनरी   पेड़, बहुरूपता और रनटाइम   टाइपिंग, सामान्य कोडिंग कौशल, और (यदि   आप इसे अतिरिक्त कठिन बनाना चाहते हैं)   पार्सिंग सिद्धांत।

     

किसी बिंदु पर उम्मीदवार उम्मीदवार   यह समझता है कि आप एक का प्रतिनिधित्व कर सकते हैं   एक द्विआधारी के रूप में अंकगणितीय अभिव्यक्ति   पेड़, मानते हुए कि आप केवल उपयोग कर रहे हैं   द्विआधारी ऑपरेटर जैसे "+", "-",   "*", "/"। पत्ता नोड्स सभी हैं   संख्याएं, और आंतरिक नोड्स हैं   सभी ऑपरेटरों। मूल्यांकन करना   अभिव्यक्ति का मतलब है पेड़ चलना। अगर   उम्मीदवार को यह एहसास नहीं है,   आप धीरे-धीरे उन्हें ले जा सकते हैं, या यदि   जरूरी है, बस उन्हें बताओ।

     

यहां तक ​​कि यदि आप उन्हें बताते हैं, यह अभी भी एक है   दिलचस्प समस्या।

     

प्रश्न का पहला भाग, जो   कुछ लोग (जिनके नाम मैं करेंगे   मेरी मरने वाली सांस की रक्षा करें, लेकिन उनका   शुरुआती विली लुईस हैं) महसूस एक है   नौकरी की आवश्यकता अगर आप कॉल करना चाहते हैं   स्वयं एक डेवलपर और काम पर   अमेज़ॅन, वास्तव में थोड़ी मुश्किल है।   सवाल यह है कि आप कैसे से जाते हैं   अंकगणितीय अभिव्यक्ति (उदा। ए में   स्ट्रिंग) जैसे "2 + (2)" को एक   अभिव्यक्ति पेड़ हमारे पास एडीजे हो सकता है   कुछ पर इस सवाल पर चुनौती   बिंदु।

     

दूसरा आधा है: मान लें कि यह है   एक 2 व्यक्ति परियोजना, और आपके साथी,   जिसे हम "विली" कहते हैं, है   बदलने के लिए जिम्मेदार है   एक पेड़ में स्ट्रिंग अभिव्यक्ति। आपको मिला   आसान हिस्सा: आपको यह तय करने की ज़रूरत है कि क्या   कक्षाएं विली का निर्माण करना है   पेड़ के साथ। आप इसे किसी भी में कर सकते हैं   भाषा, लेकिन सुनिश्चित करें कि आप एक चुनते हैं,   या विली आपको असेंबली सौंपेगी   भाषा। अगर वह ऑर्नेरी महसूस कर रहा है, तो यह   एक प्रोसेसर के लिए होगा जो नहीं है   उत्पादन में अब निर्मित।

     

आप कितने उम्मीदवारों पर चकित होंगे   यह एक बोफ।

     

मैं जवाब नहीं दूंगा, लेकिन ए   मानक खराब समाधान में उपयोग शामिल है   एक स्विच या केस स्टेटमेंट (या बस   अच्छी पुरानी शैली वाली कैस्केड-आईएफएस)। ए   थोड़ा बेहतर समाधान शामिल है   फ़ंक्शन पॉइंटर्स की एक तालिका का उपयोग करके,   और शायद सबसे अच्छा समाधान   polymorphism का उपयोग शामिल है। मैं   आपको इसके माध्यम से काम करने के लिए प्रोत्साहित करते हैं   कुछ समय। मज़ा सामान!

तो, चलो समस्या से निपटने का प्रयास तीनों तरीकों से करें। आप एक अंकगणितीय अभिव्यक्ति (उदाहरण के लिए एक स्ट्रिंग में) जैसे कि "2 + (2)" को कैस्केड-इज़, फ़ंक्शन पॉइंटर्स की एक तालिका, और/या बहुरूपता का उपयोग करके अभिव्यक्ति वृक्ष में कैसे जाते हैं?

एक, दो, या तीनों से निपटने के लिए स्वतंत्र महसूस करें।

[अद्यतन: बेहतर मिलान करने के लिए शीर्षक संशोधित किया गया है कि अधिकांश उत्तर क्या हैं।]

0
ro fr bn
मार्क हैरिसन के जवाब के आधार पर, मैंने एक PHP कार्यान्वयन लिखा है
जोड़ा लेखक serdarsenay, स्रोत

12 उत्तर

Polymorphic Tree Walking, 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)

परीक्षण केवल रचनाकारों का उपयोग करके बाइनरी पेड़ का निर्माण कर रहे हैं।

कार्यक्रम संरचना:

सार आधार वर्ग: नोड

  • सभी नोड्स इस वर्ग से प्राप्त होते हैं

सार आधार वर्ग: बाइनरी नोड

  • सभी बाइनरी ऑपरेटरों को इस वर्ग से प्राप्त होता है
  • प्रक्रिया विधि अभिव्यक्ति को evaluting और परिणाम लौटने का काम
  • करता है

बाइनरी ऑपरेटर कक्षाएं: प्लस, मिनस, मुल, डिव

  • दो बच्चे नोड्स, एक बाएं तरफ और दाएं तरफ उप-अभिव्यक्तियों के लिए प्रत्येक

संख्या वर्ग: संख्या

  • एक पत्ता-नोड संख्यात्मक मान रखता है, उदा। 17 या 42
0
जोड़ा
सवाल एक अंकगणितीय गणना के लिए था जैसे कि 2 + (2), 2 + (2) की गणना नहीं। इसलिए, यह अधिक इंजीनियर नहीं है, लेकिन सवाल के रूप में सवाल का जवाब है।
जोड़ा लेखक Thomas Owens, स्रोत
"आपको आसान हिस्सा मिल जाता है: आपको यह तय करने की ज़रूरत है कि किस वर्ग के साथ पेड़ का निर्माण करना है।"
जोड़ा लेखक vanja., स्रोत
यह जवाब इस सवाल का नहीं है कि "आप अंकगणितीय अभिव्यक्ति (उदाहरण के लिए STRING में) कैसे जाते हैं जैसे कि" 2 + (2) "...." डेमो (प्लस (मुल (न्यू) (2) कहां है, न्यूम (3)), डिव (न्यूम (10), न्यूम (5)))) "आओ? वह अन्य कार्यक्रम जिसे हम नहीं देखते हैं? इसे सर्वश्रेष्ठ जवाब के रूप में क्यों चिह्नित किया जाता है?
जोड़ा लेखक Guge, स्रोत
यह जवाब बहुत अधिक इंजीनियर है। सवाल 2 + (2) के लिए था, मनमानी अंकगणितीय गणना नहीं। इसके अलावा, यह सिर्फ पेड़ को निष्पादित करता है, यह इसे नहीं बनाता है।
जोड़ा लेखक ReaperUnreal, स्रोत

@Justin:

नोड्स का प्रतिनिधित्व करने पर मेरा नोट देखें। यदि आप उस योजना का उपयोग करते हैं, तो

2 + (2)

के रूप में प्रतिनिधित्व किया जा सकता है

           .
         /\
         2  ( )
             |
             2
0
जोड़ा

नोड्स का प्रतिनिधित्व करना

अगर हम कोष्ठक शामिल करना चाहते हैं, तो हमें 5 प्रकार के नोड्स की आवश्यकता है:

  • the binary nodes: Add Minus Mul Div
    these have two children, a left and right side

         +
       /\
    node   node
    
  • a node to hold a value: Val
    no children nodes, just a numeric value

  • a node to keep track of the parens: Paren
    a single child node for the subexpression

        ( )
         |
        node
    

एक बहुलक समाधान के लिए, हमें इस तरह के वर्ग संबंध होने की आवश्यकता है:

  • नोड
  • बाइनरी नोड: नोड से प्राप्त
  • प्लस: बाइनरी नोड से प्राप्त
  • माइनस: बाइनरी नोड से प्राप्त
  • Mul: बाइनरी नोड से प्राप्त
  • Div: बाइनरी नोड से प्राप्त
  • मान: नोड से प्राप्त
  • माता-पिता: नोड से प्राप्त

Eval() नामक सभी नोड्स के लिए वर्चुअल फ़ंक्शन है। यदि आप उस फ़ंक्शन को कॉल करते हैं, तो वह उस सबएक्सप्रेस के मान को वापस कर देगा।

0
जोड़ा
कुछ मामलों में है। आपके पास मूल अभिव्यक्ति को फिर से लिखने/पुनः बनाने के लिए एक टूल हो सकता है, और मूल अभिव्यक्ति में अनावश्यकता को अनुकूलित नहीं किया जा सकता है। बेशक, अभिव्यक्ति का मूल्यांकन करने और उत्तर प्राप्त करने के मामले में आप सही हैं।
जोड़ा लेखक Mark Harrison, स्रोत
अमूर्त वाक्यविन्यास पेड़ में कोष्ठक शामिल करने का कोई कारण नहीं है।
जोड़ा लेखक Jonas Kongslund, स्रोत

या शायद यह असली सवाल है:   आप बीएसटी के रूप में (2) कैसे प्रतिनिधित्व कर सकते हैं?   यही वह हिस्सा है जो मुझे ट्राइप कर रहा है   अप।

प्रत्यावर्तन।

0
जोड़ा

एक कार्यात्मक भाषा आईएमओ का उपयोग करना चाहिए। पेड़ ओओ भाषाओं में प्रतिनिधित्व और कुशलतापूर्वक उपयोग करने के लिए कठिन हैं।

0
जोड़ा
वास्तव में ? यह बेवकूफ सी ++ कार्यान्वयन है: कक्षा एएसटी {वेक्टर <�एएसटी *> बच्चे; शून्य धक्का (एएसटी *);/* बच्चे जोड़ें, yacc/bison पार्सर /एएसटी eval() से बुलाया जाना चाहिए;/ रिकर्सिव गणना बाल नोड्स /स्ट्रिंग डंप (int = 0);/ टैब के साथ पेड़ के रूप में डंप * /};
जोड़ा लेखक Dmitry Ponyatov, स्रोत
लेकिन आप eval() शरीर में सही है: जब आप घोंसला की तरह बेवकूफ eval करने की कोशिश [0]/* lchild */= घोंसला [0] -> eval() घोंसला [0] वस्तु की स्मृति रिसाव मिलना बहुत आसान है यह eval है। मैं वास्तव में कुछ अभिव्यक्तियों के बीच साझा चर के मामले में इसे ट्रैक करने के बारे में नहीं जानता, लेकिन पत्ती संख्याओं को हटाया जा सकता है।
जोड़ा लेखक Dmitry Ponyatov, स्रोत
मैं भूल गया? स्ट्रिंग वैल? एएसटी में नोड के लिए लेबल के रूप में
जोड़ा लेखक Dmitry Ponyatov, स्रोत

स्ट्रिंग टोकेनाइज़र + एलएल (1) पार्सर आपको एक अभिव्यक्ति वृक्ष देगा ... बहुरूपता के तरीके में "मूल्यांकन (ए, बी)" फ़ंक्शन के साथ एक अमूर्त अंकगणितीय वर्ग शामिल हो सकता है, जिसमें शामिल प्रत्येक ऑपरेटरों के लिए ओवरराइड किया गया है (अतिरिक्त, घटाव इत्यादि) उचित मूल्य वापस करने के लिए, और पेड़ में इंटीग्रर्स और अंकगणितीय ऑपरेटरों शामिल हैं, जिनका मूल्यांकन एक पोस्ट (?) - पेड़ के आदेश ट्रैवर्सल द्वारा किया जा सकता है।

0
जोड़ा

यह पार्सिंग/कंपाइलर सिद्धांत में आता है, जो एक खरगोश छेद है ... ड्रैगन बुक कंपाइलर निर्माण के लिए मानक पाठ है, और इसे चरम पर ले जाता है। इस विशेष मामले में, आप बुनियादी के लिए एक संदर्भ-मुक्त व्याकरण बनाना चाहते हैं अंकगणित, फिर उस व्याकरण का उपयोग अमूर्त वाक्यविन्यास पेड़ को पार्स करने के लिए करें। फिर आप पेड़ पर फिर से घुमा सकते हैं, इसे नीचे से कम कर सकते हैं (इस बिंदु पर आप पेड़ को कम करने के लिए पॉलीमोर्फिज्म/फ़ंक्शन पॉइंटर्स/स्विच कथन लागू करेंगे)।

मैंने इन नोट्स को संकलक में अविश्वसनीय रूप से सहायक पाया है और पार्सिंग सिद्धांत।

0
जोड़ा
मूल प्रश्न के लिए यहां एक न्यूनतम सीएफजी है: एस -> एन एन -> 2 एन -> एन ओ एन -> (एन) ओ -> - एन
जोड़ा लेखक ReaperUnreal, स्रोत

पुन: जस्टिन

मुझे लगता है कि पेड़ इस तरह कुछ दिखता है:

  +
/\
2  ( )
    |
    2

असल में, आपके पास "eval" नोड होगा, जो कि इसके नीचे के पेड़ का मूल्यांकन करता है। इसके बाद इसे अनुकूलित करने के लिए अनुकूलित किया जाएगा:

  +
/\
2   2

इस मामले में माता-पिता की आवश्यकता नहीं होती है और कुछ भी नहीं जोड़ते हैं। वे तार्किक रूप से कुछ भी नहीं जोड़ते हैं, इसलिए वे अभी चले जाएंगे।

0
जोड़ा

मैं जवाब नहीं दूंगा, लेकिन ए   मानक खराब समाधान में उपयोग शामिल है   एक स्विच या केस स्टेटमेंट (या बस   अच्छी पुरानी शैली वाली कैस्केड-आईएफएस)। ए   थोड़ा बेहतर समाधान शामिल है   फ़ंक्शन पॉइंटर्स की एक तालिका का उपयोग करके,   और शायद सबसे अच्छा समाधान   polymorphism का उपयोग शामिल है।

बाद स्विच करने के लिए (अनुभवहीन बाइट कोड दुभाषियों) बहुरूपता (जैसे अनुभवहीन स्मालटाक metacircular दुभाषिए) संकेत दिए गए कार्य करने के लिए (, सी ++ अनुभवहीन तुतलाना कार्यान्वयन, पिरोया कोड), और फिर - पिछले बीस दुभाषिए में विकास के वर्षों के अन्य रास्ते पर जा रहा के रूप में देखा जा सकता है JITs और इतने पर करने के लिए - जो या तो बहुत बड़ी कक्षाओं की आवश्यकता होती है, या (अकेले बहुरूपी भाषाओं में) डबल-प्रेषण है, जो एक प्रकार मामले को बहुरूपता कम कर देता है, और आप चरण एक में वापस आ गए हैं। 'सर्वश्रेष्ठ' किस परिभाषा प्रयोग में यहाँ है?

सरल सामग्री के लिए एक पॉलिमॉर्फिक समाधान ठीक है - यहां मैंने पहले बनाया है </ए>, लेकिन स्टैकटाइम के कंपाइलर का स्टैक और बाइटकोड/स्विच या शोषण आमतौर पर बेहतर होता है यदि आप कुछ हज़ार डेटा पॉइंट्स के साथ फ़ंक्शन प्लॉट करते हैं।

0
जोड़ा

मुझे लगता है कि समस्या यह है कि हमें perentheses पार्स करने की जरूरत है, और फिर भी वे एक बाइनरी ऑपरेटर नहीं हैं? क्या हमें एक टोकन के रूप में (2) लेना चाहिए, जो 2 का मूल्यांकन करता है?

माता-पिता को अभिव्यक्ति के पेड़ में दिखाने की ज़रूरत नहीं है, लेकिन वे इसके आकार को प्रभावित करते हैं। उदा।, पेड़ (1 + 2) +3 के लिए पेड़ 1+ (2 + 3) से अलग है:

    +
  /\
  +   3
/\
1   2

बनाम

    +
  /\
  1   +
    /\
    2   3

कोष्ठक पार्सर के लिए "संकेत" होते हैं (उदाहरण के लिए, प्रति सुपरजो 30, "रिकर्सिवली अवरोही")

0
जोड़ा

मुझे लगता है कि प्रश्न एक पार्सर लिखने के बारे में है, मूल्यांकनकर्ता नहीं। या फिर, स्ट्रिंग से अभिव्यक्ति वृक्ष कैसे बनाएं।

केस स्टेटमेंट जो बेस क्लास लौटाते हैं, बिल्कुल गिनती नहीं करते हैं।

"पॉलिमॉर्फिक" समाधान की मूल संरचना (जो कहने का एक और तरीका है, मुझे इसकी परवाह नहीं है कि आप इसे किस चीज के साथ बनाते हैं, मैं बस इसे कम से कम कोड की पुनः लिखने के साथ विस्तारित करना चाहता हूं) एक ऑब्जेक्ट पदानुक्रम को deserializing है ज्ञात प्रकारों के एक (गतिशील) सेट के साथ धारा।

पॉलिमॉर्फिक समाधान के कार्यान्वयन का क्रूक्स एक पैटर्न मैचर से अभिव्यक्ति ऑब्जेक्ट बनाने का एक तरीका है, संभवतः रिकर्सिव। यानी, एक ऑब्जेक्ट फैक्ट्री में एक बीएनएफ या इसी तरह के वाक्यविन्यास को मानचित्र करें।

0
जोड़ा

चूंकि लोग पहले उल्लेख कर रहे हैं, जब आप अभिव्यक्ति पेड़ का उपयोग करते हैं तो माता-पिता आवश्यक नहीं होते हैं। जब आप अभिव्यक्ति वृक्ष को देख रहे हों तो संचालन का क्रम छोटा और स्पष्ट हो जाता है। माता-पिता पार्सर को संकेत देते हैं।

जबकि स्वीकृत उत्तर समस्या का एक आधा का समाधान है, दूसरा आधा - वास्तव में अभिव्यक्ति को पार्स करना - अभी भी अनसुलझा है। आम तौर पर, इन प्रकार की समस्याओं को एक रिकर्सिव descent parser का उपयोग करके हल किया जा सकता है। इस तरह के एक पार्सर को लिखना अक्सर एक मजेदार व्यायाम होता है, लेकिन अधिकांश भाषा पार्सिंग के लिए आधुनिक टूल आपके लिए दूर होंगे ।

यदि आप अपनी स्ट्रिंग में फ़्लोटिंग पॉइंट नंबरों को अनुमति देते हैं तो पार्सर भी महत्वपूर्ण कठिन होता है। मुझे सी में फ्लोटिंग पॉइंट नंबर स्वीकार करने के लिए एक डीएफए बनाना था - यह एक बहुत ही दर्दनाक और विस्तृत कार्य था। याद रखें, वैध फ़्लोटिंग पॉइंट्स में शामिल हैं: 10, 10., 10.123, 9.876e-5, 1.0f, .025, आदि। मुझे लगता है कि साक्षात्कार में (सरलता और अल्पसंख्यक के पक्ष में) कुछ विवाद किया गया था।

0
जोड़ा