주사위 표현식 구문 분석(예:3d6+5) C#:어디서 시작하나요?
-
12-09-2019 - |
문제
그래서 저는 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
매번 반대?
해결책
내가 결국 생각한 것은 다음과 같습니다.
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#의 컴파일러 컴파일러 (YACC와 같은)에서 문법을 사용할 수 있습니다. antlr) 또는 당신의 글을 쓰기 시작하십시오 재귀 하강 파서.
그런 다음 메모리 내 데이터 구조를 구축합니다 ( +이외의 임의의 수학 작업을 원한다면 트리) 방문 할 수 있으므로 두 명의 방문자를 써야합니다.:
RollVisitor
: 랜드 씨앗을 시작한 다음 각 노드를 방문하여 결과를 누적합니다.GetMaxVisitor
: 각 주사위의 상한을 합산하십시오- 다른 방문객? (와 같은
PrettyPrintVisitor
,RollTwiceVisitor
, 등 등)
나는 그 생각을한다 방문 가능한 나무 여기서 가치있는 솔루션입니다.
일부 시도 :
CodeProject에서 다음 기사를 살펴보세요. http://www.codeproject.com/KB/cpp/rpnexpressionevaluator.aspx.중위 표현식을 후위 표현식으로 변환한 후 평가하는 방법을 설명합니다.
파싱의 경우 정규식으로 처리하시면 될 것 같습니다.