-
Notifications
You must be signed in to change notification settings - Fork 1
/
Expression.cs
75 lines (65 loc) · 2.6 KB
/
Expression.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using Algorithm.Minterms;
namespace Algorithm
{
public class Expression
{
private List<MintermBase> Minterms { get; set; }
= new List<MintermBase>();
/// <summary>
/// Parses a string into <see cref="Minterm"/> fragments.
/// </summary>
/// <param name="input">A string containing an expression.</param>
/// <exception cref="FormatException">
/// Thrown in the Minterm constructor if a subexpression is invalid; uncaught.
/// </exception>
public Expression(string input)
{
var rawMinterms = input.Split('+');
foreach (var raw in rawMinterms)
Minterms.Add(new Minterm(raw));
}
/// <summary>
/// Simplifies the <see cref="Minterms"/> contents
/// using the Q-M algorithm and returns the expression.
/// </summary>
public async Task<Expression> Simplify()
{
var currentBatch = Minterms;
var simplification = new List<MintermBase>();
List<MintermBase> foundMatches = null;
do
{
if (foundMatches != null) // if not first iteration
currentBatch = foundMatches.Distinct().ToList();
foundMatches = new List<MintermBase>();
foreach (var minterm in currentBatch.OrderBy(m => m.NumberOfOnes))
{
var potentialMatches = currentBatch
.Where(m => m.NumberOfOnes == minterm.NumberOfOnes + 1)
.Where(m => m.MatchesDomain(minterm));
foreach (var otherMinterm in potentialMatches)
{
if (await minterm.TryCombineWith(otherMinterm, out MintermBase combination))
{
foundMatches.Add(combination);
minterm.IsPrime = false;
otherMinterm.IsPrime = false;
}
}
}
// Minterms that couldn't be combined are included in final result
simplification.AddRange(currentBatch.Where(m => m.IsPrime).Distinct());
} while (foundMatches.Any());
Minterms = simplification;
return this;
}
public override string ToString()
=> Minterms
.Select(m => m.Raw())
.Aggregate((current, next) => current + " + " + next);
}
}