Разбор математических выражений на 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();
}
// ...
}На этом мне надо прощаться, а уже в следующем посте разберём реализацию алгоритма сортировочной станции.
