C# парсинг выражения

Парсинг выражений является одним из фундаментальных аспектов при разработке программного обеспечения на языке C#. Он позволяет анализировать строковые выражения и преобразовывать их в структурированные данные, что очень полезно при работе с математическими формулами, логическими операциями и другими подобными задачами.

Классический подход к парсингу выражений

В классическом подходе к парсингу выражений в C# можно использовать рекурсивный спуск или методы типа "шунтовый" анализ (shunting-yard algorithm). В обоих случаях основная идея заключается в разделении выражения на множество маленьких частей и последовательном анализировании каждой из них.

Рекурсивный спуск

Рекурсивный спуск - это метод, основанный на разбиении выражения на подвыражения до тех пор, пока мы не достигнем самого маленького фрагмента, который мы можем обработать. Обычно это обычные числа, переменные или операции с единственным операндом.

Пример простого выражения, содержащего математическую операцию сложения: "2 + 3":

public class ExpressionParser
{
    private string expression;
    private int position;

    public ExpressionParser(string expression)
    {
        this.expression = expression;
        this.position = 0;
    }

    public int ParseExpression()
    {
        int left = ParseTerm();

        while (position < expression.Length)
        {
            char op = expression[position];
            position++;

            int right = ParseTerm();

            if (op == '+')
            {
                left += right;
            }
            else if (op == '-')
            {
                left -= right;
            }
            else
            {
                throw new ArgumentException($"Unknown operator: {op}");
            }
        }

        return left;
    }

    private int ParseTerm()
    {
        int number = 0;
        bool parsingNumber = false;
        bool isNegative = false;

        while (position < expression.Length)
        {
            char c = expression[position];

            if (char.IsDigit(c))
            {
                number = number * 10 + (int)char.GetNumericValue(c);
                parsingNumber = true;
            }
            else if (c == '+')
            {
                if (parsingNumber)
                {
                    position--;
                    break;
                }
                else
                {
                    throw new ArgumentException("Invalid expression: two consecutive operators");
                }
            }
            else if (c == '-')
            {
                if (parsingNumber)
                {
                    position--;
                    break;
                }
                else if (!isNegative)
                {
                    isNegative = true;
                }
                else
                {
                    throw new ArgumentException("Invalid expression: two consecutive operators");
                }
            }

            position++;
        }

        return isNegative ? -number : number;
    }
}

Шунтовый алгоритм

Шунтовый алгоритм использует стек для упорядочивания операторов и решения вопроса о приоритете. Он позволяет правильно обрабатывать выражения с учетом приоритета операций (например, умножение выполняется раньше сложения). Алгоритм построения нового выражения на базе исходного использует определенные правила и логику.

Пример использования шунтового алгоритма для вычисления значения выражения "2 + 3":

public class ExpressionParser
{
    private string expression;
    private int position;
    private Stack<int> numberStack;
    private Stack<char> operatorStack;

    public ExpressionParser(string expression)
    {
        this.expression = expression;
        this.position = 0;
        this.numberStack = new Stack<int>();
        this.operatorStack = new Stack<char>();
    }

    public int ParseExpression()
    {
        while (position < expression.Length)
        {
            char c = expression[position];

            if (char.IsDigit(c))
            {
                int number = ParseNumber();
                numberStack.Push(number);
            }
            else if (c == '+' || c == '-')
            {
                ProcessOperator(c);
            }

            position++;
        }

        while (operatorStack.Count > 0)
        {
            ApplyOperator();
        }

        return numberStack.Pop();
    }

    private int ParseNumber()
    {
        int number = (int)char.GetNumericValue(expression[position]);

        while (position + 1 < expression.Length && char.IsDigit(expression[position + 1]))
        {
            number = number * 10 + (int)char.GetNumericValue(expression[position + 1]);
            position++;
        }

        return number;
    }

    private void ProcessOperator(char op)
    {
        while (operatorStack.Count > 0 && operatorStack.Peek() != '(')
        {
            ApplyOperator();
        }

        operatorStack.Push(op);
    }

    private void ApplyOperator()
    {
        int right = numberStack.Pop();
        int left = numberStack.Pop();
        char op = operatorStack.Pop();

        switch (op)
        {
            case '+':
                numberStack.Push(left + right);
                break;
            case '-':
                numberStack.Push(left - right);
                break;
            default:
                throw new ArgumentException($"Unknown operator: {op}");
        }
    }
}

Библиотеки для парсинга выражений в C#

Помимо классического подхода, существуют специализированные библиотеки, которые облегчают задачу парсинга выражений в C#. Некоторые из самых популярных библиотек в этой области включают:

NCalc: это библиотека, которая позволяет анализировать и вычислять математические формулы, логические операторы и функции. Она поддерживает переменные, пользовательские функции, а также возможность создания пользовательских операторов.

using NCalc;

string expression = "2 * (3 + 1)";
Expression e = new Expression(expression);
object result = e.Evaluate();

Console.WriteLine(result); // Output: 8

Sprache: это библиотека, разработанная для парсинга естественного языка. Она предоставляет удобные синтаксические конструкции, такие как Parse.Char('a'), Parse.String("abc") и другие, позволяя построить грамматику для парсинга выражений.

using Sprache;

var number = Parse.Number.Select(int.Parse);
var sum = number.Then(n => Parse.Char('+').Then(_ => number)).Select(tuple => tuple.Item1 + tuple.Item2);

var result = sum.Parse("2 + 3");

Console.WriteLine(result); // Output: 5

Irony: это инструмент для создания собственных компиляторов и интерпретаторов, который предоставляет простой в использовании API для создания языков и их анализаторов.

using Irony.Parsing;

Grammar grammar = new Grammar();

grammar.NonTerminals.Add(new NonTerminal("expression")
    .Rule
    .Number()
    .Or(
        new NonTerminal("expression").Plus()
        .Add("+")
        .Add(grammar.NonTerminals["expression"])
    ));

Parser parser = new Parser(grammar);

ParseTree parseTree = parser.Parse("2 + 3");

Console.WriteLine(parseTree.Root); // Output: expression

Заключение

Парсинг выражений является важной задачей при разработке программного обеспечения на языке C#. В этой статье мы рассмотрели классический подход к парсингу, а также представили некоторые популярные библиотеки, которые могут использоваться для упрощения этой задачи. В зависимости от требований проекта вам может потребоваться использовать один из этих способов или создать свое собственное решение.