सी # में पार्सिंग पासा अभिव्यक्ति (उदाहरण के लिए 3 डी 6 + 5): कहां से शुरू करें?

Question

तो मैं सी # में "पासा अभिव्यक्ति" का विश्लेषण और मूल्यांकन करने में सक्षम होना चाहता हूं। एक पासा अभिव्यक्ति को इस तरह परिभाषित किया गया है:

<expr> := <expr> + <expr> 
      | <expr> - <expr> 
      | [<number>]d(<number>|%) 
      | <number> 
<number> := positive integer 

तो उदा। d6+20-2d3 की अनुमति दी जाएगी, और जैसा कि

rand.Next(1, 7) + 20 - (rand.Next(1, 4) + rand.Next(1, 4)) 

इसके अलावा d%d100 के बराबर होना चाहिए मूल्यांकन करना चाहिए।

मैं जानता हूँ कि मैं एक साथ कुछ समाधान हैक कर सकता है, लेकिन मैं यह भी जानता हूँ कि यह एक बहुत ही विशिष्ट कंप्यूटर विज्ञान प्रकार समस्या की तरह लगता है, इसलिए कुछ सुपर सुरुचिपूर्ण समाधान मैं इस पर गौर करना चाहिए होना चाहिए।

मैं अपने पार्स का परिणाम चाहते हैं तो इन क्षमताओं:

• मैं अभिव्यक्ति का एक सामान्यीकृत रूप उत्पादन में सक्षम होना चाहिए; मैं पहले पासा सोच रहा हूं, पासा आकार द्वारा क्रमबद्ध, और हमेशा एक उपसर्ग के साथ। तो उदा। उपरोक्त नमूना 1d6-2d3+20 बन जाएगा। इसके अलावा d% के किसी भी उदाहरण सामान्यीकृत रूप में d100 बन जाएगा।
• मैं, पर-इच्छा की अभिव्यक्ति का मूल्यांकन करने के विभिन्न यादृच्छिक संख्या हर बार रोलिंग सक्षम होना चाहिए।
• मैं, इसलिए जैसे पासा रोल अधिकतम के सभी के साथ अभिव्यक्ति का मूल्यांकन करने में सक्षम होना चाहिए उपरोक्त नमूना (निर्धारक रूप से) 1*6+20+2*3 = 32 देगा।

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

मेरे शुरुआती विचार रिकर्सन, सूचियों और शायद कुछ LINQ की ओर रुख करते हैं, लेकिन फिर भी, अगर मैंने कुछ लोगों के बारे में कुछ संकेत दिए बिना कोशिश की, तो मुझे यकीन है कि यह एक अजीब गड़बड़ हो जाएगा।

एक और रणनीति जो काम कर सकती है, कुछ प्रारंभिक रेगेक्स-आधारित स्ट्रिंग-प्रतिस्थापन होगा जो पासा अभिव्यक्ति को rand.Next कॉलों में बदलने के लिए, और फिर ऑन-द-फ्लाई मूल्यांकन या संकलन ... क्या यह वास्तव में काम करेगा? मैं हर बार एक नया rand ऑब्जेक्ट बनाने से कैसे बच सकता हूं?

Answer 1

यहाँ है कि मैं क्या अंततः के साथ आया है:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text.RegularExpressions; 

public enum DiceExpressionOptions 
{ 
    None, 
    SimplifyStringValue 
} 
public class DiceExpression 
{ 
    /* <expr> := <expr> + <expr> 
    *   | <expr> - <expr> 
    *   | [<number>]d(<number>|%) 
    *   | <number> 
    * <number> := positive integer 
    * */ 
    private static readonly Regex numberToken = new Regex("^[0-9]+$"); 
    private static readonly Regex diceRollToken = new Regex("^([0-9]*)d([0-9]+|%)$"); 

    public static readonly DiceExpression Zero = new DiceExpression("0"); 

    private List<KeyValuePair<int, IDiceExpressionNode>> nodes = new List<KeyValuePair<int, IDiceExpressionNode>>(); 

    public DiceExpression(string expression) 
     : this(expression, DiceExpressionOptions.None) 
    { } 
    public DiceExpression(string expression, DiceExpressionOptions options) 
    { 
     // A well-formed dice expression's tokens will be either +, -, an integer, or XdY. 
     var tokens = expression.Replace("+", " + ").Replace("-", " - ").Split(' ', StringSplitOptions.RemoveEmptyEntries); 

     // Blank dice expressions end up being DiceExpression.Zero. 
     if (!tokens.Any()) 
     { 
      tokens = new[] { "0" }; 
     } 

     // Since we parse tokens in operator-then-operand pairs, make sure the first token is an operand. 
     if (tokens[0] != "+" && tokens[0] != "-") 
     { 
      tokens = (new[] { "+" }).Concat(tokens).ToArray(); 
     } 

     // This is a precondition for the below parsing loop to make any sense. 
     if (tokens.Length % 2 != 0) 
     { 
      throw new ArgumentException("The given dice expression was not in an expected format: even after normalization, it contained an odd number of tokens."); 
     } 

     // Parse operator-then-operand pairs into this.nodes. 
     for (int tokenIndex = 0; tokenIndex < tokens.Length; tokenIndex += 2) 
     { 
      var token = tokens[tokenIndex]; 
      var nextToken = tokens[tokenIndex + 1]; 

      if (token != "+" && token != "-") 
      { 
       throw new ArgumentException("The given dice expression was not in an expected format."); 
      } 
      int multiplier = token == "+" ? +1 : -1; 

      if (DiceExpression.numberToken.IsMatch(nextToken)) 
      { 
       this.nodes.Add(new KeyValuePair<int, IDiceExpressionNode>(multiplier, new NumberNode(int.Parse(nextToken)))); 
      } 
      else if (DiceExpression.diceRollToken.IsMatch(nextToken)) 
      { 
       var match = DiceExpression.diceRollToken.Match(nextToken); 
       int numberOfDice = match.Groups[1].Value == string.Empty ? 1 : int.Parse(match.Groups[1].Value); 
       int diceType = match.Groups[2].Value == "%" ? 100 : int.Parse(match.Groups[2].Value); 
       this.nodes.Add(new KeyValuePair<int, IDiceExpressionNode>(multiplier, new DiceRollNode(numberOfDice, diceType))); 
      } 
      else 
      { 
       throw new ArgumentException("The given dice expression was not in an expected format: the non-operand token was neither a number nor a dice-roll expression."); 
      } 
     } 

     // Sort the nodes in an aesthetically-pleasing fashion. 
     var diceRollNodes = this.nodes.Where(pair => pair.Value.GetType() == typeof(DiceRollNode)) 
             .OrderByDescending(node => node.Key) 
             .ThenByDescending(node => ((DiceRollNode)node.Value).DiceType) 
             .ThenByDescending(node => ((DiceRollNode)node.Value).NumberOfDice); 
     var numberNodes = this.nodes.Where(pair => pair.Value.GetType() == typeof(NumberNode)) 
            .OrderByDescending(node => node.Key) 
            .ThenByDescending(node => node.Value.Evaluate()); 

     // If desired, merge all number nodes together, and merge dice nodes of the same type together. 
     if (options == DiceExpressionOptions.SimplifyStringValue) 
     { 
      int number = numberNodes.Sum(pair => pair.Key * pair.Value.Evaluate()); 
      var diceTypes = diceRollNodes.Select(node => ((DiceRollNode)node.Value).DiceType).Distinct(); 
      var normalizedDiceRollNodes = from type in diceTypes 
              let numDiceOfThisType = diceRollNodes.Where(node => ((DiceRollNode)node.Value).DiceType == type).Sum(node => node.Key * ((DiceRollNode)node.Value).NumberOfDice) 
              where numDiceOfThisType != 0 
              let multiplicand = numDiceOfThisType > 0 ? +1 : -1 
              let absNumDice = Math.Abs(numDiceOfThisType) 
              orderby multiplicand descending 
              orderby type descending 
              select new KeyValuePair<int, IDiceExpressionNode>(multiplicand, new DiceRollNode(absNumDice, type)); 

      this.nodes = (number == 0 ? normalizedDiceRollNodes 
             : normalizedDiceRollNodes.Concat(new[] { new KeyValuePair<int, IDiceExpressionNode>(number > 0 ? +1 : -1, new NumberNode(number)) })).ToList(); 
     } 
     // Otherwise, just put the dice-roll nodes first, then the number nodes. 
     else 
     { 
      this.nodes = diceRollNodes.Concat(numberNodes).ToList(); 
     } 
    } 

    public override string ToString() 
    { 
     string result = (this.nodes[0].Key == -1 ? "-" : string.Empty) + this.nodes[0].Value.ToString(); 
     foreach (var pair in this.nodes.Skip(1)) 
     { 
      result += pair.Key == +1 ? " + " : " − "; // NOTE: unicode minus sign, not hyphen-minus '-'. 
      result += pair.Value.ToString(); 
     } 
     return result; 
    } 
    public int Evaluate() 
    { 
     int result = 0; 
     foreach (var pair in this.nodes) 
     { 
      result += pair.Key * pair.Value.Evaluate(); 
     } 
     return result; 
    } 
    public decimal GetCalculatedAverage() 
    { 
     decimal result = 0; 
     foreach (var pair in this.nodes) 
     { 
      result += pair.Key * pair.Value.GetCalculatedAverage(); 
     } 
     return result; 
    } 

    private interface IDiceExpressionNode 
    { 
     int Evaluate(); 
     decimal GetCalculatedAverage(); 
    } 
    private class NumberNode : IDiceExpressionNode 
    { 
     private int theNumber; 
     public NumberNode(int theNumber) 
     { 
      this.theNumber = theNumber; 
     } 
     public int Evaluate() 
     { 
      return this.theNumber; 
     } 

     public decimal GetCalculatedAverage() 
     { 
      return this.theNumber; 
     } 
     public override string ToString() 
     { 
      return this.theNumber.ToString(); 
     } 
    } 
    private class DiceRollNode : IDiceExpressionNode 
    { 
     private static readonly Random roller = new Random(); 

     private int numberOfDice; 
     private int diceType; 
     public DiceRollNode(int numberOfDice, int diceType) 
     { 
      this.numberOfDice = numberOfDice; 
      this.diceType = diceType; 
     } 

     public int Evaluate() 
     { 
      int total = 0; 
      for (int i = 0; i < this.numberOfDice; ++i) 
      { 
       total += DiceRollNode.roller.Next(1, this.diceType + 1); 
      } 
      return total; 
     } 

     public decimal GetCalculatedAverage() 
     { 
      return this.numberOfDice * ((this.diceType + 1.0m)/2.0m); 
     } 

     public override string ToString() 
     { 
      return string.Format("{0}d{1}", this.numberOfDice, this.diceType); 
     } 

     public int NumberOfDice 
     { 
      get { return this.numberOfDice; } 
     } 
     public int DiceType 
     { 
      get { return this.diceType; } 
     } 
    } 
} 

Answer 2

आप सी # (जैसे antlr) के लिए एक कंपाइलर-कंपाइलर (Yacc की तरह कुछ) में अपने व्याकरण का उपयोग कर सकते हैं या बस अपना recursive descent parser लिखना शुरू कर सकते हैं।

तो फिर तुम एक में स्मृति डेटा संरचना का निर्माण कि is Visitable so you need to write a couple of visitors (एक पेड़ अगर आप मनमाने ढंग से गणित से + अन्य कार्यों चाहते हैं):

• RollVisitor: init एक रैंड बीज तो प्रत्येक नोड पर जाकर जमा परिणाम
• GetMaxVisitor: योग ऊपरी प्रत्येक पासा
• अन्य आगंतुकों के लिए बाध्य?

(इस तरह के PrettyPrintVisitor, RollTwiceVisitor, आदि आदि के रूप में) मुझे लगता है कि एक दर्शनीय पेड़ एक योग्य समाधान यहाँ है।

Answer 3

आपको इस आलेख को CodeProject: http://www.codeproject.com/KB/cpp/rpnexpressionevaluator.aspx पर देखना चाहिए। मैं बताता हूं कि इन्फिक्स अभिव्यक्ति को पोस्टफिक्स में कैसे परिवर्तित करें और उसके बाद इसका मूल्यांकन करें।

पार्सिंग के लिए, मुझे लगता है कि आप इसे नियमित अभिव्यक्तियों से संभाल सकते हैं।

Answer 4

कुछ प्रयास:

Evaluate dice rolling notation strings