Не так давно я столкнулся с необходимостью
релизации вычисления значения логических выржений представленных в виде
обыкновенной строки. Логическое выражение может быть простым, например b > 5 или же составным,
и состоять из нескольких груп, как показано ниже.
a <> 0
& (b > 5 | c <> 0) & (d < 5 & e = "test")
В целях формализации данной задачи,
я написал юнит-тест который демонстрирует что конкретно я хочу. Код теста прдставлен ниже.
[TestMethod]
public void Demo_Test()
{
var statementBody = "a
<> 0 & (b > 5 | c <> 0) & (d < 5 & e =
\"test\")";
var dic = new Dictionary<string,
string>
{
{ "a", "10"
}, { "b",
"1" }, { "c",
"1" }, { "d",
"2" }, { "e",
"test" }
};
var checker = new ConditionChecker();
var result = checker.Check(
statementBody , dic);
Assert.IsTrue(result);
}
Классический способ решения данной задачи состоит в том, что по выражению формируется
дерево, осуществляются вычисления для каждого узла дерева и формируется
результат.
Решение которое мне пришло в голову показалось мне более простым и достаточно эффективным и я решил
что это именно то что мне нужно. Суть его заключалась в том, что вместо того
что бы по этому выражению стоить дерево, достаточно найти все условные операции
в выражении вычислить результат для каждой из них и в выражении вместо условной
операции поместить результат. То есть в итоге прийти к следующему выражению
которое будет эквивалентным исходному:
"1 & (0 | 1) & (1 & 1)".
Здесь 1 – означает что условие выполняется, а 0 –что нет. То есть условие a <> 0 при a = 10 выполняется и поэтому замещаем его единицей, а при b = 1 условие b > 5 не выполняется поэтому замещаем его нулем, И таким же образом поступаем со всеми остальными операциями.
"1 & (0 | 1) & (1 & 1)".
Здесь 1 – означает что условие выполняется, а 0 –что нет. То есть условие a <> 0 при a = 10 выполняется и поэтому замещаем его единицей, а при b = 1 условие b > 5 не выполняется поэтому замещаем его нулем, И таким же образом поступаем со всеми остальными операциями.
После того как все условия были посчитаны и замещены нулем или единицей,
следующим этапом будет вычисления результата логических операций в скобках, то
есть сначала вычисляем результат для (0 | 1), потом для (1 & 1), а потом для т ого что получилось 1 & 1 & 1. В итоге получим требуемый результат.
Ниже представлена реализация данного способа в деталях.
private const char groupStart
= '(';
private const char groupEnd
= ')';
private const char logicalAnd
= '&';
private const char logicalOr
= '|';
private const string operatorEqual
= "=";
private const string operatorGreate
= ">";
private const string operatorLess
= "<";
private const string operatorNotEqual
= "<>";
internal bool
Check(string
content, Dictionary<string, string>
variables)
{
var operations = new[]
{ operatorEqual, operatorNotEqual, operatorGreate,
operatorLess };
var dic = new List<CalculatedCondition>();
content = groupStart + content
+ groupEnd;
foreach (var operation
in operations)
{
var index = 0;
do
{
index = content.IndexOf(operation,
index);
if(index == -1)
{
break;
}
if(!dic.Any(c
=> index > c.BeginIndex
&& index < c.EndIndex))
{
int beginIndex = GetExpressionBeginBoundary(content,
index, operation.Length);
int endIndex = GetExpressionEndBoundary(content,
index, operation.Length);
var expression = content.Substring(beginIndex,
endIndex - beginIndex);
var result = this.CheckCondition(expression, variables);
dic.Add(new CalculatedCondition
{ BeginIndex = beginIndex, EndIndex = endIndex, Expression
= expression, Result = result });
}
index += operation.Length;
} while(true);
}
content = dic.Aggregate(content,
(current, calculatedCondition) => current.Replace(calculatedCondition.Expression, calculatedCondition.Result ? "1"
: "0"));
content = content.Replace(" ", string.Empty);
return ComposeResult(content);
}
Вычисление условия:
internal bool CheckCondition(string
condition, Dictionary<string, string>
variables)
{
var result = false;
if (condition.IndexOfAny(new[] { logicalAnd,
logicalOr }) != -1)
{
// only expressions like "varname >
value" are supported
throw new
NotSupportedException();
}
var operations = new
[] { operatorEqual, operatorNotEqual, operatorGreate,
operatorLess};
foreach (var operation in
operations)
{
if(condition.Contains(operation))
{
int index = condition.IndexOf(operation);
var verb = condition.Substring(0, index).Trim();
var arg = condition.Substring(index + operation.Length).Trim(new [] {' ','\'','\"'
});
string val = null;
if(variables.ContainsKey(verb))
{
val = variables[verb];
}
if(val !=null)
{
decimal num1 = 0, num2 = 0;
bool isNum1 = decimal.TryParse(val, out
num1);
bool
isNum2 = decimal.TryParse(arg,
out num2);
switch (operation)
{
case operatorEqual:
result = isNum1
&& isNum2 ? num1 == num2 : val == arg;
break;
case operatorNotEqual:
result = isNum1
&& isNum2 ? num1 != num2 : val != arg;
break;
case
operatorGreate:
result =
!isNum1 || !isNum2 || num1 > num2;
break;
case operatorLess:
result =
!isNum1 || !isNum2 || num1 < num2;
break;
}
break;
}
else
{
throw new NotSupportedException(
string.Format("Variable {0} doesn't exists in the current context",
verb));
}
}
}
return result;
}
Подготовка конечного результата:
private bool ComposeResult(string
content)
{
// (0|(1&1))&1)
Debug.WriteLine(content);
var start = 0;
var resultChanged = false;
do
{
start = 0;
resultChanged = false;
while(true)
{
start = content.IndexOf(groupStart, start);
var nextStart = content.IndexOf(groupStart,
start + 1);
var end = content.IndexOf(groupEnd,
start + 1);
if (start == -1 && end ==
-1)
{
break;
}
else
{
if(end < nextStart || nextStart == -1)
{
var str = content.Substring(start,
(end + 1) - start);
bool result = ToBool(str);
content = content.Replace(str, result ? "1"
: "0");
resultChanged
= true;
break;
}
}
start = nextStart;
}
}while(resultChanged && start !=
-1);
return content == "1";
}
Вычисление границ выражения:
internal int GetExpressionBeginBoundary(string content, int
operationIndex, int operationLength)
{
int resultIndex = -1;
var index = operationIndex - 1;
while (content.ElementAt(index)
== ' ')
{
--index;
}
for (; index >= 0; --index)
{
var separatorsForNotStrings = new[] { ' ', groupStart, logicalAnd,
logicalOr };
var currentElement = content.ElementAt(index);
if (groupEnd
== currentElement)
{
throw new
NotSupportedException(string.Format("Illegal endGroup symbol found at {0}",
index));
}
if (separatorsForNotStrings.Any(c => c == currentElement))
{
resultIndex = index + 1;
break;
}
}
// set begin on expression
if (resultIndex == -1)
{
resultIndex = 0;
}
return resultIndex;
}
internal int GetExpressionEndBoundary(string
content, int operationIndex, int operationLength)
{
int resultIndex = -1;
// skip operation text
var index = operationIndex + operationLength;
// skip spaces if present
while (content.ElementAt(index)
== ' ')
{
++index;
}
// check if operand is string
bool isString = false;
var argumentStartsWith = content.ElementAt(index);
if(argumentStartsWith == '\''
|| argumentStartsWith == '\"')
{
isString = true;
++index;
}
for(; index < content.Length; index++)
{
var separatorsForNotStrings = new[] { ' ', groupEnd, logicalAnd,
logicalOr };
var separatorsForStrings = new[] { '\'', '\"' };
var currentElement = content.ElementAt(index);
if(groupStart
== currentElement)
{
throw new
NotSupportedException(string.Format("Illegal startGroup symbol found at {0}",
index));
}
if(isString)
{
if (separatorsForStrings.Any(c => c == currentElement))
{
++index;
resultIndex = index;
break;
}
}
else
{
if (separatorsForNotStrings.Any(c => c == currentElement))
{
resultIndex = index;
break;
}
}
}
// set end on expression
if (resultIndex == -1)
{
resultIndex = content.Length;
}
return resultIndex;
}
Вспомогательные функции:
private bool ToBool(string
str)
{
str = str.Trim(new[] { groupStart,
groupEnd });
var
operations = new[] { logicalAnd,
logicalOr };
if(!operations.Any(o
=> str.Contains(o)))
{
return str == "1";
}
var arg1 = str.ElementAt(0)
== '1';
for(int i=1; iLength ; i+=2)
{
var operation = str.ElementAt(i);
var arg2 = str.ElementAt(i+1)
== '1';
switch (operation)
{
case logicalAnd:
arg1 = arg1
& arg2;
break;
case logicalOr:
arg1 = arg1
| arg2;
break;
}
}
return arg1;
}
