解析C＃中的骰子表达式（例如3d6 + 5）：从哪里开始？ [英] Parsing dice expressions (e.g. 3d6+5) in C#: where to start?
本文介绍了解析C＃中的骰子表达式（例如3d6 + 5）：从哪里开始？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
因此，我希望能够解析和评估C＃中的骰子表达式。骰子表达式的定义如下：
< expr> ：=< expr> +< expr>
| < expr> -< expr>
| [< number>] d（< number ||％）
| < number>
< number> ：=正整数
例如 d6 + 20-2d3 是允许的，并且应评估为
rand.Next（1，7）+ 20-（rand.Next（1，4）+ rand.Next（1，4））
d％也应等于 d100 。
我知道我可以一起破解一些解决方案，但我也知道这似乎是一个非常典型的计算机科学类型的问题，因此我必须研究一些超级优雅的解决方案。 / p>
我希望解析的结果具有以下功能：
- 我应该能够输出表达式的规范化形式；我先考虑骰子，按骰子大小排序，并且始终带有前缀。所以上面的示例将变为
1d6-2d3 + 20。同样，任何d％实例都将以规范化形式变为d100。 - 我应该能够随意评估表达式，每次滚动不同的随机数。
- 我应该能够评估所有骰子最大化的表达式，例如上面的示例将（确定地）给出
1 * 6 + 20 + 2 * 3 = 32。
我知道，这正是Haskell以及其他功能类型语言最擅长的类型，但如果可能的话，我想继续使用C＃。
我最初的想法倾向于递归，列表，也许还有一些LINQ，但是再说一次，如果我在没有认识的人的指导下进行尝试，我相信它最终会变成一团糟
另一种可行的策略是，使用一些基于正则表达式的初始字符串替换，将骰子表达式转换为 rand。下一步调用，然后进行即时评估或编译……这实际上可以工作吗？如何避免每次都创建新的 rand 对象？
解决方案
这是我最终想到的：
using System;
使用System.Collections.Generic;
使用System.Linq;
使用System.Text.RegularExpressions;
公共枚举DiceExpressionOptions
{
无，
SimplifyStringValue
}
公共类DiceExpression
{
/ * < expr> ：=< expr> +< expr>
* | < expr> -< expr>
* | [< number>] d（< number ||％）
* | < number>
*< number> ：=正整数
* * /
私有静态只读Regex numberToken = new Regex（ ^ [0-9] + $）;
私有静态只读Regex diceRollToken = new Regex（ ^（[0-9] *）d（[0-9] + |％）$）;
公共静态只读DiceExpression零=新的DiceExpression（ 0）;
private List< KeyValuePair< int，IDiceExpressionNode>>节点=新List< KeyValuePair< int，IDiceExpressionNode>>（）;
公共DiceExpression（字符串表达式）
：此（表达式，DiceExpressionOptions.None）
{}
公共DiceExpression（字符串表达式，DiceExpressionOptions选项）
{
//格式正确的骰子表达式的记号将为+，-，整数或XdY。
var令牌= expression.Replace（ +， +）.Replace（-，-）.Split（’’，StringSplitOptions.RemoveEmptyEntries）;
//空白骰子表达式最终为DiceExpression.Zero。
if（！tokens.Any（））
{
tokens = new [] { 0};
}
//由于我们解析操作符-然后-操作数对中的标记，因此请确保第一个标记是操作数。
if（tokens [0]！= +&& tokens [0]！=-）
{
tokens =（new [] { +}） .Concat（令牌）.ToArray（）;
}
//这是下面的解析循环有意义的前提。
if（tokens.Length％2！= 0）
{
throw new ArgumentException（给定的骰子表达式不是预期的格式：即使在归一化之后，它也包含奇数个令牌。）；
}
//将operator-then-operand对解析为this.nodes。
for（int tokenIndex = 0; tokenIndex< tokens.Length; tokenIndex + = 2）
{
var token = tokens [tokenIndex];
var nextToken = tokens [tokenIndex + 1];
if（令牌！= +&&令牌！=-）
{
throw new ArgumentException（给定的骰子表达式不在预期中格式。）;
}
int乘数=令牌== +？ +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>（乘数，new DiceRollNode（numberOfDice，diceType）））;
}
else
{
throw new ArgumentException（给定的骰子表达式不是预期的格式：非操作数令牌既不是数字也不是骰子表达式。）;
}
}
//以美观的方式对节点进行排序。
var diceRollNodes = this.nodes.Where（pair => pair.Value.GetType（）== typeof（DiceRollNode））
.OrderByDescending（node => node.Key）
.nnByDescending（node =>（（（DiceRollNode）node.Value）.DiceType）
.nnbyDescending（node =>（（（DiceRollNode）node.Value）.NumberOfDice）;
var numberNodes = this.nodes.Where（pair => pair.Value.GetType（）== typeof（NumberNode））
.OrderByDescending（node => node.Key）
.nnByDescending（node => node.Value.Evaluate（））;
//如果需要，将所有数字节点合并在一起，并将相同类型的骰子节点合并在一起。
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 =来自diceTypes中的类型
let numDiceOfThisType = diceRollNodes.Where（node =>（（DiceRollNode）node.Value）.DiceType == type）.Sum（node => node.Key *（（（DiceRollNode）node.Value）.NumberOfDice）
其中numDiceOfThisType！= 0
让被乘数= numDiceOfThisType> 0？ +1：-1
let absNumDice = Math.Abs（numDiceOfThisType）
orderby被乘数降序
orderby类型由降序
选择新的KeyValuePair< int，IDiceExpressionNode>（multiplicand，新的DiceRollNode（ absNumDice，类型））；
this.nodes =（number == 0？normalizedDiceRollNodes
：normalizedDiceRollNodes.Concat（new [] {new KeyValuePair< int，IDiceExpressionNode>（number> 0？+1：-1 ，新的NumberNode（number））}）。ToList（）;
}
//否则，只需将骰子掷骰节点放在第一位，然后是数字节点即可。
else
{
this.nodes = diceRollNodes.Concat（numberNodes）.ToList（）;
}
}
公共替代字符串ToString（）
{
字符串result =（this.nodes [0] .Key == -1？ -：string.Empty）+ this.nodes [0] .Value.ToString（）;
foreach（this.nodes.Skip（1）中的变量对）
{
结果+ = pair.Key == +1？ +：-; //注意：unicode减号，而不是连字符减号-。
结果+ = pair.Value.ToString（）;
}
返回结果；
}
public int Evaluate（）
{
int result = 0;
foreach（this.nodes中的变量对）
{
结果+ = pair.Key * pair.Value.Evaluate（）;
}
返回结果；
}
公众十进制GetCalculatedAverage（）
{
十进制结果= 0;
foreach（此节点中的变量对）
{
结果+ = pair.Key * pair.Value.GetCalculatedAverage（）;
}
返回结果；
}
专用接口IDiceExpressionNode
{
int Evaluate（）;
十进制GetCalculatedAverage（）;
}
私有类NumberNode：IDiceExpressionNode
{
private int theNumber;
public NumberNode（int theNumber）
{
this.theNumber = theNumber;
}
public int Evaluate（）
{
返回this.theNumber;
}
公共小数点GetCalculatedAverage（）
{
返回this.theNumber;
}
公共替代字符串ToString（）
{
返回this.theNumber.ToString（）;
}
}
私有类DiceRollNode：IDiceExpressionNode
{
私有静态只读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）;
}
总回报；
}
公共小数点GetCalculatedAverage（）
{
返回this.numberOfDice *（（this.diceType + 1.0m）/ 2.0m）;
}
公共替代字符串ToString（）
{
返回string.Format（ {0} d {1}，this.numberOfDice，this.diceType ）;
}
public int NumberOfDice
{
get {return this.numberOfDice; }
}
public int DiceType
{
get {返回this.diceType; }
}
}
}
So I want to be able to parse, and evaluate, "dice expressions" in C#. A dice expression is defined like so:
<expr> := <expr> + <expr>
| <expr> - <expr>
| [<number>]d(<number>|%)
| <number>
<number> := positive integer
So e.g. d6+20-2d3 would be allowed, and should evaluate as
rand.Next(1, 7) + 20 - (rand.Next(1, 4) + rand.Next(1, 4))
Also d% should be equivalent to d100.
I know I could hack together some solution, but I also know that this seems like a very typical computer-science type problem, so there must be some super-elegant solution I should look into.
I'd like the result of my parsing to have these capabilities:
- I should be able to output a normalized form of the expression; I'm thinking dice first, sorted by dice size, and always with a prefix. So e.g. the above sample would become
1d6-2d3+20. Also any instances ofd%would becomed100in the normalized form. - I should be able to evaluate the expression at-will, rolling different random numbers each time.
- I should be able to evaluate the expression with all of the dice-rolls maximized, so e.g. the sample above would give (deterministically)
1*6+20+2*3 = 32.
I know that this is exactly the type of thing Haskell, and probably other functional-type languages, would be great at, but I'd like to stay in C# if possible.
My initial thoughts tend toward recursion, lists, and maybe some LINQ, but again, if I tried without some pointers from people who know things, I'm sure it'd end up being an inelegant mess.
Another tactic that might work would be some initial regex-based string-replacement to turn dice expressions into rand.Next calls, and then on-the-fly evaluation or compilation... would this actually work? How could I avoid creating a new rand object every time?
解决方案
Here's what I eventually came up with:
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; }
}
}
}
这篇关于解析C＃中的骰子表达式（例如3d6 + 5）：从哪里开始？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
