在 C# 中解析骰子表达式(例如 3d6+5):从哪里开始?
所以我希望能够解析和评估 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,但同样,如果我在没有懂行的人的指导下尝试,我确信它最终会变成一团不雅的混乱。
另一种可能有效的策略是一些基于正则表达式的初始字符串替换,将骰子表达式转换为 rand.Next 调用,然后进行即时评估或编译...这实际上有效吗? 如何避免每次都创建新的 rand
对象?
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 becomed100
in 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?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
这是我最终想出的:
Here's what I eventually came up with:
你可以在 C# 的编译器编译器(比如 Yacc)中使用你的语法(比如 antlr)或者直接开始编写您的递归下降解析器。
然后,您构建一个内存中的数据结构(如果您想要除 + 之外的任意数学运算,则为树),该数据结构是可访问的。所以你需要写几个访问者:
RollVisitor
:初始化一个随机种子,然后访问每个节点,累加结果GetMaxVisitor
:将每个骰子的上限相加PrettyPrintVisitor
、RollTwiceVisitor
等)我认为visitable-tree在这里是一个有价值的解决方案。
you could use your grammar in a compiler-compiler (something like Yacc) for C# (like antlr) or just start to write your recursive descent parser.
Then you build a in-memory data structure (a tree if you want arbitrary math operations other than +) that is Visitable so you need to write a couple of visitors:
RollVisitor
: init a rand seed then visiting each node, accumulating resultGetMaxVisitor
: sum the upper bound of each dicePrettyPrintVisitor
,RollTwiceVisitor
, etc etc)I think that a visitable-tree is a worthy solution here.
一些尝试:
评估骰子滚动符号字符串
Some attempts:
Evaluate dice rolling notation strings
您应该看看 CodeProject 上的这篇文章: http://www.codeproject.com /KB/cpp/rpnexpressionevaluator.aspx。 我解释了如何将中缀表达式转换为后缀一,然后对其求值。
对于解析,我认为可以用正则表达式来处理。
You should take a look at this article at CodeProject: http://www.codeproject.com/KB/cpp/rpnexpressionevaluator.aspx. I explains how to convert infix expression to postfix one and then evaluate it.
For parsing, I think you can handle it with regular expressions.