Вычислитель
Приступим к самому интересному. Вычисление выражения в постфиксной записи можно осуществить двумя способами: через рекурсию, неявно используя стек процесса, или используя явный стек. Реализуем второй вариант. Алгоритм с использованием явного стека такой:
- Если на вход подан операнд, он помещается на вершину стека.
- Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
- После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.
В данной статье я не буду реализовывать контекст выполнения и вычисление нескольких выражений. Поэтому начальный список тестов будет коротким:
- Если на входе пустой список, возвращаем 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'\0'; } 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.
ссылка на оригинал статьи http://habrahabr.ru/post/232097/
Добавить комментарий