電卓
楽しい部分に行きましょう。 後置レコードの式を計算するには、再帰を使用する方法、プロセススタックを暗黙的に使用する方法、または明示的なスタックを使用する方法の2つがあります。 2番目のオプションを実装します。 明示的なスタックを使用するアルゴリズムは次のとおりです。
- オペランドが入力される場合、それはスタックの最上部に配置されます。
- 演算記号が入力されると、スタックから抽出された必要な数の値に対して、追加の順序で対応する演算が実行されます。 操作の結果はスタックの一番上に配置されます。
- 入力文字セットの処理が完了すると、式の評価結果はスタックの一番上になります。
この記事では、実行コンテキストと複数の式の評価を実装しません。 したがって、テストの初期リストは短くなります。
- 入力が空のリストの場合、0を返します。
- 入力が1つの番号を持つリストの場合、この番号を返します。
- 入力が[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
2番目のテストを書きましょう。
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; }
もっと難しい。 1つの演算子で式を計算してみましょう。
TEST_METHOD(Should_eval_expression_with_one_operator) { double result = Evaluator::Evaluate({ _1, _2, plus }); Assert::AreEqual(3.0, result); }
このテストに合格するには、コードに1文字だけ追加します。
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(); }
クラスの詳細:: 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
通訳
クライアント側での作業を簡素化するために、インタプリタ全体のファサードである小さな関数を作成します。 最初に、いくつかの統合テストを追加しましょう。
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); } };
既存の
Interpreter
名前空間に
InterpreteExperssion
関数の実装を書きましょう。
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
転送
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<const TokenConcept>
に格納されます。トークンは不変であるため、状態を共有することは完全に安全です。
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
クラスでのみ使用されるため、先に進んで
TokenType
列挙を削除しましょう。 その前に、
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
基本クラスを少し
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
メソッドの派生クラスは、最初のディスパッチステップを実行して最初のトークンのタイプを判別し、その後、2番目のトークンが既知のタイプと比較します。 異なるタイプのトークンはデフォルトでは等しくないため、派生クラスは、適切なタイプの引数を取るメソッドを1つオーバーライドするだけで済みます。
おわりに
この記事では、TDDマテリアルの通常のトピックから離れて、理論に重点を置き、この手法の実用化を掘り下げようとしました。 すでに示したように、C ++であっても、テストを通じて開発をそれほど困難なく行うことができます。 さらに、Visual StudioにはC ++プロジェクトの組み込みテストサポートがあるため、これを簡単に開始できます。 もちろん、より複雑なシステムを作成するには、Boost.Test、Google.Test、CppUTestなどのより複雑なライブラリ、およびGoogle.Mock、Turtleなどのモックオブジェクトを作成するためのライブラリが必要です。 また、すべてのシナリオを単体テストでしかテストできないわけではありません。 しかし、それにもかかわらず、単体テストの作成とテストによる開発は、コードの作成に非常に役立ち、将来の修正を簡素化し、すべてが計画どおりに機能するという自信を与えます。
読者に興味があれば、この記事の最初の部分のリストにある残りの項目の実装を説明する同様のスタイルで2番目の部分を書くことができます。
資源
以下は、最終バージョンのすべてのコードです。
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の記事のコード 。 コミットの名前とその順序は、上記のテストとリファクタリングに対応しています。 3番目の部分の終わりは、ラベル「3番目の部分のEnd_」に対応します。
PEGWikiのソートステーションアルゴリズムの詳細な説明。
ジェフ・ランガーの本を読むことをお勧めします。 テスト駆動開発による最新のC ++プログラミング。 -The Pragmatic Programmers、2013年。