Разбор матэматычных выразаў на 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. На гэтым будзем заканчваць разбор алгарытму сартавальнай станцыі, і, не губляючы часу, пераходзім да алгарытму такенізацыі, які апісаны ў наступным пасце.