تحليل تعبيرات النرد (مثل 3D6 + 5) في C #: أين تبدأ؟

Question

لذلك أريد أن أكون قادرا على التحليل، وتقييم "تعبيرات النرد" في C #. يتم تعريف تعبير النرد مثل ذلك:

<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.

أعلم أن هذا هو بالضبط نوع الشيء Haskell، وربما لغات أخرى من النوع الوظيفية، ستكون رائعة في، ولكن أود البقاء في C # إن أمكن.

تميل أفكاري الأولية إلى التحويل، والقوائم، وربما بعض LINQ، ولكن مرة أخرى، إذا حاولت دون بعض المؤشرات من الأشخاص الذين يعرفون الأشياء، فأنا متأكد من أنه سينتهي بك الأمر إلى أن تكون فوضى غير مذهلة.

التكتيك الآخر الذي قد يعمل سيكون بعض استبدال السلسلة القائمة القائمة على Regex لتحويل تعبيرات النرد إلى 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

يمكنك استخدام قواعد اللغة الخاصة بك في مترجم مترجم (شيء مثل yacc) ل C # (مثل antlr.) أو مجرد البدء في كتابة الخاص بك المحلل النسب المتكرر.

ثم تقوم ببناء بنية بيانات داخل الذاكرة (شجرة إذا كنت تريد عمليات الرياضيات التعسفية غير +) ذلك هو قابلة للزيارة لذلك تحتاج إلى كتابة بضع زوار:

• RollVisitor: init بذرة راند ثم زيارة كل عقدة، تراكم نتيجة
• GetMaxVisitor: مجموع الحد العلوي من كل النرد
• زوار آخرين؟ (مثل PrettyPrintVisitor, RollTwiceVisitor, ، إلخ الخ)

أعتقد أن القابلة للزيارة شجرة هو حل جدير هنا.

Answer 3

بعض المحاولات:

تقييم النرد سلاسل الترميز المتداول

Answer 4

يجب عليك إلقاء نظرة على هذه المقالة في CodeProject: http://www.codeproject.com/kb/cpp/rpnexpressionevaluator.aspx.. وبعد أوضح كيفية تحويل تعبير Infix إلى Postfix One ثم تقييمه.

لتحليل، أعتقد أنه يمكنك التعامل معها مع تعبيرات منتظمة.