Wyrażenia kostki parsowania (np. 3d6 + 5) w języku C#: od czego zacząć?

Question

Więc chcę móc analizować i oceniać "wyrażenia kostki" w języku C#. Wyrażenie kostki jest zdefiniowane w następujący sposób:

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

Tak np. d6+20-2d3 będzie mogła i powinna ocenić jako

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

także d% powinna być równoważna d100.

Wiem, że mogę zhakować razem jakieś rozwiązanie, ale wiem też, że wydaje się to bardzo typowym problemem komputerowo-naukowym, więc musi być jakieś super-eleganckie rozwiązanie, które powinienem zbadać.

Chciałbym wynik mojego parsowania mieć te funkcje:

• powinienem być w stanie do wyjścia znormalizowaną formą wypowiedzi; Najpierw myślę o kościach, posortowane według rozmiaru kości i zawsze z prefiksem. Np. powyższa próbka stanie się 1d6-2d3+20. Również wszelkie wystąpienia d% staną się d100 w znormalizowanej postaci.
• Powinienem być w stanie ocenić wyrażenie w-woli, tocząc różne liczby losowe za każdym razem.
• Powinienem być w stanie ocenić wyrażenie ze zmaksymalizowanymi wszystkimi rzutami kości, np. próbka powyżej dałaby (deterministycznie) 1*6+20+2*3 = 32.

Wiem, że to jest dokładnie taki typ rzeczy, w którym Haskell i prawdopodobnie inne języki funkcjonalne byłyby świetne, ale chciałbym pozostać w C#, jeśli to możliwe.

Moje początkowe myśli mają tendencję do rekurencji, list, a może niektórych LINQ, ale znowu, jeśli spróbuję bez wskazówek od ludzi, którzy znają się na rzeczy, jestem pewien, że skończyłoby się to nieeleganckim bałaganem.

Inną taktyką, która może zadziałać, byłby jakiś początkowy zastępczy łańcuch znaków zastępujący wyrażenia kostki w wywołaniach rand.Next, a następnie ocena lub kompilacja w locie ... czy to faktycznie zadziałałoby? Jak mogę uniknąć tworzenia nowego obiektu za każdym razem?

Answer 1

oto co ostatecznie wymyślił: pierwszy parametr

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

możesz użyć swojej gramatyki w kompilatorze-kompilatorze (coś jak Yacc) dla C# (jak antlr) lub po prostu zacznij pisać swoją recursive descent parser.

Następnie należy zbudować strukturę danych w pamięci (drzewa, jeśli chcą dowolnych operacji matematycznych inne niż +), który is Visitable so you need to write a couple of visitors:

• RollVisitor: init ziarno rand następnie odwiedzenie każdego węzła, gromadząc wynik
• GetMaxVisitor: suma górnej granicy każdej kostki
• innych odwiedzających? (Takich jak PrettyPrintVisitor, RollTwiceVisitor, etc etc)

myślę że visitable drzewa jest godne rozwiązanie tutaj.

Answer 3

Powinieneś rzucić okiem na ten artykuł w CodeProject: http://www.codeproject.com/KB/cpp/rpnexpressionevaluator.aspx. Wyjaśniam, jak konwertować wyrażenie infix, aby je poprawić, a następnie ocenić.

Do parsowania, myślę, że poradzisz sobie z nim za pomocą wyrażeń regularnych.

Answer 4

Niektóre próby:

Evaluate dice rolling notation strings