Writing a simple interpreter in C ++ using TDD, part 3

The lexer was written in the first part , and the parser in the second part . Further development of the calculator and the facade for the entire interpreter, as well as code refactoring to eliminate duplication will be considered.

Calculator

Let's get to the fun part. The calculation of the expression in the postfix entry can be done in two ways: through recursion, implicitly using the process stack, or using an explicit stack. We implement the second option. An algorithm using an explicit stack is:

If an operand is fed to the input, it is placed on top of the stack.
If the sign of the operation is input, the corresponding operation is performed on the required number of values extracted from the stack, taken in the order of addition. The result of the operation is placed on top of the stack.
After complete processing of the input character set, the result of evaluating the expression lies at the top of the stack.

In this article I will not implement the execution context and the calculation of several expressions. Therefore, the initial test list will be short:
')

If the input list is empty, return 0.
If the input list with one number, return this number.
If input [1 2 +], return 3.

Create a new test class and add the first test.

TEST_CLASS(EvaluatorTests) { public: TEST_METHOD(Should_return_zero_when_evaluate_empty_list) { double result = Evaluator::Evaluate({}); Assert::AreEqual(0.0, result); } };

Usually add an empty function to the required namespace.

 namespace Evaluator { inline double Evaluate(Tokens) { return 0; } } // namespace Evaluator

Let's write the second test.

  TEST_METHOD(Should_return_number_when_evaluate_list_with_number) { double result = Evaluator::Evaluate({ _1 }); Assert::AreEqual(1.0, result); }

Just return what was last in the list. It would be easier to do, but then you still need to add a loop.

 inline double Evaluate(const Tokens &tokens) { double result = 0; for(const Token &token : tokens) { result = token; } return result; }

Further - more difficult. Let's try to calculate an expression with one operator.

  TEST_METHOD(Should_eval_expression_with_one_operator) { double result = Evaluator::Evaluate({ _1, _2, plus }); Assert::AreEqual(3.0, result); }

In order for this test to pass, add just one character to the code.

  for(const Token &token : tokens) { if(token.Type() == TokenType::Number) { result += token; } }

That was enough to pass the test. Let's try to break this algorithm by calculating the result of multiplication.

  TEST_METHOD(Should_eval_expression_with_one_multiplication) { double result = Evaluator::Evaluate({ _2, _3, mul }); Assert::AreEqual(6.0, result); }

The test does not pass, as the addition is rigidly scored. A more complex implementation is needed, taking into account the type of operator. Add a branch and replace the variable with the result on the container.

 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(); }

Note that this algorithm can already perform more complex calculations. Let's do a test operator minus. Its complexity is that you can confuse arguments by pulling them from the stack.

  TEST_METHOD(Should_eval_expression_with_one_subtraction) { double result = Evaluator::Evaluate({ _2, _3, minus }); Assert::AreEqual(-1.0, result); }

In general, according to the C ++ standard, no assumptions can be made regarding the order in which the function arguments are calculated. Therefore, it is necessary to remove operands from the stack in explicit order.

  … else if(token == Token(Operator::Minus)) { double d = pop(); result.push_back(pop() - d); }

A similar test for division.

  TEST_METHOD(Should_eval_expression_with_one_division) { double result = Evaluator::Evaluate({ _5, _2, div }); Assert::AreEqual(2.5, result); }

In the beginning, I wrote a test for division, using the expression 4/2=2 , and it immediately passed, despite the fact that the division operation was not added. This was due to the fact that the last number added to it was retrieved from the stack, which, by coincidence, turned out to be equal to the result of the expression. That is why the tests immediately after writing should fall, otherwise there is a high probability that the test does not actually test anything.

  … else if(token == Token(Operator::Div)) { double d = pop(); result.push_back(pop() / d); }

To make sure that everything works as it should, add the last test to calculate a complex expression.

  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); }

It passes, but it was intended. There is quite a bit of duplication in our function. We take it into a separate class and refactor.

 inline double Evaluate(const Tokens &tokens) { Detail::StackEvaluator evaluator(tokens); evaluator.Evaluate(); return evaluator.Result(); }

Class Detail :: StackEvaluator

 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

Interpreter

To simplify the work of the client, we will write a small function, which is a facade for the entire interpreter. Let's start with a couple of integration tests.

 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); } };

Let's write the implementation of the InterpreteExperssion function in the already existing Interpreter namespace.

 inline double InterpreteExperssion(const std::wstring &expression) { return Evaluator::Evaluate(Parser::Parse(Lexer::Tokenize(expression))); }

Hurray, tests pass, then all parts of the interpreter interact as planned.

Refactoring

Now that the entire code is covered with tests, you can see if there is duplication on a global scale and eliminate it. Immediately struck by a bunch of identical switch that perform checks on the type of token. And in the token itself, both the number and the operator are stored simultaneously. In order to get away from the conditional statements in each method, use the visitor template. Create an abstract class TokenVisitor :

 struct TokenVisitor { virtual void VisitNumber(double) {} virtual void VisitOperator(Operator) {} protected: ~TokenVisitor() {} };

For simplicity, virtual methods will have an empty default implementation. For security, we declare the destructor as protected and non-virtual in order to prevent the possibility of deletion through a pointer to this class. Add a method to the token that accepts a visitor and transfer the ill-fated 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"); } }

Now let's look at the ShuntingYardParser class and its ParseCurrentToken method.

  void ParseCurrentToken() { switch(m_current->Type()) { case TokenType::Operator: ParseOperator(); break; case TokenType::Number: ParseNumber(); break; default: throw std::out_of_range("TokenType"); } }

The similarity is obvious. Inherit this class from the abstract visitor and rename the Parse* methods to Visit* . After that, the class will considerably lose weight, and the Parse method will look like this:

  void Parse() { for(; m_current != m_end; ++m_current) { m_current->Accept(*this); } PopToOutputUntil([this]() {return StackHasNoOperators(); }); }

We will do the same with the StackEvaluator class.

 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); } };

It would be possible not to use inheritance and virtual functions at all, replacing everything with templates, but then all support from the IDE will be lost and you will have to rely only on implicit agreements. Now let's deal with the remaining switch and union switch . Here the state pattern can be useful, which, by the way, implicitly uses std::function . We proceed by analogy. Create a TokenConcept private abstract class inside the token class, which will contain operations that depend on the type of token. The specific implementation of the concept will be stored in std::shared_ptr<const TokenConcept> , since the token is immutable, then it is completely safe to make the state shared.

  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"); } };

Let's not get rid of TokenType completely so as not to break the tests. Now we add the implementations for the number and the operator, then we replace the logic in the token methods with the reference to the concept.

Token class after refactoring

 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; };

Note that not a single test broke during refactoring, although the type of code has changed quite significantly. Go ahead and delete the TokenType enumeration, since it is used only in the Token class. Before that, we change the tests Should_get_type_for_operator_token and Should_get_type_for_number_token so that they do not use the type of token, slightly adjusting their semantics.

  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); }

After deleting an enumeration, the problem of comparing tokens of different types arises. You do not want to use RTTY, so we will slightly TokenConcept base class by adding double dispatch support for the Equals operation.

  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); } };

The derived classes in the Equals method perform the first dispatch step to determine the type of the first token, after which the second token makes a comparison with the already known type. Tokens of different types are not equal by default, so derived classes need to override only one method that takes an argument of the appropriate type.

Conclusion

In this article, I tried to move away from the usual topics of TDD materials, focusing more on theory and delve into the practical application of this technique. As shown, even in C ++, you can develop through testing without much difficulty. Moreover, it is easy to get started, given the presence of built-in test support for C ++ projects in Visual Studio. Of course, writing more complex systems requires more complex libraries, such as Boost.Test, Google.Test, or CppUTest, as well as libraries for creating mock objects, such as Google.Mock, or Turtle. And not all scripts can be tested only with the help of unit tests. But, nevertheless, the writing of unit tests and the development through testing markedly help in writing code, simplify its modification in the future and give confidence that everything works exactly as planned.

If readers are interested, I can write the second part in a similar style, in which the implementation of the remaining items from the list at the beginning of the first part of this article will be described.

Resources

Below is the entire code in the final version:

Interpreter.h

 #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 /// <summary> /// Convert the expression string to a sequence of tokens. /// </summary> 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 /// <summary> /// Convert the sequence of tokens in infix notation to a sequence in postfix notation. /// </summary> 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 /// <summary> /// Evaluate the sequence of tokens in postfix notation and get a numerical result. /// </summary> inline double Evaluate(const Tokens &tokens) { Detail::StackEvaluator evaluator; evaluator.Evaluate(tokens); return evaluator.Result(); } } // namespace Evaluator /// <summary> /// Interpret the mathematical expression in infix notation and return a numerical result. /// </summary> inline double InterpreteExperssion(const std::wstring &expression) { return Evaluator::Evaluate(Parser::Parse(Lexer::Tokenize(expression))); } } // namespace Interpreter

InterpreterTests.cpp

 #include "stdafx.h" #include "CppUnitTest.h" #include "Interpreter.h" 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 const Token plus(Operator::Plus), minus(Operator::Minus); const Token mul(Operator::Mul), div(Operator::Div); const Token pLeft(Operator::LParen), pRight(Operator::RParen); 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_evaluete_empty_list) { double result = Evaluator::Evaluate({}); Assert::AreEqual(0.0, result); } TEST_METHOD(Should_return_number_when_evaluete_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.

Source: https://habr.com/ru/post/232097/

All Articles