Нужно разобрать выражение типа 1 + 1 (<Число><Оператор><Число>) и получить результат без использования операторов switch, if-else
Помогите с идеями, пожалуйста, не могу подступиться к проблеме!
Ответ
Собственно, @tym32167 уже дал 2 ответа на поставленный вопрос вперед меня, так что я подведу итог и добавлю еще варианты решения подобных задач
#0. Использование DataTable Expressions
DataTable - мощный .NET инструмент не только для хранения данных, но и для их обработки
При помощи метода DataTable.Compute(string expression, string filter) обычно производятся расчеты, исходя из данных, занесенных в DataTable. Однако часто к этому методу прибегают именно в Вашем случае
Так что организуем скромный вспомогательный класс:
public static class Calculator
{
// Создадим статический экземпляр DataTable, чтобы каждый раз не инициализировать его заново
private static DataTable Table { get; } = new DataTable();
// Наш метод подсчета
// Добавьте отлов ошибок по вкусу)
public static double Calc(string Expression) => Convert.ToDouble(Table.Compute(Expression, string.Empty));
}
И будем использовать его подобным образом:
Console.WriteLine(Calculator.Calc("11 * 13")); // 143
Console.WriteLine(Calculator.Calc("2 + 2 * 2")); // 6
Console.WriteLine(Calculator.Calc("(13 % 11) / 4")); // 0.5
#1.0 Парсинг
Так как в рамках Вашей задачи точно известна модель <Число><Знак><Число>, как и предложил @tym32167 в своем втором ответе, можно использовать ручной парсинг выражения.
Перепишем наш класс:
public static class Calculator
{
// Определим функции для доступных операторов
private static Dictionary> Operators { get; } = new Dictionary> {
{ '+', (a, b) => a + b },
{ '-', (a, b) => a - b },
{ '/', (a, b) => a / b },
{ '%', (a, b) => a % b },
{ '*', (a, b) => a * b }
};
public static double Calc(string Expression)
{
// Очистим нашу строку от "мусора" в лице пробелов и прочих нехороших знаков
Expression = string.Concat(Expression.Where(x => char.IsDigit(x) || Operators.ContainsKey(x) || x == ','));
try
{
int begin = 0;
int end = 0;
// Заведем переменные для хранения наших чисел и оператора
string a = string.Empty;
string b = string.Empty;
char op = '\0';
// Считаем переменную a из строки
while (end < Expression.Length && (char.IsDigit(Expression[end]) || Expression[end] == ','))
end++;
a = Expression.Substring(0, end);
// Если строка закончилась, значит нам отдали только одно число. Его же и вернем
if (end == Expression.Length)
return double.Parse(a);
// Считаем оператор
op = Expression[end++];
begin = end;
// Считаем переменную b
while (end < Expression.Length && (char.IsDigit(Expression[end]) || Expression[end] == ','))
end++;
b = Expression.Substring(begin, end - begin);
// Достанем из словаря нужную нам функцию и запустим ее с двумя параметрами
return Operators[op](double.Parse(a), double.Parse(b));
}
catch
{
// Выражение некорректно и не может быть вычислено
throw new EvaluateException();
}
}
}
Из пояснений к коду, надеюсь, логика понятна
Используется как и в предыдущем случае:
Console.WriteLine(Calculator.Calc("1 + 7")); // 8
Console.WriteLine(Calculator.Calc("70 - 1")); // 69
Console.WriteLine(Calculator.Calc("70 % 3")); // 1
Console.WriteLine(Calculator.Calc("4 / 2")); // 2
#1.1 Парсинг
Процесс парсинга можно серьезно упростить, используя регулярные выражения
Выглядеть это будет так:
public static class Calculator
{
// Определим функции для доступных операторов
private static Dictionary> Operators { get; } = new Dictionary> {
{ "+", (a, b) => a + b },
{ "-", (a, b) => a - b },
{ "/", (a, b) => a / b },
{ "%", (a, b) => a % b },
{ "*", (a, b) => a * b }
};
// Регулярное выражение
// (-?\d+(?:\,\d+)?) - число типа double (может быть с запятой или без)
// (.) - одиночный символ (наш оператор)
private static Regex Regex { get; } = new Regex(@"(-?\d+(?:\,\d+)?)(.)(-?\d+(?:\,\d+)?)");
public static double Calc(string Expression)
{
// Очистим нашу строку от "мусора" в лице пробелов и прочих нехороших знаков
Expression = string.Concat(Expression.Where(x => char.IsDigit(x) || Operators.ContainsKey(char.ToString(x)) || x == ','));
try
{
Match match = Regex.Match(Expression);
// Если все прошло успешно, то:
// под индексом 1 лежит первое число
// под индексом 2 - оператор
// а под индексом 3 - второе число
if (match.Success && match.Groups.Count == 4)
// Достанем из словаря нужную нам функцию и запустим ее с двумя параметрами
return Operators[match.Groups[2].Value](double.Parse(match.Groups[1].Value), double.Parse(match.Groups[3].Value));
// Выражение некорректно и не может быть вычислено
throw new EvaluateException();
}
catch
{
// Выражение некорректно и не может быть вычислено
throw new EvaluateException();
}
}
}
Из пояснений к коду, надеюсь, логика понятна
Используется как и в предыдущем случае:
Console.WriteLine(Calculator.Calc("1 + 7")); // 8
Console.WriteLine(Calculator.Calc("70 - 1")); // 69
Console.WriteLine(Calculator.Calc("70 % 3")); // 1
Console.WriteLine(Calculator.Calc("4 / 2")); // 2
#1.2 И снова парсинг (ANTLR4)
Спасибо большое @VladD за провокацию вдохновение на написание данного варианта решения проблемы)
Итак, подойдем к парсингу максимально серьезно и прибегнем к построению лексического и синтаксического анализатора. Для этого воспользуемся ANTLR4 (вещица весьма занятная и катастрофически удобная. Удивительно, что ранее я ее каким-то образом обходил стороной))
Для начала поставим необходимое расширение для VisualStudio
Теперь в списке доступных шаблонов при добавлении нового файла в
проект у нас появился раздел ANTLR. Выберем ANTLR4 Combined Grammar, который назовем Calculator.g4
Соберем проект
Теперь у нас в папке obj/(Debug/Release) сгенерировались файлы
CalculatorBaseVisitor.cs, CalculatorLexer.cs,
CalculatorParser.cs, CalculatorVisitor.cs. Добавим их в проект по
ссылке (Добавить как связь)
Первоначальная настройка произведена!
Приступим непосредственно к созданию лексического анализатора
Грамматика (Calculator.g4) для нашего случая у меня получилась следующая (первый раз использую данную технологию, так что, возможно, написать можно было и лучше)
grammar Calculator;
/// Starting rule
compilationUnit : expression+;
/// Parser Rules
// Обозначим наше выражение
expression
// Выше всего по приоритету идет выражение в скобках
: LBRACKET expression RBRACKET # Brackets
// После идут single-функции
| statement=(SIN | COS | ROUND) expression # Function
// Возведение в степень
// заставляет парсер читать данное выражение справа налево
| expression statement=POW expression # Pow
// Деление и умножение
| expression statement=(MUL | DIV | MOD) expression # MulDiv
// Сложение и вычитание
| expression statement=(SUB | ADD) expression # SubAdd
// Определенные нами константы
| constant=(PI | E) # Constant
// Просто числовое значение (например: 3)
| VAL # Val
;
/// Lexer Rules
// Фрагменты, которые мы потом будем использовать
// для обозначения других лексических выражений
fragment DIGIT : [0-9];
fragment NUMBER : DIGIT+;
fragment DOT : '.';
fragment COMMA : ',';
fragment SEPARATOR : (DOT | COMMA);
// Значения, используемые в парсере
E : 'e';
PI : 'pi';
ADD : '+';
SUB : '-';
MUL : '*';
DIV : '/';
MOD : '%';
POW : '^';
COS : 'cos';
SIN : 'sin';
LBRACKET : '(';
RBRACKET : ')';
ROUND : 'round';
VAL : NUMBER((SEPARATOR)NUMBER)?;
// WhiteSpace, который нам не очень-то и нужен)
WS : (' '|'
'|'
'|'\t') -> skip;
Пересоберем проект. Теперь в наших автогенерирующихся файлах есть все необходимое для последующей работы
Обходить наше выражения для вычисления мы будем с помощью класса, реализующего паттерн Visitor
// Унаследуемся от базового "посетителя"
// Укажем тип результата посещения - double
public class ExpressionVisitor : CalculatorBaseVisitor
{
// Словарь с константами
private static Dictionary Constants { get; } = new Dictionary {
{ "pi", Math.PI },
{ "e", Math.E }
};
// Словарь с функциями для одного выражения
private static Dictionary> SingleOperators { get; } = new Dictionary> {
{ "sin", a => Math.Sin(a) },
{ "cos", a => Math.Cos(a) },
{ "round", a => Math.Round(a) }
};
// Словарь с функциями для двух выражений
private static Dictionary> DualOperators { get; } = new Dictionary> {
{ "+", (a, b) => a + b },
{ "-", (a, b) => a - b },
{ "/", (a, b) => a / b },
{ "%", (a, b) => a % b },
{ "*", (a, b) => a * b },
{ "^", (a, b) => Math.Pow(a, b) }
};
// Посещаем выражения
public override double VisitBrackets([NotNull] CalculatorParser.BracketsContext Context) => Visit(Context.expression());
public override double VisitConstant([NotNull] CalculatorParser.ConstantContext Context) => Constants[Context.constant.Text];
public override double VisitVal([NotNull] CalculatorParser.ValContext Context) => double.Parse(Context.VAL().GetText().Replace('.', ','));
public override double VisitFunction([NotNull] CalculatorParser.FunctionContext Context) => ComputeOperation(Context.statement.Text, Context.expression());
public override double VisitPow([NotNull] CalculatorParser.PowContext Context) => ComputeOperation(Context.expression(0), Context.statement.Text, Context.expression(1));
public override double VisitMulDiv([NotNull] CalculatorParser.MulDivContext Context) => ComputeOperation(Context.expression(0), Context.statement.Text, Context.expression(1));
public override double VisitSubAdd([NotNull] CalculatorParser.SubAddContext Context) => ComputeOperation(Context.expression(0), Context.statement.Text, Context.expression(1));
// Вычисляем
private double ComputeOperation(string Operation, CalculatorParser.ExpressionContext OperationContext) => SingleOperators.ContainsKey(Operation) ? SingleOperators[Operation](Visit(OperationContext)) : throw new EvaluateException();
private double ComputeOperation(CalculatorParser.ExpressionContext FirstOperation, string Operation, CalculatorParser.ExpressionContext SecondOperation) => DualOperators.ContainsKey(Operation) ? DualOperators[Operation](Visit(FirstOperation), Visit(SecondOperation)) : throw new EvaluateException();
}
Готово! Теперь при посещении лексических деревьев нужных нам выражений с помощью данного класса мы будем получать результат вычислений данных выражений)
Перепишем наш класс Calculator для взаимодействия с нашим "посетителем"
public static class Calculator
{
// Статический экземпляр "посетителя", чтобы каждый раз хоть его не создавать заново)
private static ExpressionVisitor Visitor { get; } = new ExpressionVisitor();
// Парсим выражение и обходим полученное лексическое дерево
public static double Calc(string Expression) => Visitor.Visit(new CalculatorParser(new CommonTokenStream(new CalculatorLexer(new AntlrInputStream(Expression.ToLower())))).compilationUnit());
}
Проверим:
Console.WriteLine(Calculator.Calc("2 + 2 * 2")); // 6
Console.WriteLine(Calculator.Calc("(2 + 2) * 2")); // 8
Console.WriteLine(Calculator.Calc("2 + 2 * 2^3^2")); // 1026
Console.WriteLine(Calculator.Calc("5 % 2 - 3")); // -2
Console.WriteLine(Calculator.Calc("sin(pi / 2) + cos(0) + round(0.9)")); // 3
Как видите, полученный калькулятор выполняет действия в правильной последовательности, а также может поддерживать абсолютно любые выражения и функции (которые мы, понятное дело, настроим))
И пусть данный вариант в ~40 раз медленнее метода #1.0, его преимущества в лице поддержки любого числа аргументов и всех вообразимых операторов делают сию версию подхода к разрешению подобных проблем очень и очень "вкусной")
#2.0 Компиляция выражения
Этот вариант будет самым массивным, ибо мы будем использовать доступ к экземплярам генератора и компилятора кода C# CSharpCodeProvider!
С помощью данного класса мы можем откомпилировать любой нужный нам код и поместить выходную сборку, скажем, в память
Итак. Логика наших действий:
Запихиваем наше выражение в return-statement некого метода некого
класса (в качестве строки)
Компилируем полученный код
Полученную сборку загружаем в память
Достаем из нее тип описанного нами класса
Из него достаем описанный нами метод
Запускаем его
Отдаем результат
Выглядит сложновато. Но на деле все довольно просто!
Вновь перепишем наш уже многострадальный класс Calculator
public static class Calculator
{
// Создадим экземпляр генератора и компилятора C#-кода
private static Microsoft.CSharp.CSharpCodeProvider CodeProvider { get; } = new Microsoft.CSharp.CSharpCodeProvider();
// Зададим опции компиляции
private static System.CodeDom.Compiler.CompilerParameters CompilerParameters { get; } = new System.CodeDom.Compiler.CompilerParameters()
{
// Нам не нужен исполняемый файл
GenerateExecutable = false,
// Выходной файл должен располагаться в памяти
GenerateInMemory = true
};
public static double Calc(string Expression)
{
try
{
// Откомпилируем наше выражение, которое будет располагаться внутри метода Calc класса Calculator
System.CodeDom.Compiler.CompilerResults compilerResult = CodeProvider.CompileAssemblyFromSource(CompilerParameters, $"using System; static class Calculator {{ public static double Calc() {{ return {Expression}; }} }}");
// Получим сборку
System.Reflection.Assembly assembly = compilerResult.CompiledAssembly;
// Достанем из сборки нужный нам тип Calculator, из него - метод Calc и таки запустим его, приведя результат исполнения к double
return (double)assembly.DefinedTypes.First(x => x.Name == "Calculator").GetMethods().First(x => x.Name == "Calc").Invoke(null, null);
} catch {
// Выражение некорректно и не может быть вычислено
throw new EvaluateException();
}
}
}
Очевидным минусом такого подхода является время, которое уходит на компиляцию (на первый взгляд оно, конечно, может показаться не слишком значимым, однако оно все таки куда больше, чем время, требующееся для других методов)
Однако есть и хороший плюс: Вы можете использовать в выражении встроенные функции различных .NET библиотек, как то System.Math
Console.WriteLine(Calculator.Calc("Math.Sqrt(81) + Math.Sin(Math.PI / 2)")); // 10
Console.WriteLine(Calculator.Calc("Math.Log(8, 2)")); // 3
Console.WriteLine(Calculator.Calc("2 + 2 * Math.Log(4, 2)")); // 6
Console.WriteLine("70 % 3"); // 1
#2.1 Использование CSharp.Scripting
CSharp.Scripting - одно из детищ Roslyn, предоставляющее очень удобное API для построения и исполнения кода прямо в runtime!
(Необходимо поставить соответствующий NuGet-пакет!)
С использованием данного механизма наш класс Calculator ужмется до:
public static class Calculator
{
// Добавьте отлов ошибок на случай неверных выражений!
public static double Calc(string Expression) => CSharpScript.EvaluateAsync(Expression).Result;
}
Кратко, красиво и очень удобно, не так ли?
Однако стоит добавить бочку дегтя в эту ложку меда: данное API имеет схожие механизмы с теми, которые я использовал в примере #2.0, так что время, которое затрачивается на вычисления, до сих пор непомерно велико
Итоги
Чтобы выбрать из такого количества вариантов решение себе по душе, неплохо было бы иметь некую табличку со сравнительными характеристиками представленных методов... Собственно, ниже я ее и набросал (если я пропустил какой-то важный/интересный пункт - напишите, пожалуйста, в комментариях))
╔═════════════╦═════════╦═════════╦═════════╦═════════╦════════════╦════════════╗
║ ║ #0 ║ #1.0 ║ #1.1 ║ #1.2 ║ #2.0 ║ #2.1 ║
╠═════════════╬═════════╬═════════╬═════════╬═════════╬════════════╬════════════╣
║ Время⁰ ║ 1370мс ║ 680мс ║ 1800мс ║ 28000мс ║ 42420100мс ║ 35457000мс ║
╠═════════════╬═════════╬═════════╬═════════╬═════════╬════════════╬════════════╣
║ Параметры¹ ║ [1..) ║ [1..2] ║ [2..2] ║ [1..) ║ [1..) ║ [1..) ║
╠═════════════╬═════════╬═════════╬═════════╬═════════╬════════════╬════════════╣
║ Сложность ║ 0.07 ║ 0.5 ║ 0.28 ║ 1 ║ 0.21 ║ 0.03 ║
║ реализации² ║ ║ ║ ║ ║ ║ ║
╠═════════════╬═════════╬═════════╬═════════╬═════════╬════════════╬════════════╣
║ Набор ║ (+) (-) ║ (+) (-) ║ (+) (-) ║ Любые ║ Любые ║ Любые ║
║ операторов³ ║ (*) (/) ║ (*) (/) ║ (*) (/) ║ ║ ║ ║
║ ║ (%) ║ (%) ║ (%) ║ ║ ║ ║
╚═════════════╩═════════╩═════════╩═════════╩═════════╩════════════╩════════════╝
0 - Среднее время расчета 1000000 выражений ("2 + 2")
1 - Количество числовых параметров, которые могут быть обработаны методом в одном выражении
2 - Относительная сложность реализации методов, рассчитанная на основе количества значимых операций
3 - Набор операторов, доступных внутри выражения
На основе таблицы видно, что абсолютным победителем по скорости исполнения стал метод #1.0, обогнав серебряного призера (#0) почти в 2 раза!
Легче всего в реализации (бесспорно) оказались методы #0 и #2.1, помимо этого они поддерживают нефиксированное число параметров внутри выражения
Использование регулярных выражений в методе #1.1 дало выигрыш в легкости реализации почти в 2 раза, однако скорость работы метода из-за этого ухудшилась почти в 3 раза!
Методы же #2.0 и #2.1 показали наихудшую скорость работы (почти в 62500 раз медленнее метода #1.0!). Однако их серьезным плюсом является то, что они поддерживают абсолютнo любые операторы (в том числе и тернарный) и функции, представленные стандартной .NET библиотекой!
Однако на фоне метода #1.2, который при тонкой настройке также способен поддерживать любые выражения и синтаксис, эти преимущества моментально меркнут
Надеюсь, мой ответ хоть немного помог Вам)
Удачи в Ваших делах!
