Разбор математических выражений на C#. Токенизация

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

Как упоминалось в предыдущих постах про постфиксную нотацию и алгоритм сортировочной станции, мы имеем следующие виды токенов:

1. Знаки арифметических операций +, -, *, /;
2. Круглые скобки (, );
3. Вещественные числа. Для простоты ограничимся только числами с десятичным разделителем;
4. В качестве разделителей токенов может выступать только символ пробела.

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

public class Tokenizer
{
    public IEnumerable<IToken> Parse(string expression)
    {
        foreach (char next in expression)
        {
            FeedCharacter(next);
        }
        return GetResult();
    }
}

Для начала реализуем самый простой вариант: входная строка содержит только одно число, пробелы и операторы отсутствуют.

• Пока есть символы, добавляем символы в отдельное хранилище, на основе которых будем формировать результирующее число;
• Если в хранилище есть символы, то конвертируем символы в число и добавляем в список результирующих токенов.

public class Tokenizer
{
    public Tokenizer()
    {
        _valueTokenBuilder = new StringBuilder();
        _infixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Parse(string expression)
    {
        foreach (char next in expression)
        {
            FeedCharacter(next);
        }
        return GetResult();
    }

    private void FeedCharacter(char next)
    {
        _valueTokenBuilder.Append(next);
    }

    private IToken CreateOperandToken(string raw)
    {
        if (double.TryParse(raw, out double result))
        {
            return new OperandToken(result);
        }

        throw new SyntaxException($"The operand {raw} has an invalid format.");
    }

    private IEnumerable<IToken> GetResult()
    {
        if (_valueTokenBuilder.Length > 0)
        {
            var token = CreateOperandToken(_valueTokenBuilder.ToString());
            _valueTokenBuilder.Clear();
            _infixNotationTokens.Add(token);
        }

        return _infixNotationTokens.ToList();
    }

    private readonly StringBuilder _valueTokenBuilder;
    private readonly List<IToken> _infixNotationTokens;
}

Усложним немного задачу: разрешим использование нескольких чисел, разделенных пробелами. Тогда разбиение на токены можно представить в следующем виде:

• Пока есть символы, анализируем очередной символ:
  • Если символ является разделителем (пробелом), то конвертируем сохраненные в хранилище символы в число и добавляем в список результирующих токенов;
  • Иначе используем символ для формирования числа в отдельном хранилище;
• Если в хранилище остались символы, то конвертируем символы в число и добавляем в список результирующих токенов.

public class Tokenizer
{
    public Tokenizer()
    {
        _valueTokenBuilder = new StringBuilder();
        _infixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Parse(string expression)
    {
        foreach (char next in expression)
        {
            FeedCharacter(next);
        }
        return GetResult();
    }

    private void FeedCharacter(char next)
    {
        if (IsSpacingCharacter(next))
        {
            if (_valueTokenBuilder.Length > 0)
            {
                var token = CreateOperandToken(_valueTokenBuilder.ToString());
                _valueTokenBuilder.Clear();
                _infixNotationTokens.Add(token);
            }
        }
        else
        {
            _valueTokenBuilder.Append(next);
        }
    }

    private bool IsSpacingCharacter(char c)
    {
        switch (c)
        {
            case ' ':
                return true;
            default:
                return false;
        }
    }

    private IToken CreateOperandToken(string raw)
    {
        if (double.TryParse(raw, out double result))
        {
            return new OperandToken(result);
        }

        throw new SyntaxException($"The operand {raw} has an invalid format.");
    }

    private IEnumerable<IToken> GetResult()
    {
        if (_valueTokenBuilder.Length > 0)
        {
            var token = CreateOperandToken(_valueTokenBuilder.ToString());
            _valueTokenBuilder.Clear();
            _infixNotationTokens.Add(token);
        }

        return _infixNotationTokens.ToList();
    }

    private readonly StringBuilder _valueTokenBuilder;
    private readonly List<IToken> _infixNotationTokens;
}

Добавим теперь поддержку обработки операторов. Так как в нашей постановки задачи все операторы выражаются ровно одним символом, то при встрече символа оператора будем сразу добавлять оператор в результирующую последовательность. При этом если в хранилище содержатся символы для формирования числа, то конвертируем их в число. Тогда финальный алгоритм будет выглядеть следующим образом:

• Пока есть символы, анализируем очередной символ:
  • Если символ является разделителем (пробелом), то конвертируем сохраненные в хранилище символы в число и добавляем в список результирующих токенов;
  • Если символ является оператором, то конвертируем сохраненные в хранилище символы в число и добавляем в список результирующих токенов, после чело добавляем токен оператора в результирующий список;
  • Иначе используем символ для формирования числа в отдельном хранилище;
• Если в хранилище остались символы, то конвертируем символы в число и добавляем в список результирующих токенов.

public class Tokenizer
{
    public Tokenizer()
    {
        _valueTokenBuilder = new StringBuilder();
        _infixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Parse(string expression)
    {
        foreach (char next in expression)
        {
            FeedCharacter(next);
        }
        return GetResult();
    }

    private void FeedCharacter(char next)
    {
        if (IsSpacingCharacter(next))
        {
            if (_valueTokenBuilder.Length > 0)
            {
                var token = CreateOperandToken(_valueTokenBuilder.ToString());
                _valueTokenBuilder.Clear();
                _infixNotationTokens.Add(token);
            }
        }
        else if (IsOperatorCharacter(next))
        {
            if (_valueTokenBuilder.Length > 0)
            {
                var token = CreateOperandToken(_valueTokenBuilder.ToString());
                _valueTokenBuilder.Clear();
                _infixNotationTokens.Add(token);
            }

            var operatorToken = CreateOperatorToken(next);
            _infixNotationTokens.Add(operatorToken);
        }
        else
        {
            _valueTokenBuilder.Append(next);
        }
    }

    private bool IsOperatorCharacter(char c)
    {
        switch (c)
        {
            case '(':
            case ')':
            case '+':
            case '-':
            case '*':
            case '/':
                return true;
            default:
                return false;
        }
    }

    private bool IsSpacingCharacter(char c)
    {
        switch (c)
        {
            case ' ':
                return true;
            default:
                return false;
        }
    }

    private IToken CreateOperandToken(string raw)
    {
        if (double.TryParse(raw, out double result))
        {
            return new OperandToken(result);
        }

        throw new SyntaxException($"The operand {raw} has an invalid format.");
    }

    private OperatorToken CreateOperatorToken(char c)
    {
        switch (c)
        {
            case '(': return new OperatorToken(OperatorType.OpeningBracket);
            case ')': return new OperatorToken(OperatorType.ClosingBracket);
            case '+': return new OperatorToken(OperatorType.Addition);
            case '-': return new OperatorToken(OperatorType.Subtraction);
            case '*': return new OperatorToken(OperatorType.Multiplication);
            case '/': return new OperatorToken(OperatorType.Division);
            default:
                throw new SyntaxException($"There's no a suitable operator for the char {c}");
        }
    }

    private IEnumerable<IToken> GetResult()
    {
        if (_valueTokenBuilder.Length > 0)
        {
            var token = CreateOperandToken(_valueTokenBuilder.ToString());
            _valueTokenBuilder.Clear();
            _infixNotationTokens.Add(token);
        }

        return _infixNotationTokens.ToList();
    }

    private readonly StringBuilder _valueTokenBuilder;
    private readonly List<IToken> _infixNotationTokens;
}

Как всегда полную реализацию можно посмотреть на GitHub проекта coding-interview, а этим постом будем заканчивать тему разбора математических выражений. Надеюсь, что всё было познавательно и интересно. До встречи!