Разбор матэматычных выразаў на C#. Постфіксная натацыя
Прывітанне, паважаны чытач!
Хто ж, як не мы, прапаленыя жыццём і маніторам распрацоўнікі, ведае які супярэчлівы, цяжкі і несправядлівы гэты свет тэхнічных сумоўяў! Хай твае рашэнні запускаюць касмічныя караблі, або твой сэрвіс утрымлівае мільёны запытаў, дасведчаны інтэрв’юер заўсёды выведзе цябе на чыстую ваду. Не можаш з ходу ўзгадаць розніцу паміж сартаваннем зліццём і ўстаўкамі, не ведаеш на памяць усе SOLID прынцыпы? О, сябар мой, у адрозненне ад цябе інтэрв’юер падрыхтаваўся сур’ёзней і яшчэ з раніцы паўтарыў гэтыя важныя тэмы. Твая некампетэнтнасць відавочна. Пераздача!
Вядома ў наступны раз гэтыя пытанні не заспеюць цябе знянацку, ты сам зараз дзівішся, як чалавек не можа адразу рэалізаваць сартаванне кучай, або на памяць не ведае ўсе правілы балансавання чырвона-чорных дрэў. Цябе зноў клічуць на сумоўе, і якое дзіўнае супадзенне: зноў трапляецца той жа інтэрв’юер. Вось ён момант ісціны, цяпер ты ведаеш пра сартаванні ўсё, ты ўжо гатовы ўдарыць па клавішах, як нечакана чытаеш пастаноўку пытання: “Рэалізаваць парсер матэматычных выразаў”.
Нечакана? Так і ёсць! І таму, каб у гэты раз усё атрымалася, прапаную прама тут і цяпер разабрацца з гэтым пытаннем. Такім чынам, прыступім!
Пастаноўка задачы: рэалізаваць парсер матэматычных выразаў.
Вядома з такой фармулёўкай працаваць складана, таму пажадана на тэхнічных сумоўях прытрымлівацца правіла: спачатку абмеркаваць абмежаванні, потым прыступаць да рэалізацыі. Калі ёсць жаданне ўвесці інтэрв’юера ў стан экстазу, то варта прапанаваць зафіксаваць абмежаванні ў выглядзе набору тэстаў.
Увядзем наступны набор абмежаванняў:
- Выраз не можа ўтрымліваць пераменных або найменных канстант, складаецца толькі з лікаў, арыфметычных знакаў і дужак;
- Даступны наступныя арыфметычныя знакі:
+, -, *, /; - Даступны толькі круглыя дужкі;
- Калі ў выразе ёсць сінтаксічная або вылічальная памылка, то неабходна замест выніку вярнуць паведамленне пра памылку;
Складанасць разбору матэматычных выразаў заключаецца ў тым, што матэматычныя аперацыі маюць розны прыярытэт, які таксама можа змяняцца з дапамогай дужак. Гучыць складана? Насамрэч досыць пераўтварыць выраз з інфікснай натацыі ў постфіксную з дапамогай алгарытму сартавальнай станцыі, выканаць разлік і ўсё! Здаецца, можна на гэтым завяршаць пост, але хутчэй за ўсё злосны інтэрв’юер захоча паглыбіцца ў дэталі, а яшчэ, чаго добрага, запатрабуе рэалізацыі. Таму працягнем.
Інфіксная натацыя – форма запісу матэматычных выразаў, у якой аператары (у нашым выпадку арыфметычныя знакі) запісаны паміж аперандамі (у нашым выпадку лікамі), на якія яны прымяняюцца. Парадак вылічэнняў вызначаецца прыярытэтам аператараў, але можа рэгулявацца дужкамі. Такім чынам, інфіксная натацыя – гэта стандартная форма запісу выразаў, якой нас вывучалі яшчэ ў школе, напрыклад: 1 + (2 - 3) * 4.
Постфіксная натацыя – форма запісу матэматычных выразаў, у якой аператары запісаны пасля аперандаў, на якія яны прымяняюцца. У дадзенай натацыі адсутнічае прыярытэт аперацый, а таму адсутнічаюць дужкі. Напрыклад, выразу вышэй будзе адпавядаць наступны выраз у постфікснай натацыі: 2 3 - 4 * 1 + або 4 2 3 - * 1 +.
Поўную рэалізацыю на C# можна знайсці на GitHub праекта coding-interview, а пакуль разбяром алгарытм вылічэння выразу, які запісаны ў постфікснай натацыі. Створым клас, які на ўваход будзе прымаць паслядоўнае мноства токенаў (аператараў і аперандаў), а на выхадзе будзе вяртаць вынік у выглядзе вылічанага аперанда.
public class PostfixNotationCalculator
{
public OperandToken Calculate(IEnumerable<IToken> tokens)
{
foreach (var token in tokens)
{
ProcessToken(token);
}
return GetResult();
}
private void ProcessToken(IToken token)
{
switch (token)
{
case OperandToken operandToken:
StoreOperand(operandToken);
break;
case OperatorToken operatorToken:
ApplyOperator(operatorToken);
break;
default:
var exMessage = $"An unknown token type: {token.GetType().ToString()}";
throw new SyntaxException(exMessage);
}
}
private void StoreOperand(OperandToken operandToken)
{
// Discussed below
}
private void ApplyOperator(OperatorToken operatorToken)
{
// Discussed below
}
private OperandToken GetResult()
{
// Discussed below
}
}
public interface IToken { }
public class OperandToken : IToken
{
public double Value { get { return _value; } }
public OperandToken(double value)
{
_value = value;
}
private readonly double _value;
}
public enum OperatorType
{
Addition,
Subtraction,
Multiplication,
Division
}
public class OperatorToken : IToken
{
public OperatorType OperatorType { get { return _operatorType; } }
public OperatorToken(OperatorType operatorType)
{
_operatorType = operatorType;
}
private OperatorType _operatorType;
}
public class MathExpressionException : Exception
{
public MathExpressionException(string message) : base(message)
{
}
}
public class SyntaxException : MathExpressionException
{
public SyntaxException(string message) : base(message)
{
}
}Калі токен з’яўляецца аперандам, то дадаем аперанд у стэк аперандаў.
public class PostfixNotationCalculator
{
public PostfixNotationCalculator()
{
_operandTokensStack = new Stack<OperandToken>();
}
// ...
private void StoreOperand(OperandToken operandToken)
{
_operandTokensStack.Push(operandToken);
}
// ...
private Stack<OperandToken> _operandTokensStack;
}
Калі ж токен з’яўляецца аператарам, то дастаем неабходную колькасць аперандаў са стэку, вырабляем вылічэнне і дадаем вынік вылічэння ў стэк аперандаў. Калі ж у стэку няма неабходнага ліку элементаў для вылічэнні аператара, то сігналізуем пра памылку.
public class PostfixNotationCalculator
{
// ...
private void ApplyOperator(OperatorToken operatorToken)
{
switch (operatorToken.OperatorType)
{
case OperatorType.Addition:
ApplyAdditionOperator();
break;
case OperatorType.Subtraction:
ApplySubtractionOperator();
break;
case OperatorType.Multiplication:
ApplyMultiplicationOperator();
break;
case OperatorType.Division:
ApplyDivisionOperator();
break;
default:
var exMessage = $"An unknown operator type: {operatorToken.OperatorType}.";
throw new SyntaxException(exMessage);
}
}
private void ApplyAdditionOperator()
{
var operands = GetBinaryOperatorArguments();
var result = new OperandToken(operands.Item1.Value + operands.Item2.Value);
_operandTokensStack.Push(result);
}
private void ApplySubtractionOperator()
{
var operands = GetBinaryOperatorArguments();
var result = new OperandToken(operands.Item1.Value - operands.Item2.Value);
_operandTokensStack.Push(result);
}
private void ApplyMultiplicationOperator()
{
var operands = GetBinaryOperatorArguments();
var result = new OperandToken(operands.Item1.Value * operands.Item2.Value);
_operandTokensStack.Push(result);
}
private void ApplyDivisionOperator()
{
var operands = GetBinaryOperatorArguments();
var result = new OperandToken(operands.Item1.Value / operands.Item2.Value);
_operandTokensStack.Push(result);
}
private Tuple<OperandToken, OperandToken> GetBinaryOperatorArguments()
{
if (_operandTokensStack.Count < 2)
{
var exMessage = "Not enough arguments for applying a binary operator.";
throw new SyntaxException(exMessage);
}
var right = _operandTokensStack.Pop();
var left = _operandTokensStack.Pop();
return Tuple.Create(left, right);
}
// ...
}Засталося толькі дадаць рэалізацыю вяртання выніку – адзінага элемента ў стэку. Калі пасля апрацоўкі ўсіх токенаў ў стэку знаходзіцца больш за адзін элемент, то гэта будзе сігналізаваць аб неадпаведнасці паміж аператарамі і аперандамі. Калі ж у стэку няма элементаў, то гэта значыць, што на ўваход была пададзена пустая паслядоўнасць.
class PostfixNotationCalculator
{
// ...
private OperandToken GetResult()
{
if (_operandTokensStack.Count == 0)
{
var exMessage = "The expression is invalid." +
" Check, please, that the expression is not empty.";
throw new SyntaxException(exMessage);
}
if (_operandTokensStack.Count != 1)
{
var exMessage = "The expression is invalid." +
" Check, please, that you're providing the full expression and" +
" the tokens have a correct order.";
throw new SyntaxException(exMessage);
}
return _operandTokensStack.Pop();
}
// ...
}На гэтым мне трэба развітвацца, а ўжо ў наступным пасце разбяром рэалізацыю алгарытму сартавальнай станцыі.
