एक शंटिंग यार्ड एल्गोरिदम

Question

के साथ समस्याएं मैंने जावा में एक शंटिंग यार्ड एल्गोरिदम सफलतापूर्वक कार्यान्वित किया है। एल्गोरिदम स्वयं सरल था हालांकि मुझे टोकनेज़र के साथ परेशानी हो रही है। वर्तमान में एल्गोरिदम एक चीज को छोड़कर मैं जो कुछ भी चाहता हूं उसके साथ काम करता है। मैं घटाव के बीच का अंतर कैसे बता सकता हूँ (-) और नकारात्मक (-)

जैसे 4-3 घटाव है लेकिन -4 + 3

अब मैं जानता पता लगाने के लिए जब यह होना चाहिए नकारात्मक है एक नकारात्मक और जब यह एक शून्य हो, लेकिन जहां एल्गोरिदम में इसे रखा जाना चाहिए क्योंकि यदि आप इसे किसी फ़ंक्शन की तरह उपयोग करते हैं तो यह हमेशा उदाहरण के लिए काम नहीं करेगा

3 + 4 * 2/- (1 - 5)^2^3

जब 1-5 बन जाता है -4 यह वर्ग बनने से पहले 4 हो जाएगा और

जैसे 3 + 4 * 2/cos (1 - 5)^2^3, आप बराबरी और cubing

से पहले कोज्या ले जाएगा लेकिन असली गणित में आप एक साथ नहीं होगा - क्योंकि जो अपने वास्तव में कह रहा है 3 + 4 * 2/- ((1 - 5)^2^3) सही मूल्य

Answer 1

this question के उत्तर सहायक हो सकते हैं।

विशेष रूप से, उन उत्तरों में से एक सी में solution संदर्भित करता है जो यूनरी माइनस को संभालता है।

असल में, आपको कम से कम साइन इन स्थितियों की उपस्थिति के आधार पर एक यूनरी माइनस को पहचानना होगा जहां एक बाइनरी ऑपरेटर नहीं हो सकता है, और इसके लिए एक अलग टोकन बनाते हैं, क्योंकि इसकी अलग-अलग प्राथमिकता होती है।

डिजस्ट्रा का original paper स्पष्ट रूप से यह स्पष्ट नहीं करता कि उसने इसका सामना कैसे किया, लेकिन यूनरी माइनस को एक अलग ऑपरेटर के रूप में सूचीबद्ध किया गया था।

Answer 2

ऐसा लगता है कि आप एक लेक्स-पर-पार्स स्टाइल पार्सर कर रहे हैं, जहां आपको लेजर में एक साधारण राज्य मशीन की आवश्यकता होगी ताकि यूनरी और बाइनरी माइनस के लिए अलग टोकन प्राप्त हो सकें। यदि आप एक DEFAULT राज्य है जहां - चरित्र पर विचार करेंगे UNARY_MINUS होने के लिए चाहते हैं (एक पेग पार्सर में, यह नहीं कुछ आप के बारे में चिंता करने की ज़रूरत है।)

JavaCC में,। जब आपने प्राथमिक अभिव्यक्ति के अंत (या तो एक बंद करने वाला अभिभावक, या एक पूर्णांक, आपके द्वारा दिए गए उदाहरणों के आधार पर) को टोकननाइज्ड किया, तो आप INFIX स्थिति पर स्विच करेंगे जहां -INFIX_MINUS माना जाएगा। एक बार जब आप किसी भी इंफिक्स ऑपरेटर का सामना कर चुके हैं, तो आप DEFAULT स्थिति पर वापस आ जाएंगे।

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

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

जब मूल्यांकन करने का समय आता है, तो आपको यूनरी ऑपरेटरों को थोड़ा अलग तरीके से संभालना होगा, क्योंकि आपको केवल दो की बजाय स्टैक से एक नंबर पॉप करना होगा। आपके कार्यान्वयन की तरह दिखने के आधार पर, सूची के माध्यम से जाना आसान हो सकता है और की प्रत्येक घटना को [-1, "*"] से बदलना आसान हो सकता है।

यदि आप पाइथन का पालन कर सकते हैं, तो आप जिस उदाहरण के बारे में बात कर रहे हैं, उसके बारे में आप जो कुछ भी बात कर रहे हैं, उसे देखने में सक्षम होना चाहिए। मुझे कोड को सी संस्करण से पढ़ने के लिए थोड़ा आसान लगता है जिसे किसी और ने बताया है। इसके अलावा, यदि आप उत्सुक हैं, तो मैंने थोड़ी देर पहले शंटिंग-यार्ड in Ruby का उपयोग करने के बारे में थोड़ा सा लिख ​​लिया था, लेकिन मैंने यूनरी ऑपरेटरों को एक अलग nonterminal के रूप में संभाला, इसलिए वे नहीं दिखाए जाते हैं।

Answer 3

अपने lexer में, आप इस छद्म तर्क को लागू कर सकते हैं:

if (symbol == '-') { 
    if (previousToken is a number 
    OR previousToken is an identifier 
    OR previousToken is a function) { 
     currentToken = SUBTRACT; 
    } else { 
     currentToken = NEGATION; 
    } 
} 

आप एक पूर्वता गुणा और भाग की तुलना में अधिक है करने के लिए निषेध सेट कर सकते हैं, लेकिन घातांक से कम है। आप इसे सही सहयोगी (बस '^' की तरह) भी सेट कर सकते हैं। फिर आपको विकिपीडिया के पृष्ठ पर वर्णित एल्गोरिदम में प्राथमिकता और सहयोगीता को एकीकृत करने की आवश्यकता है।

टोकन है एक ऑपरेटर, O1, तो: जबकि वहाँ एक ऑपरेटर टोकन, O2, ढेर के शीर्ष पर है, और या तो O1 बाएं साहचर्य है और इसके पूर्वता से कम या बराबर है o2, या o1 की ओ 2 की तुलना में कम प्राथमिकता, स्टैक से पॉप ओ 2, कतार पर; ढेर पर ओ 1 धक्का।

if (token is operator negate) { 
    operand = pop; 
    push operand * -1; 
} 

उदाहरण परियोजना:

} else if (nextToken instanceof Operator) { 
    final Operator o1 = (Operator) nextToken; 

    while (!stack.isEmpty() && stack.peek() instanceof Operator) { 
     final Operator o2 = (Operator) stack.peek(); 

     if ((o1.associativity == Associativity.LEFT && o1.precedence <= o2.precedence) 
     || (o1.associativity == Associativity.RIGHT && o1.precedence < o2.precedence)) { 
      popStackTopToOutput(); 
     } else { 
      break; 
     } 
    } 

    stack.push(nextToken); 
} 

ऑस्टिन टेलर बहुत सही है कि आप केवल एक एकल ऑपरेटर के लिए एक नंबर बंद पॉप की जरूरत है:

मैं इस इसी कोड को लागू करने समाप्त हो गया:

https://github.com/Digipom/Calculator-for-Android/

अतिरिक्त पठन:

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

http://sankuru.biz/blog/1-parsing-object-oriented-expressions-with-dijkstras-shunting-yard-algorithm

Answer 4

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

तो आप परिभाषित कर सकते हैं - सामान्य चरित्र के रूप में, जिसका अर्थ यह नहीं माना जाएगा संख्या के लिए एक संकेत।उदाहरण के लिए, यदि आपके पास अभिव्यक्ति 2-3 है, तो आपके पास [2, -, 3] होगा, लेकिन यदि आपने इसे सामान्य के रूप में निर्दिष्ट नहीं किया है, तो यह [2, -3]