Phân tích biểu thức súc sắc (ví dụ: 3d6 + 5) trong C#: bắt đầu từ đâu?

Question

Vì vậy, tôi muốn có thể phân tích cú pháp và đánh giá "biểu thức xúc xắc" trong C#. Biểu thức xúc xắc được xác định như sau:

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

Vì vậy, ví dụ: d6+20-2d3 sẽ được phép, và nên đánh giá như

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

Cũng d% nên tương đương với d100.

Tôi biết tôi có thể hack cùng một số giải pháp, nhưng tôi cũng biết rằng điều này có vẻ như một vấn đề khoa học máy tính rất điển hình, vì vậy phải có một số giải pháp siêu thanh lịch mà tôi nên xem xét.

Tôi muốn kết quả của phân tích cú pháp của tôi để có những khả năng:

• tôi sẽ có thể sản xuất một hình thức bình thường của biểu thức; Tôi đang suy nghĩ xúc xắc đầu tiên, được sắp xếp theo kích thước súc sắc, và luôn luôn với một tiền tố. Vì vậy, ví dụ: mẫu trên sẽ trở thành 1d6-2d3+20. Ngoài ra, mọi trường hợp d% sẽ trở thành d100 ở dạng được chuẩn hóa.
• Tôi sẽ có thể đánh giá biểu thức theo ý muốn, luân phiên các số ngẫu nhiên khác nhau mỗi lần.
• Tôi sẽ có thể đánh giá biểu thức với tất cả các cuộn xúc xắc được phóng to, vì vậy ví dụ: mẫu trên sẽ đưa ra (xác định) 1*6+20+2*3 = 32.

Tôi biết rằng đây chính là loại điều Haskell, và có thể là các ngôn ngữ kiểu hàm khác, sẽ rất tuyệt, nhưng tôi muốn ở lại C# nếu có thể. Ý tưởng ban đầu của tôi có xu hướng hướng tới đệ quy, danh sách, và có thể một số LINQ, nhưng một lần nữa, nếu tôi cố gắng mà không có một số gợi ý từ những người biết mọi thứ, tôi chắc chắn nó sẽ trở thành một mớ hỗn độn không thích hợp.

Một chiến thuật khác có thể hoạt động sẽ là chuỗi thay thế dựa trên regex ban đầu để biến các biểu thức xúc xắc thành các cuộc gọi rand.Next, sau đó đánh giá hoặc biên dịch trực tuyến ... thực sự có hiệu quả không? Làm thế nào tôi có thể tránh tạo một đối tượng rand mới mỗi lần?

Answer 1

Dưới đây là những gì tôi cuối cùng đã đưa ra: tham số đầu tiên

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

bạn có thể sử dụng ngữ pháp của mình trong trình biên dịch-trình biên dịch (giống như Yacc) cho C# (như antlr) hoặc chỉ bắt đầu viết recursive descent parser.

Sau đó, bạn xây dựng một cấu trúc dữ liệu trong bộ nhớ (một cây nếu bạn muốn hoạt động độc đoán toán học khác hơn +) mà is Visitable so you need to write a couple of visitors:

• RollVisitor: init một hạt giống rand sau đó quý khách đến thăm mỗi nút, tích lũy kết quả
• GetMaxVisitor: tổng giá trị trên của mỗi con xúc xắc
• khách truy cập khác? (Chẳng hạn như PrettyPrintVisitor, RollTwiceVisitor, etc etc)

Tôi nghĩ rằng một có thể đến thăm cây là một giải pháp đáng ở đây.

Answer 3

Bạn nên xem bài viết này tại CodeProject: http://www.codeproject.com/KB/cpp/rpnexpressionevaluator.aspx. Tôi giải thích làm thế nào để chuyển đổi biểu thức infix thành postfix một và sau đó đánh giá nó.

Để phân tích cú pháp, tôi nghĩ bạn có thể xử lý nó bằng cụm từ thông dụng.

Answer 4

Một số nỗ lực:

Evaluate dice rolling notation strings