मैं अपने शंटिंग-यार्ड एल्गोरिदम को कैसे संशोधित कर सकता हूं ताकि यह यूनरी ऑपरेटरों को स्वीकार कर सके?

Question

मैं कक्षा के लिए जावास्क्रिप्ट में शंटिंग-यार्ड एल्गोरिदम लागू करने पर काम कर रहा हूं।

var userInput = prompt("Enter in a mathematical expression:"); 
var postFix = InfixToPostfix(userInput); 
var result = EvaluateExpression(postFix); 

document.write("Infix: " + userInput + "<br/>"); 
document.write("Postfix (RPN): " + postFix + "<br/>"); 
document.write("Result: " + result + "<br/>"); 


function EvaluateExpression(expression) 
{ 
    var tokens = expression.split(/([0-9]+|[*+-\/()])/); 
    var evalStack = []; 

    while (tokens.length != 0) 
    { 
     var currentToken = tokens.shift(); 

     if (isNumber(currentToken)) 
     { 
      evalStack.push(currentToken); 
     } 
     else if (isOperator(currentToken)) 
     { 
      var operand1 = evalStack.pop(); 
      var operand2 = evalStack.pop(); 

      var result = PerformOperation(parseInt(operand1), parseInt(operand2), currentToken); 
      evalStack.push(result); 
     } 
    } 
    return evalStack.pop(); 
} 

function PerformOperation(operand1, operand2, operator) 
{ 
    switch(operator) 
    { 
     case '+': 
      return operand1 + operand2; 
     case '-': 
      return operand1 - operand2; 
     case '*': 
      return operand1 * operand2; 
     case '/': 
      return operand1/operand2; 
     default: 
      return; 
    } 

} 

function InfixToPostfix(expression) 
{ 
    var tokens = expression.split(/([0-9]+|[*+-\/()])/); 
    var outputQueue = []; 
    var operatorStack = []; 

    while (tokens.length != 0) 
    { 
     var currentToken = tokens.shift(); 

     if (isNumber(currentToken)) 
     { 
      outputQueue.push(currentToken); 
     } 
     else if (isOperator(currentToken)) 
     { 
      while ((getAssociativity(currentToken) == 'left' && 
        getPrecedence(currentToken) <= getPrecedence(operatorStack[operatorStack.length-1])) || 
        (getAssociativity(currentToken) == 'right' && 
        getPrecedence(currentToken) < getPrecedence(operatorStack[operatorStack.length-1]))) 
      { 
       outputQueue.push(operatorStack.pop()) 
      } 

      operatorStack.push(currentToken); 

     } 
     else if (currentToken == '(') 
     { 
       operatorStack.push(currentToken); 
     } 
     else if (currentToken == ')') 
     { 
      while (operatorStack[operatorStack.length-1] != '(') 
      { 
       if (operatorStack.length == 0) 
        throw("Parenthesis balancing error! Shame on you!"); 

       outputQueue.push(operatorStack.pop()); 
      } 
      operatorStack.pop();   
     } 
    } 

    while (operatorStack.length != 0) 
    { 
     if (!operatorStack[operatorStack.length-1].match(/([()])/)) 
      outputQueue.push(operatorStack.pop()); 
     else 
      throw("Parenthesis balancing error! Shame on you!");   
    } 

    return outputQueue.join(" "); 
}  


function isOperator(token) 
{ 
    if (!token.match(/([*+-\/])/)) 
     return false; 
    else 
     return true; 
} 


function isNumber(token) 
{ 
    if (!token.match(/([0-9]+)/)) 
     return false; 
    else 
     return true; 
} 


function getPrecedence(token) 
{ 
    switch (token) 
    { 
     case '^': 
      return 9; 
     case '*':   
     case '/': 
     case '%': 
      return 8; 
     case '+': 
     case '-': 
      return 6; 
     default: 
      return -1; 
    } 
} 

function getAssociativity(token) 
{ 
    switch(token) 
    { 
     case '+': 
     case '-': 
     case '*': 
     case '/': 
      return 'left'; 
     case '^': 
      return 'right'; 
    } 

} 

यह ठीक अब तक काम करता है:

यहाँ मेरा काम अब तक है।

((5 + 3) * 8)

यह होगा उत्पादन:

इन्फ़िक्स: ((5 + 3) * 8)
पोस्टफिक्स अगर मैं इसे देने के (आरपीएन): 5 3 + 8 *
परिणाम: 64

हालांकि, मैं एकल operato को लागू करने के साथ संघर्ष कर रहा हूँ रु इसलिए मैं कुछ ऐसा कर सकता है:

((-5 +3) * 8)

सबसे अच्छा तरीका क्या होगा एकल ऑपरेटरों (निषेध, आदि) लागू करने के लिए? साथ ही, क्या किसी के पास फ्लोटिंग पॉइंट नंबरों को संभालने के लिए कोई सुझाव है?

एक आखिरी बात, अगर कोई मुझे जावास्क्रिप्ट में अजीब कुछ भी देखता है तो मुझे बताएं। यह मेरा पहला जावास्क्रिप्ट प्रोग्राम है और मैं अभी तक इसका उपयोग नहीं कर रहा हूं।

Answer 1

मेरा सुझाव यह है। एक अंकगणितीय ऑपरेटर के रूप में '-' संभाल नहीं है। इसे 'साइन' ऑपरेटर के रूप में पेश करें। या इसका इलाज करें जैसे कि यह पूरे ऑपरेंड का हिस्सा है (यानी इसका संकेत)। मेरा मतलब यह है कि हर बार जब आप '-' का सामना करते हैं, तो आपको केवल 1 के बाद ऑपरेंड को गुणा करना होगा, फिर अगले टोकन को पढ़ने के लिए आगे बढ़ें। :) मुझे आशा है कि वह मदद करेंगे। बस एक साधारण विचार ...

Answer 2

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

यह वास्तव में मदद करता है अगर आप "यूनरी माइनस" को इंगित करने के लिए किसी अन्य चरित्र का उपयोग करते हैं।

Answer 3

सबसे आसान बात यह है कि isNumber मैच /-?[0-9]+(\.[0-9]+)?/, फ़्लोटिंग पॉइंट्स और नकारात्मक संख्या दोनों को संभालने के लिए सबसे आसान बात होगी।

तुम सच में एकल ऑपरेटरों (जैसे कि, parenthesized अभिव्यक्ति की एकल निषेध) को संभालने की ज़रूरत है, तो आप के लिए:

• उन्हें सही-साहचर्य करें।
• किसी भी इंफिक्स ऑपरेटरों की तुलना में उन्हें उच्च प्राथमिकता बनाएं।
• EvaluateExpression में उन्हें अलग से संभालें (एक अलग PerformUnaryExpression फ़ंक्शन बनाएं जो केवल एक ऑपरेंड लेता है)।
• किसी प्रकार के राज्य का ट्रैक रखकर InfixToPostfix में यूनरी और बाइनरी माइनस के बीच अंतर करें। देखें कि '-' इस Python example में '-u' में बदल गया है।

मैंने another SO question पर यूनरी माइनस को संभालने का एक और गहन स्पष्टीकरण लिखा।

Answer 4

मेरी जावा कार्यान्वयन में मैं अगले तरीके से किया था:

expression = expression.replace(" ", "").replace("(-", "(0-") 
       .replace(",-", ",0-"); 
     if (expression.charAt(0) == '-') { 
      expression = "0" + expression; 
     } 

Answer 5

मैं एकल ऑपरेटरों को संशोधित करके इस समस्या का समाधान कर सकता है ('+' और '-') उन्हें द्विआधारी लोगों से अलग करने के।

उदाहरण के लिए, मैंने यूनरी माइनस 'एम' और यूनरी प्लस '+' कहा, जिससे उन्हें सही-आक्रामक बना दिया गया और उनकी प्राथमिकता एक्सपोनेंट ऑपरेटर ('^') के बराबर होती है।

यह पता लगाने के लिए कि ऑपरेटर एकजुट है या नहीं, मुझे बस यह जांचना पड़ा कि ऑपरेटर ऑपरेटर या ओपनिंग ब्रैकेट था या नहीं।

 if (isOperator(*token)) 
     { 
      if (!isdigit(*(token - 1)) && *(token - 1) != ')') // Unary check 
      { 
       if (*token == '+') 
        *token = 'p';  // To distinguish from the binary ones 
       else if (*token == '-') 
        *token = 'm'; 
       else 
        throw; 
      } 

      short prec = precedence(*token); 
      bool rightAssociative = (*token == '^' || *token == 'm' || *token == 'p'); 

      if (!operators.empty()) 
      { 
       while (prec < precedence(operators.top()) || (prec == precedence(operators.top()) && !rightAssociative)) 
       { 
        rpn += operators.top(); 
        operators.pop(); 

        if (operators.empty()) 
         break; 
       } 
      } 
      operators.push(*token); 
     } 

यहाँ ऑपरेटरों एक ढेर है और टोकन इन्फ़िक्स अभिव्यक्ति स्ट्रिंग

(यह सिर्फ ऑपरेटर से निपटने हिस्सा)