उपसर्ग नोटेशन

Question

में एक अभिव्यक्ति का मूल्यांकन कैसे करें मैं एक सूची का मूल्यांकन करने की कोशिश कर रहा हूं जो उपसर्ग नोटेशन में अभिव्यक्ति का प्रतिनिधित्व करता है। यहां इस तरह के एक सूची का एक उदाहरण है:

[+, [sin, 3], [- 10 5]] 

सबसे अच्छा तरीका क्या सूची

Answer 1

यदि आप उपसर्ग के बजाय पोस्टफिक्स का उपयोग करते हैं तो यह आसान होगा। Reverse Polish Notation (RPN) देखें। आरपीएन में एक अभिव्यक्ति को देखते हुए, केवल एक स्टैक का उपयोग करके इसका मूल्यांकन करना आसान है।

लेकिन जब से तुम एक तरह से करने के लिए कहा प्रत्यावर्तन और ढेर का उपयोग किए बिना उपसर्ग भाव का मूल्यांकन करने के लिए (एक संभवतः सरल तरीके के लिए, संपादित करें देखें: नीचे), यहाँ एक तरीका है:

हम इस दो का उपयोग कर सकते ढेर।

एक ढेर (इसे मूल्यांकन कहते हैं) ऑपरेटरों (जैसे +, पाप इत्यादि) और ऑपरेंड (जैसे 3,4 इत्यादि) और अन्य स्टैक (इसे कॉल करें) रखता है, जो बाएं ऑपरेटरों की संख्या का एक गुच्छा रखता है देखा + ऑपरेटर की संख्या ऑपरेटर की उम्मीद है।

जब भी आप एक ऑपरेटर देखते हैं, तो आप ऑपरेटर को मूल्यांकन स्टैक पर दबाते हैं और संबंधित टुपल को काउंटर स्टैक पर दबाते हैं।

जब भी आप एक ऑपरेंड (जैसे 3,5 आदि) देखते हैं, तो आप गणना स्टैक के शीर्ष टुपल की जांच करते हैं और उस टुपल में दिखाई देने वाले ऑपरेंड की संख्या को कम करते हैं।

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

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

यदि ऑपरेंड गिनती शून्य नहीं बनती है, तो आप इनपुट में अगले टोकन के साथ जारी रखते हैं।

उदाहरण के लिए मान लीजिए कि आप का मूल्यांकन करने के लिए किया था + 3 + 4/20 4

ढेर की तरह दिखाई देगा (बाएं ढेर के शीर्ष है)

Count     Evaluation     Input 
                + 3 + 4/20 4 

(2,2)     +       3 + 4/20 4 

(2,1)     3 +       + 4/20 4 

(2,2) (2,1)    + 3 +       4/20 4 

(2,1) (2,1)    4 + 3 +       /20 4 

(2,2) (2,1) (2,1)  /4 + 3 +       20 4 

(2,1) (2,1) (2,1)  20/4 + 3 +       4 

(2,0) (2,1) (2,1)  4 8/4 + 3 +     

Since it has become zero, you pop off two operands, the operator/
and evaluate and push back 5. You pop off (2,0) from the Count stack. 

(2,1) (2,1)    5 4 + 3 + 

Pushing back you decrement the current Count stack top. 

(2,0) (2,1)    5 4 + 3 + 

Since it has become zero, you pop off 5,4 and + and evaluate and push back 9. 
Also pop off (2,0) from the count stack. 

(2,0)       9 3 + 

           12 

संपादित करें:

एक दोस्त ने कई स्टैक्स के बिना ऐसा करने का एक तरीका सुझाया:

अंत से शुरू करें, पहले ऑपरेटर पर जाएं। उसके दाईं ओर टोकन ऑपरेंड होंगे। मूल्यांकन करें और फिर से करें। दो ढेर के साथ ऐसा करने से कहीं ज्यादा सरल लगता है। हम इनपुट के प्रतिनिधित्व के लिए एक दोगुनी लिंक्ड सूची का उपयोग कर सकते हैं जिसे हम प्रसंस्करण के दौरान बदलते हैं। जब आप मूल्यांकन करते हैं, तो आप नोड्स हटाते हैं, और फिर परिणाम डालें। या आप शायद एक ढेर का उपयोग कर सकते हैं।

Answer 2

KISS का मूल्य का मूल्यांकन करने, एक पोस्टफ़िक्स अभिव्यक्ति के रूप में रिवर्स में मूल्यांकन करते हैं।

Answer 3

जिस तरह से मैं इसे देखता हूं आपके पास दो विकल्प हैं। या तो दायें या दाएं से बाएं (जैसा ऊपर उल्लिखित पाउल है) पर जाएं। दोनों विधियों को नीचे दिए गए कोड में प्रदर्शित किया गया है।

public static class Evaluator 
{ 
    public static double EvaluatePrefix(string expr) 
    { 
     if (expr == null) throw new ArgumentNullException("expr"); 

     var symbols = expr.Split(','); 
     var stack = new Stack<Symbol>(); 

     foreach (var symbol in symbols) 
     { 
      double operand; 
      if (!double.TryParse(symbol, out operand)) //encountered an operator 
      { 
       stack.Push(new Operator(symbol)); 
       continue; 
      } 

      //encountered an operand 
      if (stack.Count == 0) throw new ArgumentException("Invalid expression"); 

      double right = operand; 
      var leftOperand = stack.Peek() as Operand; 
      while (leftOperand != null) 
      { 
       stack.Pop(); //pop left operand that we just peeked 
       if (stack.Count == 0) throw new ArgumentException("Invalid expression"); 
       double result = Calculate(leftOperand.Value, right, ((Operator)stack.Pop()).OperatorChar); 

       right = result; 
       leftOperand = (stack.Count == 0) ? null : stack.Peek() as Operand; 
      } 
      stack.Push(new Operand(right)); 
     } 

     if (stack.Count != 1) throw new ArgumentException("Invalid expression"); 
     var operandSymbol = stack.Pop() as Operand; 
     if (operandSymbol == null) throw new ArgumentException("Invalid expression"); 
     return operandSymbol.Value; 
    } 

    public static double EvaluatePrefixAlternative(string expr) 
    { 
     if (expr == null) throw new ArgumentNullException("expr"); 

     double d; 
     var stack = new Stack<Symbol>(
      expr.Split(',').Select(s => double.TryParse(s, out d) ? (Symbol) new Operand(d) : new Operator(s))); 

     var operands = new Stack<double>(); 
     while (stack.Count > 0) 
     { 
      var symbol = stack.Pop(); 
      var operand = symbol as Operand; 
      if (operand != null) 
      { 
       operands.Push(operand.Value); 
      } 
      else 
      { 
       if (operands.Count < 2) throw new ArgumentNullException("expr"); 
       operands.Push(Calculate(operands.Pop(), operands.Pop(), ((Operator) symbol).OperatorChar)); 
      } 
     } 

     if (operands.Count != 1) throw new ArgumentNullException("expr"); 
     return operands.Pop(); 
    } 

    private static double Calculate(double left, double right, char op) 
    { 
     switch (op) 
     { 
      case '*': 
       return (left * right); 
      case '+': 
       return (left + right); 
      case '-': 
       return (left - right); 
      case '/': 
       return (left/right); //May divide by zero ! 
      default: 
       throw new ArgumentException(string.Format("Unrecognized operand {0}", op), "op"); 
     } 
    } 

    abstract class Symbol 
    { 
    } 

    private class Operand : Symbol 
    { 
     public double Value { get; private set; } 

     public Operand(double value) 
     { 
      Value = value; 
     } 
    } 

    private class Operator : Symbol 
    { 
     public char OperatorChar { get; private set; } 

     public Operator(string symbol) 
     { 
      if (symbol.Trim().Length != 1) throw new ArgumentException("Invalid expression"); 
      OperatorChar = symbol[0]; 
     } 
    } 
} 

कुछ परीक्षण:

[TestMethod] 
public void TestPrefixEvaluation() 
{ 
    Assert.AreEqual(5, Evaluator.EvaluatePrefix("-,*,/,15,-,7,+,1,1,3,+,2,+,1,1")); 
    Assert.AreEqual(4, Evaluator.EvaluatePrefix("/,-,*,2,5,*,1,2,-,11,9")); 
    Assert.AreEqual(5, Evaluator.EvaluatePrefixAlternative("-,*,/,15,-,7,+,1,1,3,+,2,+,1,1")); 
    Assert.AreEqual(4, Evaluator.EvaluatePrefixAlternative("/,-,*,2,5,*,1,2,-,11,9")); 
}