Пишем простой интерпретатор на C++ с помощью TDD, часть 3

В первой части был написан лексер, а во второй части — парсер. Далее будет рассмотрена разработка вычислителя и фасада для всего интерпретатора, а также рефакторинг кода для устранения дублирования.

Вычислитель

Приступим к самому интересному. Вычисление выражения в постфиксной записи можно осуществить двумя способами: через рекурсию, неявно используя стек процесса, или используя явный стек. Реализуем второй вариант. Алгоритм с использованием явного стека такой:

• Если на вход подан операнд, он помещается на вершину стека.
• Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
• После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.

В данной статье я не буду реализовывать контекст выполнения и вычисление нескольких выражений. Поэтому начальный список тестов будет коротким:

• Если на входе пустой список, возвращаем 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();
}

Класс 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

Интерпретатор

Для упрощения работы со стороны клиента, напишем небольшую функцию, являющуюся фасадом для всего интерпретатора. Добавим для начала пару интеграционных тестов.

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<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 полностью, чтобы не ломать тесты. Теперь добавим реализации для числа и оператора, после чего заменим логику в методах токена на обращение к концепту.

Класс Token после рефакторинга

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. Да и не все сценарии можно протестировать только с помощью модульных тестов. Но, тем не менее, написание модульных тестов и разработка через тестирование заметно помогают в написании кода, упрощают его модификацию в будущем и придают уверенность в том, что всё работает именно так, как было запланировано.

При наличии интереса у читателей я могу написать вторую часть в подобном стиле, в которой будет описана реализация оставшихся пунктов из списка в начале первой части этой статьи.

Ресурсы

Ниже приведён весь код в конечном варианте:

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.