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

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

Данный алгоритм предназначен для преобразования выражений из инфиксной нотации в постфиксную. В данном посте не будет приводиться полное доказательство работы данного алгоритма, а лишь даны частичные пояснения, чтобы сделать реализацию более интуитивно понятной.

Начнём с самых простых примеров: применение бинарного оператора к операндам. Например, для выражение 2 + 3 аналогичным выражением в постфиксной нотации будет 2 3 +. То же будет верно для других бинарных операторов. Попробуем составить простую модель на C# для работы с такими выражениями:

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

public class ShuntingYardAlgorithm
{
    public ShuntingYardAlgorithm()
    {
        _operatorStorage = null;
        _postfixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Apply(IEnumerable<IToken> infixNotationTokens)
    {
        foreach (var token in infixNotationTokens)
        {
            ProcessToken(token);
        }
        return GetResult();
    }

    private void ProcessToken(IToken token)
    {
        switch (token)
        {
            case OperandToken operandToken:
                StoreOperand(operandToken);
                break;
            case OperatorToken operatorToken:
                PushOperator(operatorToken);
                break;
            default:
                var exMessage = $"An unknown token type: {token.GetType().ToString()}.";
                throw new SyntaxException(exMessage);
        }
    }

    private void StoreOperand(OperandToken operandToken)
    {
        _postfixNotationTokens.Add(operandToken);
    }

    private void PushOperator(OperatorToken operatorToken)
    {
        _operatorStorage = operatorToken;
    }

    private List<IToken> GetResult()
    {
        if (_operatorStorage.HasValue)
        {
            _postfixNotationTokens.Add(_operatorStorage.Value);
        }
        return _postfixNotationTokens;
    }

    private OperatorToken? operatorStorage;
    private readonly List<IToken> _postfixNotationTokens;
}

Всё это работает великолепно до того момента, пока мы не захотим усложнить исходное выражение и добавить ещё один оператор 2 + 3 - 4. В данном случае аналогичным постфиксным выражением будет 2 3 + 4 -. Заметим, что предыдущий алгоритм не может сохранять больше одного оператора во временном хранилище, таким образом мы потеряем один оператор в процессе вычисления и в результате получим 2 3 4 -. Это не может не огорчать, поэтому попробуем внести улучшение в наш алгоритм преобразования.

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

public class ShuntingYardAlgorithm
{
    public ShuntingYardAlgorithm()
    {
        _operatorStorage = null;
        _postfixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Apply(IEnumerable<IToken> infixNotationTokens)
    {
        foreach (var token in infixNotationTokens)
        {
            ProcessToken(token);
        }
        return GetResult();
    }

    private void ProcessToken(IToken token)
    {
        switch (token)
        {
            case OperandToken operandToken:
                StoreOperand(operandToken);
                break;
            case OperatorToken operatorToken:
                PushOperator(operatorToken);
                break;
            default:
                var exMessage = $"An unknown token type: {token.GetType().ToString()}.";
                throw new SyntaxException(exMessage);
        }
    }

    private void StoreOperand(OperandToken operandToken)
    {
        _postfixNotationTokens.Add(operandToken);
    }

    private void PushOperator(OperatorToken operatorToken)
    {
        if (_operatorStorage.HasValue)
        {
            _postfixNotationTokens.Add(_operatorStorage.Value);
        }
        _operatorStorage = operatorToken;
    }

    private List<IToken> GetResult()
    {
        if (_operatorStorage.HasValue)
        {
            _postfixNotationTokens.Add(_operatorStorage.Value);
        }
        return _postfixNotationTokens;
    }

    private OperatorToken? operatorStorage;
    private readonly List<IToken> _postfixNotationTokens;
}

Красота! Но что же делать, если операторы имеют разный приоритет? 2 + 3 * 4 выражение должно быть преобразовано к выражению 2 3 4 * +, но никак не к выражению 2 3 + 4 *. Для дальнейшего улучшения алгоритма рассмотрим также выражение 2 * 3 + 4 и его аналог 2 3 * 4 +. Отсюда мы можем сделать вывод, что наш алгоритм не работает только для случаев, когда следующий оператор имеет более высокий приоритет, чем предыдущий. Причём в случае, когда следующий оператор имеет более высокий приоритет, операторы должны как бы поменяться местами в результирующем выражении. Отсюда напрашивается вывод, что необходимо для хранилища операторов использовать стек, внесём очередное изменение в наш алгоритм:

• Пока выражение имеет токены берём очередной токен:
  • Если токен является операндом, то записываем его в результирующую последовательность;
  • Если токен является оператором, то запоминаем его в отдельном хранилище. Если хранилище содержит другой оператор, то записываем сохранённый оператор в результирующую последовательность, а новый оператор сохраняем в хранилище.
  • Если токен является оператором, то:
    • Пока стек операторов не пустой, и в вершине стека лежит оператор с не меньшим (>=) приоритетом, достаём его из стека и записываем в результирующую последовательность;
    • Сохраняем токен в стек операторов.
• Достаём сохранённый токен из хранилища и добавляем его сохраненные операторы из стека операторов и добавляем их в результирующее выражение.

public class ShuntingYardAlgorithm
{
    public ShuntingYardAlgorithm()
    {
        _operatorsStack = new Stack<OperatorToken>();
        _postfixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Apply(IEnumerable<IToken> infixNotationTokens)
    {
        foreach (var token in infixNotationTokens)
        {
            ProcessToken(token);
        }
        return GetResult();
    }

    private void ProcessToken(IToken token)
    {
        switch (token)
        {
            case OperandToken operandToken:
                StoreOperand(operandToken);
                break;
            case OperatorToken operatorToken:
                PushOperator(operatorToken);
                break;
            default:
                var exMessage = $"An unknown token type: {token.GetType().ToString()}.";
                throw new SyntaxException(exMessage);
        }
    }

    private void StoreOperand(OperandToken operandToken)
    {
        _postfixNotationTokens.Add(operandToken);
    }

    private void PushOperator(OperatorToken operatorToken)
    {
        var operatorPriority = GetOperatorPriority(operatorToken);

        while (_operatorsStack.Count > 0)
        {
            var stackOperatorToken = _operatorsStack.Peek();
            var stackOperatorPriority = GetOperatorPriority(stackOperatorToken);
            if (stackOperatorPriority < operatorPriority)
            {
                break;
            }

            _postfixNotationTokens.Add(_operatorsStack.Pop());
        }

        _operatorsStack.Push(operatorToken);
    }

    private int GetOperatorPriority(OperatorToken operatorToken)
    {
        switch (operatorToken.OperatorType)
        {
            case OperatorType.Addition:
            case OperatorType.Subtraction:
                return 1;
            case OperatorType.Multiplication:
            case OperatorType.Division:
                return 2;
            default:
                var exMessage = "An unexpected action for the operator: " +
                    $"{operatorToken.OperatorType}.";
                throw new SyntaxException(exMessage);
        }
    }

    private List<IToken> GetResult()
    {
        while (_operatorsStack.Count > 0)
        {
            var token = _operatorsStack.Pop();
            _postfixNotationTokens.Add(token);
        }
        return _postfixNotationTokens.ToList();
    }

    private readonly Stack<OperatorToken> _operatorsStack;
    private readonly List<IToken> _postfixNotationTokens;
}

Остался последний штрих — добавить подержку скобок, которые могут менять приоритет выполнения операций. Рассмотрим следующее выражение (2 + 3 * 4) / 5 и аналогичное выражение в постфиксной нотации 2 3 4 * + 5 /. Другими словами, выражение в скобках должно быть расчитано перед выполнением деления. Расшририм список возможных операторов скобочными операторами порядка:

public enum OperatorType
{
    Addition,
    Subtraction,
    Multiplication,
    Division,
    OpeningBracket,
    ClosingBracket
}

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

• Пока выражение имеет токены берём очередной токен:
  • Если токен является операндом, то записываем его в результирующую последовательность;
  • Если токен является оператором вычисления (не скобочным), то:
    • Пока стек операторов не пустой, и в вершине стека лежит оператор с не меньшим (>=) приоритетом, достаём его из стека и записываем в результирующую последовательность;
    • Сохраняем токен в стек операторов.
  • Если токен является открывающайся скобкой, то сохраняем оператор в стек операторов;
  • Если токен является закрывающайся скобкой, то достаем операторы из стека операторов и сохраняем в результирующую последовательность, пока не встретим открывающуюся скобку. Если открывающаяся скобка не была обнаружена, то сигнализируем об ошибке в выражении.
• Достаём сохраненные операторы из стека операторов и добавляем их в результирующее выражение. Если среди операторов есть открывающаяся скобка, то сигнализируем об ошибке в выражении.

public class ShuntingYardAlgorithm
{
    public ShuntingYardAlgorithm()
    {
        _operatorsStack = new Stack<OperatorToken>();
        _postfixNotationTokens = new List<IToken>();
    }

    public IEnumerable<IToken> Apply(IEnumerable<IToken> infixNotationTokens)
    {
        Reset();
        foreach (var token in infixNotationTokens)
        {
            ProcessToken(token);
        }
        return GetResult();
    }

    private void Reset()
    {
        _operatorsStack.Clear();
        _postfixNotationTokens.Clear();
    }


    private void ProcessToken(IToken token)
    {
        switch (token)
        {
            case OperandToken operandToken:
                StoreOperand(operandToken);
                break;
            case OperatorToken operatorToken:
                ProcessOperator(operatorToken);
                break;
            default:
                var exMessage = $"An unknown token type: {token.GetType().ToString()}.";
                throw new SyntaxException(exMessage);
        }
    }

    private void StoreOperand(OperandToken operandToken)
    {
        _postfixNotationTokens.Add(operandToken);
    }

    private void ProcessOperator(OperatorToken operatorToken)
    {
        switch (operatorToken.OperatorType)
        {
            case OperatorType.OpeningBracket:
                PushOpeningBracket(operatorToken);
                break;
            case OperatorType.ClosingBracket:
                PushClosingBracket(operatorToken);
                break;
            default:
                PushOperator(operatorToken);
                break;
        }
    }

    private void PushOpeningBracket(OperatorToken operatorToken)
    {
        _operatorsStack.Push(operatorToken);
    }

    private void PushClosingBracket(OperatorToken operatorToken)
    {
        bool openingBracketFound = false;

        while (_operatorsStack.Count > 0)
        {
            var stackOperatorToken = _operatorsStack.Pop();
            if (stackOperatorToken.OperatorType == OperatorType.OpeningBracket)
            {
                openingBracketFound = true;
                break;
            }

            _postfixNotationTokens.Add(stackOperatorToken);
        }

        if (!openingBracketFound)
        {
            throw new SyntaxException("An unexpected closing bracket.");
        }
    }

    private void PushOperator(OperatorToken operatorToken)
    {
        var operatorPriority = GetOperatorPriority(operatorToken);

        while (_operatorsStack.Count > 0)
        {
            var stackOperatorToken = _operatorsStack.Peek();
            if (stackOperatorToken.OperatorType == OperatorType.OpeningBracket)
            {
                break;
            }

            var stackOperatorPriority = GetOperatorPriority(stackOperatorToken);
            if (stackOperatorPriority < operatorPriority)
            {
                break;
            }

            _postfixNotationTokens.Add(_operatorsStack.Pop());
        }

        _operatorsStack.Push(operatorToken);
    }

    private int GetOperatorPriority(OperatorToken operatorToken)
    {
        switch (operatorToken.OperatorType)
        {
            case OperatorType.Addition:
            case OperatorType.Subtraction:
                return 1;
            case OperatorType.Multiplication:
            case OperatorType.Division:
                return 2;
            default:
                var exMessage = "An unexpected action for the operator: " +
                    $"{operatorToken.OperatorType}.";
                throw new SyntaxException(exMessage);
        }
    }

    private List<IToken> GetResult()
    {
        while (_operatorsStack.Count > 0)
        {
            var token = _operatorsStack.Pop();
            if (token.OperatorType == OperatorType.OpeningBracket)
            {
                throw new SyntaxException("A redundant opening bracket.");
            }
            _postfixNotationTokens.Add(token);
        }
        return _postfixNotationTokens.ToList();
    }

    private readonly Stack<OperatorToken> _operatorsStack;
    private readonly List<IToken> _postfixNotationTokens;
}

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