В первой части был написан лексер, а во второй части — парсер. Далее будет рассмотрена разработка вычислителя и фасада для всего интерпретатора, а также рефакторинг кода для устранения дублирования.
Вычислитель
Приступим к самому интересному. Вычисление выражения в постфиксной записи можно осуществить двумя способами: через рекурсию, неявно используя стек процесса, или используя явный стек. Реализуем второй вариант. Алгоритм с использованием явного стека такой:
- Если на вход подан операнд, он помещается на вершину стека.
- Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
- После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.
В данной статье я не буду реализовывать контекст выполнения и вычисление нескольких выражений. Поэтому начальный список тестов будет коротким:
- Если на входе пустой список, возвращаем 0.
- Если на входе список с одним числом, возвращаем это число.
- Если на входе [1 2 +], возвращаем 3.
Создадим новый тестовый класс и добавим первый тест.
TEST_CLASS(EvaluatorTests) {
public:
TEST_METHOD(Should_return_zero_when_evaluate_empty_list) {
double result = Evaluator::Evaluate({});
Assert::AreEqual(0.0, result);
}
};
Привычно добавим пустую функцию в необходимое пространство имён.
namespace Evaluator {
inline double Evaluate(Tokens) { return 0; }
} // namespace Evaluator
Напишем второй тест.
TEST_METHOD(Should_return_number_when_evaluate_list_with_number) {
double result = Evaluator::Evaluate({ _1 });
Assert::AreEqual(1.0, result);
}
Просто возвращаем, то что было в списке последним. Можно было бы поступить проще, но потом всё равно нужно будет добавлять цикл.
inline double Evaluate(const Tokens &tokens) {
double result = 0;
for(const Token &token : tokens) {
result = token;
}
return result;
}
Дальше — сложнее. Попробуем вычислить выражение с одним оператором.
TEST_METHOD(Should_eval_expression_with_one_operator) {
double result = Evaluator::Evaluate({ _1, _2, plus });
Assert::AreEqual(3.0, result);
}
Для того, чтобы этот тест прошёл, добавим всего один символ к коду.
for(const Token &token : tokens) {
if(token.Type() == TokenType::Number) {
result += token;
}
}
Этого было достаточно для прохождения теста. Попробуем сломать данный алгоритм, вычислив результат умножения.
TEST_METHOD(Should_eval_expression_with_one_multiplication) {
double result = Evaluator::Evaluate({ _2, _3, mul });
Assert::AreEqual(6.0, result);
}
Тест не проходит, так как у нас жёстко забито сложение. Необходима более сложная реализация, учитывающая тип оператора. Добавим ветвление и заменим переменную с результатом на контейнер.
inline double Evaluate(const Tokens &tokens) {
std::vector<double> result{ 0 };
auto pop = [&]() { double d = result.back(); result.pop_back(); return d; };
for(const Token &token : tokens) {
if(token.Type() == TokenType::Number) {
result.push_back(token);
}
else if(token == Token(Operator::Plus)) {
result.push_back(pop() + pop());
}
else if(token == Token(Operator::Mul)) {
result.push_back(pop() * pop());
}
}
return pop();
}
Заметим, что данный алгоритм уже может выполнять и более сложные вычисления. Сделаем тест оператора минус. Его сложность в том, что можно перепутать местами аргументы, извлекая их из стека.
TEST_METHOD(Should_eval_expression_with_one_subtraction) {
double result = Evaluator::Evaluate({ _2, _3, minus });
Assert::AreEqual(-1.0, result);
}
Вообще, согласно стандарту C++, нельзя делать какие-либо предположения относительно порядка вычисления аргументов функции. Поэтому извлекать операнды из стека нужно в явной последовательности.
…
else if(token == Token(Operator::Minus)) {
double d = pop();
result.push_back(pop() - d);
}
Аналогичный тест для деления.
TEST_METHOD(Should_eval_expression_with_one_division) {
double result = Evaluator::Evaluate({ _5, _2, div });
Assert::AreEqual(2.5, result);
}
В начале я написал тест на деление, используя выражение 4/2=2, и он сразу же прошёл, несмотря на то, что операция деления не была добавлена. Это произошло по той причине, что из стека извлекалось последнее добавленное в него число, которое, по совпадению, оказалось равно результату выражения. Именно поэтому тесты сразу после написания должны падать, иначе есть большая вероятность того, что тест ничего на самом деле не тестирует.
…
else if(token == Token(Operator::Div)) {
double d = pop();
result.push_back(pop() / d);
}
Чтобы удостовериться, что всё работает так как надо, добавим последний тест на вычисление сложного выражения.
TEST_METHOD(Should_eval_complex_expression) {
// (4+1)*2/(4/(3-1)) = 4 1 + 2 * 4 3 1 - / / = 5
double result = Evaluator::Evaluate({ _4, _1, plus, _2, mul, _4, _3, _1, minus, div, div });
Assert::AreEqual(5.0, result);
}
Он проходит, но так и было задумано. В нашей функции довольно много дублирования. Вынесем её в отдельный класс и отрефакторим.
inline double Evaluate(const Tokens &tokens) {
Detail::StackEvaluator evaluator(tokens);
evaluator.Evaluate();
return evaluator.Result();
}
namespace Detail {
class StackEvaluator {
public:
StackEvaluator(const Tokens &tokens) : m_current(tokens.cbegin()), m_end(tokens.cend()) {}
void Evaluate() {
for(; m_current != m_end; ++m_current) {
EvaluateCurrentToken();
}
}
double Result() const { return m_stack.empty() ? 0 : m_stack.back(); }
private:
void EvaluateCurrentToken() {
switch(m_current->Type()) {
case TokenType::Operator:
EvaluateOperator();
break;
case TokenType::Number:
EvaluateNumber();
break;
default:
throw std::out_of_range("TokenType");
}
}
void EvaluateOperator() {
double second = PopOperand();
double first = PopOperand();
m_stack.push_back(BinaryFunctionFor(*m_current)(first, second));
}
void EvaluateNumber() {
m_stack.push_back(*m_current);
}
double PopOperand() {
double back = m_stack.back();
m_stack.pop_back();
return back;
}
static const std::function<double(double, double)> &BinaryFunctionFor(Operator op) {
static const std::map<Operator, std::function<double(double, double)>> functions{
{ Operator::Plus, std::plus<double>() },
{ Operator::Minus, std::minus<double>() },
{ Operator::Mul, std::multiplies<double>() },
{ Operator::Div, std::divides<double>() },
};
auto found = functions.find(op);
if(found == functions.cend()) {
throw std::logic_error("Operator not found.");
}
return found->second;
}
Tokens::const_iterator m_current, m_end;
std::vector<double> m_stack;
};
} // namespace Detail
Интерпретатор
Для упрощения работы со стороны клиента, напишем небольшую функцию, являющуюся фасадом для всего интерпретатора. Добавим для начала пару интеграционных тестов.
TEST_CLASS(InterpreterIntegrationTests) {
public:
TEST_METHOD(Should_interprete_empty_experssion) {
double result = Interpreter::InterpreteExperssion(L" ");
Assert::AreEqual(0.0, result);
}
TEST_METHOD(Should_interprete_experssion) {
double result = Interpreter::InterpreteExperssion(L"1+2");
Assert::AreEqual(3.0, result);
}
};
Напишем реализацию функции InterpreteExperssion в уже существующем пространстве имён Interpreter.
inline double InterpreteExperssion(const std::wstring &expression) {
return Evaluator::Evaluate(Parser::Parse(Lexer::Tokenize(expression)));
}
Ура, тесты проходят, значит все части интерпретатора взаимодействуют так, как и было запланировано.
Рефакторинг
Теперь, когда весь код покрыт тестами, можно посмотреть, есть ли дублирование в глобальном масштабе и устранить его. Сразу же бросается в глаза куча одинаковых операторов switch, выполняющих проверку на тип токена. Да и в самом токене одновременно хранится как число, так и оператор. Для того, чтобы уйти от условных операторов в каждом методе, воспользуемся шаблоном посетитель. Создадим абстрактный класс TokenVisitor:
struct TokenVisitor {
virtual void VisitNumber(double) {}
virtual void VisitOperator(Operator) {}
protected:
~TokenVisitor() {}
};
Для простоты, виртуальные методы будут иметь пустую реализацию по умолчанию. Для безопасности, объявим деструктор как защищённый и не виртуальный, чтобы предотвратить возможность удаления через указатель на этот класс. Добавим в токен метод, принимающий посетителя и перенесём в него злополучный switch.
void Accept(TokenVisitor &visitor) const {
switch(m_type) {
case TokenType::Operator:
visitor.VisitOperator(m_operator);
break;
case TokenType::Number:
visitor.VisitNumber(m_number);
break;
default: throw std::out_of_range("TokenType");
}
}
Теперь посмотрим на класс ShuntingYardParser и его метод ParseCurrentToken.
void ParseCurrentToken() {
switch(m_current->Type()) {
case TokenType::Operator:
ParseOperator();
break;
case TokenType::Number:
ParseNumber();
break;
default: throw std::out_of_range("TokenType");
}
}
Сходство очевидно. Унаследуем это класс от абстрактного посетителя и переименуем методы Parse* в Visit*. После этого класс изрядно похудеет, а метод Parse примет такой вид:
void Parse() {
for(; m_current != m_end; ++m_current) {
m_current->Accept(*this);
}
PopToOutputUntil([this]() {return StackHasNoOperators(); });
}
Аналогично поступим с классом StackEvaluator.
class StackEvaluator : TokenVisitor {
public:
void Evaluate(const Tokens &tokens) {
for(const Token &token : tokens) {
token.Accept(*this);
}
}
…
void VisitOperator(Operator op) override {
double second = PopOperand();
double first = PopOperand();
m_stack.push_back(BinaryFunctionFor(op)(first, second));
}
void VisitNumber(double number) override {
m_stack.push_back(number);
}
};
Можно было бы вообще не использовать наследование и виртуальные функции, заменив всё шаблонами, но тогда потеряется всякая поддержка со стороны IDE и придётся рассчитывать только на неявные соглашения. Теперь разберёмся с оставшимися операторами switch и union. Тут может пригодиться паттерн состояние, который, кстати, неявно использует std::function. Поступим по аналогии. Создадим закрытый абстрактный класс TokenConcept внутри класса токена, в котором будут располагаться операции, зависящие от типа токена. Конкретная реализация концепта будет храниться в std::shared_ptr, так как токен является неизменяемым, то делать состояние разделяемым совершенно безопасно.
struct TokenConcept {
virtual ~TokenConcept() {}
virtual void Accept(TokenVisitor &) const = 0;
virtual std::wstring ToString() const = 0;
virtual bool Equals(const TokenConcept &) const = 0;
virtual TokenType Type() const = 0;
virtual double ToNumber() const { throw std::logic_error("Invalid token type"); }
virtual Operator ToOperator() const { throw std::logic_error("Invalid token type"); }
};
Не будем пока что избавляться от TokenType полностью, чтобы не ломать тесты. Теперь добавим реализации для числа и оператора, после чего заменим логику в методах токена на обращение к концепту.
class Token {
struct TokenConcept {
virtual ~TokenConcept() {}
virtual void Accept(TokenVisitor &) const = 0;
virtual std::wstring ToString() const = 0;
virtual bool Equals(const TokenConcept &) const = 0;
virtual TokenType Type() const = 0;
virtual double ToNumber() const { throw std::logic_error("Invalid token type"); }
virtual Operator ToOperator() const { throw std::logic_error("Invalid token type"); }
};
struct NumberToken : TokenConcept {
NumberToken(double val) : m_number(val) {}
void Accept(TokenVisitor &visitor) const override { visitor.VisitNumber(m_number); }
std::wstring ToString() const override { return std::to_wstring(m_number); }
bool Equals(const TokenConcept &other) const override {
return other.Type() == Type() && other.ToNumber() == m_number;
}
TokenType Type() const override { return TokenType::Number; }
double ToNumber() const override { return m_number; }
private:
double m_number;
};
struct OperatorToken : TokenConcept {
OperatorToken(Operator val) : m_operator(val) {}
void Accept(TokenVisitor &visitor) const override { visitor.VisitOperator(m_operator); }
std::wstring ToString() const override { return Interpreter::ToString(m_operator); }
bool Equals(const TokenConcept &other) const override {
return other.Type() == Type() && other.ToOperator() == m_operator;
}
TokenType Type() const override { return TokenType::Operator; }
Operator ToOperator() const override { return m_operator; }
private:
Operator m_operator;
};
public:
Token(Operator val) : m_concept(std::make_shared<OperatorToken>(val)) {}
Token(double val) : m_concept(std::make_shared<NumberToken>(val)) {}
TokenType Type() const { return m_concept->Type(); }
void Accept(TokenVisitor &visitor) const { m_concept->Accept(visitor); }
operator Operator() const { return m_concept->ToOperator(); }
operator double() const { return m_concept->ToNumber(); }
friend inline bool operator==(const Token &left, const Token &right) {
return left.m_concept->Equals(*right.m_concept);
}
friend inline std::wstring ToString(const Token &token) {
return token.m_concept->ToString();
}
private:
std::shared_ptr<const TokenConcept> m_concept;
};
Заметим, что ни один тест в течение рефакторинга не сломался, хотя вид кода изменился довольно значительно. Пойдём дальше и удалим перечисление TokenType, так как оно используется только в классе Token. Перед этим изменим тесты Should_get_type_for_operator_token и Should_get_type_for_number_token так, чтобы они не использовали тип токена, немного подкорректировав их семантику.
TEST_METHOD(Should_check_for_equality_operator_tokens) {
Assert::AreEqual(minus, minus);
Assert::AreNotEqual(minus, plus);
Assert::AreNotEqual(minus, _1);
}
TEST_METHOD(Should_check_for_equality_number_tokens) {
Assert::AreEqual(_1, _1);
Assert::AreNotEqual(_1, _2);
Assert::AreNotEqual(_1, minus);
}
После удаления перечисления возникает проблема сравнения токенов разных типов. RTTY использовать не хочется, поэтому немного изменим базовый класс TokenConcept, добавив поддержку двойной диспетчеризации для операции Equals.
struct TokenConcept {
…
virtual bool Equals(const TokenConcept &other) const = 0;
virtual bool EqualsToNumber(double) const { return false; }
virtual bool EqualsToOperator(Operator) const { return false; }
};
struct NumberToken : TokenConcept {
…
bool EqualsToNumber(double value) const override { return value == m_number; }
bool Equals(const TokenConcept &other) const { return other.EqualsToNumber(m_number); }
};
struct OperatorToken : TokenConcept {
…
bool EqualsToOperator(Operator value) const override { return value == m_operator; }
bool Equals(const TokenConcept &other) const { return other.EqualsToOperator(m_operator); }
};
Производные классы в методе Equals выполняют первый шаг диспетчеризации для определения типа первого токена, после чего второй токен уже производит сравнение с конкретным типом токена. Токены разных типов не равны по умолчанию, поэтому производным классам нужно переопределить только один метод, принимающий аргумент подходящего типа.
Заключение
В этой статье я попытался отойти от привычной тематики материалов по TDD, сосредоточенных больше на теории и углубиться в практическое применение данной техники. Как было показано, даже на C++ можно вести разработку через тестирование без особых затруднений. Тем более, что начать это делать легко, учитывая наличие в Visual Studio встроенной поддержки тестов для C++ проектов. Конечно, для написания более сложных систем требуется и более сложные библиотеки, такие как Boost.Test, Google.Test, или CppUTest, а также библиотеки для создание mock-объектов, такие как Google.Mock, или Turtle. Да и не все сценарии можно протестировать только с помощью модульных тестов. Но, тем не менее, написание модульных тестов и разработка через тестирование заметно помогают в написании кода, упрощают его модификацию в будущем и придают уверенность в том, что всё работает именно так, как было запланировано.
При наличии интереса у читателей я могу написать вторую часть в подобном стиле, в которой будет описана реализация оставшихся пунктов из списка в начале первой части этой статьи.
Ресурсы
Ниже приведён весь код в конечном варианте:
#pragma once;
#include <vector>
#include <wchar.h>
#include <algorithm>
#include <functional>
#include <map>
#include <memory>
namespace Interpreter {
enum class Operator : wchar_t {
Plus = L'+',
Minus = L'-',
Mul = L'*',
Div = L'/',
LParen = L'(',
RParen = L')',
};
inline std::wstring ToString(const Operator &op) {
return{ static_cast<wchar_t>(op) };
}
struct TokenVisitor {
virtual void VisitNumber(double) {}
virtual void VisitOperator(Operator) {}
protected:
~TokenVisitor() {}
};
class Token {
struct TokenConcept {
virtual ~TokenConcept() {}
virtual void Accept(TokenVisitor &) const = 0;
virtual std::wstring ToString() const = 0;
virtual bool Equals(const TokenConcept &other) const = 0;
virtual bool EqualsToNumber(double) const {
return false;
}
virtual bool EqualsToOperator(Operator) const {
return false;
}
virtual double ToNumber() const {
throw std::logic_error("Invalid token type");
}
virtual Operator ToOperator() const {
throw std::logic_error("Invalid token type");
}
};
struct NumberToken : TokenConcept {
NumberToken(double val) : m_number(val) {}
void Accept(TokenVisitor &visitor) const override {
visitor.VisitNumber(m_number);
}
std::wstring ToString() const override {
return std::to_wstring(m_number);
}
bool EqualsToNumber(double value) const override {
return value == m_number;
}
bool Equals(const TokenConcept &other) const {
return other.EqualsToNumber(m_number);
}
double ToNumber() const override {
return m_number;
}
private:
double m_number;
};
struct OperatorToken : TokenConcept {
OperatorToken(Operator val) : m_operator(val) {}
void Accept(TokenVisitor &visitor) const override {
visitor.VisitOperator(m_operator);
}
std::wstring ToString() const override {
return Interpreter::ToString(m_operator);
}
bool EqualsToOperator(Operator value) const override {
return value == m_operator;
}
bool Equals(const TokenConcept &other) const {
return other.EqualsToOperator(m_operator);
}
Operator ToOperator() const override {
return m_operator;
}
private:
Operator m_operator;
};
public:
Token(Operator val) : m_concept(std::make_shared<OperatorToken>(val)) {}
Token(double val) : m_concept(std::make_shared<NumberToken>(val)) {}
void Accept(TokenVisitor &visitor) const {
m_concept->Accept(visitor);
}
operator Operator() const {
return m_concept->ToOperator();
}
operator double() const {
return m_concept->ToNumber();
}
friend inline bool operator==(const Token &left, const Token &right) {
return left.m_concept->Equals(*right.m_concept);
}
friend inline std::wstring ToString(const Token &token) {
return token.m_concept->ToString();
}
private:
std::shared_ptr<const TokenConcept> m_concept;
};
typedef std::vector<Token> Tokens;
namespace Lexer {
namespace Detail {
class Tokenizer {
public:
Tokenizer(const std::wstring &expr) : m_current(expr.c_str()) {}
void Tokenize() {
while(!EndOfExperssion()) {
if(IsNumber()) {
ScanNumber();
}
else if(IsOperator()) {
ScanOperator();
}
else {
MoveNext();
}
}
}
const Tokens &Result() const {
return m_result;
}
private:
bool EndOfExperssion() const {
return *m_current == L'';
}
bool IsNumber() const {
return iswdigit(*m_current) != 0;
}
void ScanNumber() {
wchar_t *end = nullptr;
m_result.push_back(wcstod(m_current, &end));
m_current = end;
}
bool IsOperator() const {
auto all = { Operator::Plus, Operator::Minus, Operator::Mul, Operator::Div, Operator::LParen, Operator::RParen };
return std::any_of(all.begin(), all.end(), [this](Operator o) {return *m_current == static_cast<wchar_t>(o); });
}
void ScanOperator() {
m_result.push_back(static_cast<Operator>(*m_current));
MoveNext();
}
void MoveNext() {
++m_current;
}
const wchar_t *m_current;
Tokens m_result;
};
} // namespace Detail
inline Tokens Tokenize(const std::wstring &expr) {
Detail::Tokenizer tokenizer(expr);
tokenizer.Tokenize();
return tokenizer.Result();
}
} // namespace Lexer
namespace Parser {
inline int PrecedenceOf(Operator op) {
return (op == Operator::Mul || op == Operator::Div) ? 1 : 0;
}
namespace Detail {
class ShuntingYardParser : TokenVisitor {
public:
void Parse(const Tokens &tokens) {
for(const Token &token : tokens) {
token.Accept(*this);
}
PopToOutputUntil([this]() {return StackHasNoOperators(); });
}
const Tokens &Result() const {
return m_output;
}
private:
void VisitOperator(Operator op) override {
switch(op) {
case Operator::LParen:
PushCurrentToStack(op);
break;
case Operator::RParen:
PopToOutputUntil([this]() { return LeftParenOnTop(); });
PopLeftParen();
break;
default:
PopToOutputUntil([&]() { return LeftParenOnTop() || OperatorWithLessPrecedenceOnTop(op); });
PushCurrentToStack(op);
break;
}
}
void VisitNumber(double number) override {
m_output.emplace_back(number);
}
bool StackHasNoOperators() const {
if(m_stack.back() == Token(Operator::LParen)) {
throw std::logic_error("Closing paren not found.");
}
return false;
}
void PushCurrentToStack(Operator op) {
return m_stack.emplace_back(op);
}
void PopLeftParen() {
if(m_stack.empty() || m_stack.back() != Operator::LParen) {
throw std::logic_error("Opening paren not found.");
}
m_stack.pop_back();
}
bool OperatorWithLessPrecedenceOnTop(Operator op) const {
return PrecedenceOf(m_stack.back()) < PrecedenceOf(op);
}
bool LeftParenOnTop() const {
return static_cast<Operator>(m_stack.back()) == Operator::LParen;
}
template<class T>
void PopToOutputUntil(T whenToEnd) {
while(!m_stack.empty() && !whenToEnd()) {
m_output.push_back(m_stack.back());
m_stack.pop_back();
}
}
Tokens m_output, m_stack;
};
} // namespace Detail
inline Tokens Parse(const Tokens &tokens) {
Detail::ShuntingYardParser parser;
parser.Parse(tokens);
return parser.Result();
}
} // namespace Parser
namespace Evaluator {
namespace Detail {
class StackEvaluator : TokenVisitor {
public:
void Evaluate(const Tokens &tokens) {
for(const Token &token : tokens) {
token.Accept(*this);
}
}
double Result() const {
return m_stack.empty() ? 0 : m_stack.back();
}
private:
void VisitOperator(Operator op) override {
double second = PopOperand();
double first = PopOperand();
m_stack.push_back(BinaryFunctionFor(op)(first, second));
}
void VisitNumber(double number) override {
m_stack.push_back(number);
}
double PopOperand() {
double back = m_stack.back();
m_stack.pop_back();
return back;
}
static const std::function<double(double, double)> &BinaryFunctionFor(Operator op) {
static const std::map<Operator, std::function<double(double, double)>> functions{
{ Operator::Plus, std::plus<double>() },
{ Operator::Minus, std::minus<double>() },
{ Operator::Mul, std::multiplies<double>() },
{ Operator::Div, std::divides<double>() },
};
auto found = functions.find(op);
if(found == functions.cend()) {
throw std::logic_error("Operator not found.");
}
return found->second;
}
std::vector<double> m_stack;
};
} // namespace Detail
inline double Evaluate(const Tokens &tokens) {
Detail::StackEvaluator evaluator;
evaluator.Evaluate(tokens);
return evaluator.Result();
}
} // namespace Evaluator
inline double InterpreteExperssion(const std::wstring &expression) {
return Evaluator::Evaluate(Parser::Parse(Lexer::Tokenize(expression)));
}
} // namespace Interpreter
#include "stdafx.h"
#include "CppUnitTest.h"
#include "Interpreter.h"
#pragma warning(disable: 4505)
namespace InterpreterTests {
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
using namespace Interpreter;
using namespace std;
namespace AssertRange {
template<class T, class ActualRange>
static void AreEqual(initializer_list<T> expect, const ActualRange &actual) {
auto actualIter = begin(actual);
auto expectIter = begin(expect);
Assert::AreEqual(distance(expectIter, end(expect)), distance(actualIter, end(actual)), L"Size differs.");
for(; expectIter != end(expect) && actualIter != end(actual); ++expectIter, ++actualIter) {
auto message = L"Mismatch in position " + to_wstring(distance(begin(expect), expectIter));
Assert::AreEqual<T>(*expectIter, *actualIter, message.c_str());
}
}
} // namespace AssertRange
static const Token plus(Operator::Plus), minus(Operator::Minus);
static const Token mul(Operator::Mul), div(Operator::Div);
static const Token pLeft(Operator::LParen), pRight(Operator::RParen);
static const Token _1(1), _2(2), _3(3), _4(4), _5(5);
TEST_CLASS(LexerTests) {
public:
TEST_METHOD(Should_return_empty_token_list_when_put_empty_expression) {
Tokens tokens = Lexer::Tokenize(L"");
Assert::IsTrue(tokens.empty());
}
TEST_METHOD(Should_tokenize_single_plus_operator) {
Tokens tokens = Lexer::Tokenize(L"+");
AssertRange::AreEqual({ plus }, tokens);
}
TEST_METHOD(Should_tokenize_single_digit) {
Tokens tokens = Lexer::Tokenize(L"1");
AssertRange::AreEqual({ _1 }, tokens);
}
TEST_METHOD(Should_tokenize_floating_point_number) {
Tokens tokens = Lexer::Tokenize(L"12.34");
AssertRange::AreEqual({ 12.34 }, tokens);
}
TEST_METHOD(Should_tokenize_plus_and_number) {
Tokens tokens = Lexer::Tokenize(L"+12.34");
AssertRange::AreEqual({ plus, Token(12.34) }, tokens);
}
TEST_METHOD(Should_skip_spaces) {
Tokens tokens = Lexer::Tokenize(L" 1 + 12.34 ");
AssertRange::AreEqual({ _1, plus, Token(12.34) }, tokens);
}
TEST_METHOD(Should_tokenize_complex_experssion) {
Tokens tokens = Lexer::Tokenize(L"1+2*3/(4-5)");
AssertRange::AreEqual({ _1, plus, _2, mul, _3, div, pLeft, _4, minus, _5, pRight }, tokens);
}
};
TEST_CLASS(TokenTests) {
public:
TEST_METHOD(Should_check_for_equality_operator_tokens) {
Assert::AreEqual(minus, minus);
Assert::AreNotEqual(minus, plus);
Assert::AreNotEqual(minus, _1);
}
TEST_METHOD(Should_check_for_equality_number_tokens) {
Assert::AreEqual(_1, _1);
Assert::AreNotEqual(_1, _2);
Assert::AreNotEqual(_1, minus);
}
TEST_METHOD(Should_get_operator_code_from_operator_token) {
Token token(Operator::Plus);
Assert::AreEqual<Operator>(Operator::Plus, token);
}
TEST_METHOD(Should_get_number_value_from_number_token) {
Token token(1.23);
Assert::AreEqual<double>(1.23, token);
}
};
TEST_CLASS(ParserTests) {
public:
TEST_METHOD(Should_return_empty_list_when_put_empty_list) {
Tokens tokens = Parser::Parse({});
Assert::IsTrue(tokens.empty());
}
TEST_METHOD(Should_parse_single_number) {
Tokens tokens = Parser::Parse({ _1 });
AssertRange::AreEqual({ _1 }, tokens);
}
TEST_METHOD(Should_parse_num_plus_num) {
Tokens tokens = Parser::Parse({ _1, plus, _2 });
AssertRange::AreEqual({ _1, _2, plus }, tokens);
}
TEST_METHOD(Should_parse_two_additions) {
Tokens tokens = Parser::Parse({ _1, plus, _2, plus, _3 });
AssertRange::AreEqual({ _1, _2, plus, _3, plus }, tokens);
}
TEST_METHOD(Should_get_same_precedence_for_operator_pairs) {
Assert::AreEqual(Parser::PrecedenceOf(Operator::Plus), Parser::PrecedenceOf(Operator::Minus));
Assert::AreEqual(Parser::PrecedenceOf(Operator::Mul), Parser::PrecedenceOf(Operator::Div));
}
TEST_METHOD(Should_get_greater_precedence_for_multiplicative_operators) {
Assert::IsTrue(Parser::PrecedenceOf(Operator::Mul) > Parser::PrecedenceOf(Operator::Plus));
}
TEST_METHOD(Should_parse_add_and_mul) {
Tokens tokens = Parser::Parse({ _1, plus, _2, mul, _3 });
AssertRange::AreEqual({ _1, _2, _3, mul, plus }, tokens);
}
TEST_METHOD(Should_parse_complex_experssion) {
Tokens tokens = Parser::Parse({ _1, plus, _2, div, _3, minus, _4, mul, _5 });
AssertRange::AreEqual({ _1, _2, _3, div, plus, _4, _5, mul, minus }, tokens);
}
TEST_METHOD(Should_skip_parens_around_number) {
Tokens tokens = Parser::Parse({ pLeft, _1, pRight });
AssertRange::AreEqual({ _1 }, tokens);
}
TEST_METHOD(Should_parse_expression_with_parens_in_beginning) {
Tokens tokens = Parser::Parse({ pLeft, _1, plus, _2, pRight, mul, _3 });
AssertRange::AreEqual({ _1, _2, plus, _3, mul }, tokens);
}
TEST_METHOD(Should_throw_when_opening_paren_not_found) {
Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ _1, pRight }); });
}
TEST_METHOD(Should_throw_when_closing_paren_not_found) {
Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ pLeft, _1 }); });
}
TEST_METHOD(Should_parse_complex_experssion_with_paren) {
// (1+2)*(3/(4-5)) = 1 2 + 3 4 5 - / *
Tokens tokens = Parser::Parse({ pLeft, _1, plus, _2, pRight, mul, pLeft, _3, div, pLeft, _4, minus, _5, pRight, pRight });
AssertRange::AreEqual({ _1, _2, plus, _3, _4, _5, minus, div, mul }, tokens);
}
};
TEST_CLASS(EvaluatorTests) {
public:
TEST_METHOD(Should_return_zero_when_evaluate_empty_list) {
double result = Evaluator::Evaluate({});
Assert::AreEqual(0.0, result);
}
TEST_METHOD(Should_return_number_when_evaluate_list_with_number) {
double result = Evaluator::Evaluate({ _1 });
Assert::AreEqual(1.0, result);
}
TEST_METHOD(Should_eval_expression_with_one_operator) {
double result = Evaluator::Evaluate({ _1, _2, plus });
Assert::AreEqual(3.0, result);
}
TEST_METHOD(Should_eval_expression_with_one_multiplication) {
double result = Evaluator::Evaluate({ _2, _3, mul });
Assert::AreEqual(6.0, result);
}
TEST_METHOD(Should_eval_expression_with_one_subtraction) {
double result = Evaluator::Evaluate({ _2, _3, minus });
Assert::AreEqual(-1.0, result);
}
TEST_METHOD(Should_eval_expression_with_one_division) {
double result = Evaluator::Evaluate({ _5, _2, div });
Assert::AreEqual(2.5, result);
}
TEST_METHOD(Should_eval_complex_expression) {
// (4+1)*2/(4/(3-1)) = 4 1 + 2 * 4 3 1 - / / = 5
double result = Evaluator::Evaluate({ _4, _1, plus, _2, mul, _4, _3, _1, minus, div, div });
Assert::AreEqual(5.0, result);
}
};
TEST_CLASS(InterpreterIntegrationTests) {
public:
TEST_METHOD(Should_interprete_empty_experssion) {
double result = Interpreter::InterpreteExperssion(L" ");
Assert::AreEqual(0.0, result);
}
TEST_METHOD(Should_interprete_experssion) {
double result = Interpreter::InterpreteExperssion(L"1+2");
Assert::AreEqual(3.0, result);
}
};
}
Код к статье на GitHub. Названия коммитов и их порядок соответствуют тестам и рефакторингам, описанным выше.
Более подробное описание алгоритма сортировочной станции на PEGWiki.
Советую к прочтению книгу Jeff Langr. Modern C++ Programming with Test-Driven Development. — The Pragmatic Programmers, 2013.
Автор: Unrul
