Jak wspomniałem w poptrzednim wpisie na ten temat, zadanie polega na znalezieniu takich działań, które wstawione pomiędzy liczby dadzą równianie. Dla utrudnienia, poszczególne składniki obu części równości można łączyć tworząc liczbę składającą się z cyfr obu składowych. Nie można przestawiać kolejności składników ani cyfr w składnikach. Wynik każdego działania musi być liczbą całkowitą, a składowe muszą być liczbą całkowitą dodatnią. Dla przykładu dane składowe 1 i 23 można zestawić tak:
1 + 23
1 – 23
1 * 23
123
(1 / 23 odpada, bo wynik dzielenia pozostawia resztę)
Program będzie wykonywał sekwencję:
- Przyjmie dane wejściowe
- Wygeneruje możliwe kombinacje dla obu stron równiania
- Policzy wartość każdego wyrażenia eliminując te, które nie spełniają wymagania dzielenia bez reszty
- Znajdzie kombinacje obu stron równania, które można zestawić ze sobą (dają równość)
- Wyświetli wyniki
W tym wpisie zajmę się utworzeniem wyrażeń dla jednej strony równania. W kolejnych wpisach, kiedy będą obliczane wartości wyrażeń (punkt 3), wywołamy kod dwuktotnie. Część 1 i 5 będą pokazane na końcu, kiedy zbudowana zostanie aplikacja Blazor a z nią interfejs użytkownika.
Na początek utworzymy obiekt – model wyrażenia. Będzie on zawierał listę składowych i listę działań matematycznych. Oprócz tego zapiszemy wynik wyrażenia oraz flagę wskazującą, czy działanie jest ważne czy też błędne. Zdefiniujmy też dozwolone działania matematyczne.
public class Expression
{
public List<int> Numbers { get; set; } = new();
public List<OperationType> Operations { get; set; } = new();
public int? CalculatedResult { get; set; }
public bool ErrorOccured { get; set; }
}
public enum OperationType
{
Add,
Substract,
Multiplicate,
Divide
}Właściwości Numbers i Operations są od razu inicjalizowane, bo za chwilę będą w nich przechowywane kolejne elementy. Dla wyrażenia '1+23′ instancja Expression będzie zawierała w liście Numbers kolejno liczby 1, 23 a Operations jedną z operacji.
Wykonajmy metodę budującą te wyrażenia. Znajdzie się ona w klasie ExpressionBuilder. Wyrażenia będą budowane od lewej. Wejściowa lista liczb, np. 1, 2, 3 będzie dzielona na liczby z lewej strony operacji oraz na te z prawej strony. Pomiędzy nie wstawiamy po kolei operacje Add, Substract, Multiplicate, Divide. Na początku pozycja podziału znajduje się pomiędzy 1 (leftHandNumbers linia 13) a 2 i 3 (rightHandNumbers linia 19). W linii 14 wywoływana jest funkcja GetPartialExpressions, do której przekazywane są leftHandNumbers i całe wyrażenie. Tam tworzone są operacje częściowe 1+, 1-, 1* i 1/. Funkcja zwraca wyliczenie takich częściowych operacji. Potem w linii 18-20 do każdej z operacji częściowych dodawana jest nowa liczba powstała z połączenia składników rightHandNumbers (dla naszego przykładu jest to 23), a całe wyrażenie (1+23, 1-23 1*23, 1/23) dodawane do listy gotowych wyrażeń (linia 21). Następnie rekurencyjnie wołamy metodę CreateExpressions dla każdego elementu partialExpression przekazując rightHandNumbers (liczby 2 i 3). Co się tam wydarzy? Do każdego wyrażenia częściowego zostaną dobudowane kolejne:
1+2+
1+2-
1+2*
1+2/
1-2+
1-2-
….. i tak dalej.
Potem znów zostanie wywołana rekurencyjnie CreateExpressions. I tak do momentu, aż zabraknie składowych po prawej stronie i nie da się przesunąć wskaźnika position w prawo. Przypadek z trzema składowymi jest jeszcze prosty, ale przy większej ich liczbie pojawiają się wyrażenia bardziej złożone, np. 123 + 4 – 56 / 7 * 6 – 89.
public class ExpressionBuilder
{
private List<Expression> Expressions { get; } = new();
private void CreateExpressions(ICollection<int> numbers, Expression? expression = null)
{
var position = 0;
while (position < numbers.Count - 1)
{
++position;
var leftHandNumbers = numbers.Take(position);
var partialExpressions = GetPartialExpressions(leftHandNumbers.ToNumber(), expression);
foreach (var partialExpression in partialExpressions)
{
var newExpression = partialExpression.Clone();
var rightHandNumbers = numbers.Skip(position).ToList();
newExpression.Numbers.Add(rightHandNumbers.ToNumber());
Expressions.Add(newExpression);
CreateExpressions(rightHandNumbers.ToArray(), partialExpression);
}
}
}
private static IEnumerable<Expression> GetPartialExpressions(int number, Expression expression)
{
var newExpressions = new List<Expression>();
foreach (var operation in Enum.GetValues<OperationType>())
{
var newExpression = expression.Clone();
newExpression.Numbers.Add(number);
newExpression.Operations.Add(operation);
newExpressions.Add(newExpression);
}
return newExpressions;
}
}Za każdym razem, kiedy tworzymy nowe wyrażenie, robimy to na podstawie innego, nie do końca zbudowanego wyrażenia częściowego. To częściowe wyrażenie jest bazą dla budowy kilku nowych. Za każdym razem musi być utworzona kompletna kopia włączając kopiowanie typów referencyjnych składających się na wyrażenie (metoda Clone w liniach 18 i 33). Jest to tzw. deep copy Więcej od Microsoftu o kopiowaniu typów. Metoda jest składową typu Expression. Uzupełnijmy zatem listing
public class Expression
{
public List<int> Numbers { get; set; } = new();
public List<OperationType> Operations { get; set; } = new();
public int? CalculatedResult { get; set; }
public bool ErrorOccured { get; set; }
public Expression Clone()
{
var clone = (Expression)MemberwiseClone();
clone.Numbers = new List<int>(Numbers);
clone.Operations = new List<OperationType>(Operations);
return clone;
}
}Ponadto używana jest medoda ToNumber rozszerzająca typ IEnumerable<int>. To mała metoda pomocnicza do konkretnego zastosowania. Nie ma sensu tworzyć jej generycznego odpowiednika, choć byłoby to możliwe.
public static class Extensions
{
public static int ToNumber(this IEnumerable<int> numbers)
{
return int.Parse(string.Concat(numbers));
}
}Listing klasy ExpressionBuilder powyżej jest nieco uproszczony, aby nie zaciemniać podstawowego kodu tworzącego wyrażenie. Ale dla pełnego obrazu przytaczam całość z komentarzami w punktach:
- Zdefiniowana jest tu metoda GetExpressions, która pozwala nasz obiekt poprosić o wyniki. Osobiśnie wolę takie podejście, niż wydawać polecenie
expressionBuilder.CreateExpressions(), a potem odczytywać właściwośćExpressions. Niech procedura wykonania zadania pozostanie wewnętrzną sprawą obiektu. My prosimy tylko o dostarczenie wyników. - Linia 13 rozwiązuje przypadek brzegowy, kiedy przekazywana kolekcja nie zawiera żadnej liczby.
- Sprawdzamy, czy to jest pierwsza iteracja (linia 15) i wtedy dodajemy do wyników wyrażenie złożone z połączonych liczb nie zawierające żadnej operacji. Dodatkowo sprawdzany jest warunek brzegowy, czy przekazana kolekcja zawiera pojedynczą liczbę. Jeśli tak, to jest ona jedynym składniniej wyrażenia i metoda kończy pracę (linia 20).
- Piersze wywołanie
GetPartialExpressions(przy pierwszej iteracji) przekazuje nowy 'pusty’ obiektExpression(linia 31).
public class ExpressionBuilder
{
private List<Expression> Expressions { get; } = new();
public List<Expression> GetExpressions(ICollection<int> numbers)
{
CreateExpressions(numbers);
return Expressions;
}
private void CreateExpressions(ICollection<int> numbers, Expression? expression = null)
{
if (!numbers.Any()) return;
if (expression is null)
{
var newExpression = new Expression();
newExpression.Numbers.Add(numbers.ToNumber());
Expressions.Add(newExpression);
if (numbers.Count == 1) return;
}
var position = 0;
while (position < numbers.Count - 1)
{
++position;
var leftHandNumbers = numbers.Take(position);
var partialExpressions = GetPartialExpressions(leftHandNumbers.ToNumber(),
expression ??= new Expression());
foreach (var partialExpression in partialExpressions)
{
var newExpression = partialExpression.Clone();
var rightHandNumbers = numbers.Skip(position).ToList();
newExpression.Numbers.Add(rightHandNumbers.ToNumber());
Expressions.Add(newExpression);
CreateExpressions(rightHandNumbers.ToArray(), partialExpression);
}
}
}
private static IEnumerable<Expression> GetPartialExpressions(int number, Expression expression)
{
var newExpressions = new List<Expression>();
foreach (var operation in Enum.GetValues<OperationType>())
{
var newExpression = expression.Clone();
newExpression.Numbers.Add(number);
newExpression.Operations.Add(operation);
newExpressions.Add(newExpression);
}
return newExpressions;
}
}Na koniec uzupełniamy obiekt Expression naszą wersją metody ToString. Będzie potrzebna przy drukowaniu wyników, kiedy będziemy chcieli pokazać każde wyrażenie w postaci czytelnej dla człowieka.
public class Expression
{
// tu kod z poprzedniego listingu klasy Expression
public override string ToString()
{
if (!Operations.Any()) return Numbers.FirstOrDefault().ToString();
var sb = new StringBuilder();
var position = 0;
while (position < Operations.Count)
{
sb.Append(Numbers[position]);
switch (Operations[position])
{
case OperationType.Add:
sb.Append(" + ");
break;
case OperationType.Substract:
sb.Append(" - ");
break;
case OperationType.Multiplicate:
sb.Append(" * ");
break;
case OperationType.Divide:
sb.Append(" / ");
break;
}
++position;
}
sb.Append(Numbers.Last());
return sb.ToString();
}
}To na razie tyle. W następnym wpisie zbudujemy kalkulator, który policzy nam wartość wyrażenia z zachowaniem kolejności działań.
