C++ Parsing with chain of responsibility

Question

The task was to create the parser for the string input, that would return the std::vector< int > of parsed numeric results and the type of given input (e.g. numbers, division by zero error, out of range and so on). The assumption was that only numeric characters, spaces, slashes and periods were in given string.

• Single number input (range of numbers is <-7, 7>):

  • "-1" - translates into {-1}, returns type "numbers"

• List input (range the same as above, return type is "numbers"):

  • "1 3 2" - translates into {1, 2, 3}
  • "1, 3, 2" - like above (periods are changed into spaces)
  • "<2" - translates into {-7, -6, -5, -4, -3, -2, -1, 0, 1}
  • ">4" - translates into {5, 6, 7}

• Divisor input, no range limit. Returns the vector and type "divisors".

  • "/2" - translates into {2}

If input is invalid, corresponding error code will be returned as a type along with an empty vector.

The code below is not divided into .h and .cpp files for the sake of brevity, the expanded code is on github page.

Request.h

The output messages are defined here, along with the returned structure.

#ifndef REQUEST_H
#define REQUEST_H

#include <string>
#include <vector>

//request return codes
namespace ReturnCodes
{
    const std::string NOT_A_NUMBER = "Not a number!";
    const std::string INVALID_INPUT = "Invalid input!";
    const std::string SUCCESOR_NULL = "Succesor is null!";
    const std::string OUT_OF_RANGE = "Out of range!";
    const std::string DIVISION_BY_ZERO = "Division by zero!";
    const std::string NUMBERS = "Numbers";
    const std::string DIVISOR = "Divisor";
    const std::string EMPTY = "Empty";
    const std::string OUT_OF_INT_RANGE = "Out of range of int!";
    //custom ones are also allowed
}

//returned structure
struct RequestValue
{
    std::vector<int> result;
    std::string message;

    bool isValid() const
    {
        return message == ReturnCodes::NUMBERS
            || message == ReturnCodes::DIVISOR
            || message == ReturnCodes::EMPTY;
    }
};

#endif

Parser.h

Wrapper class for the chain of request handlers.

#ifndef PARSER_H
#define PARSER_H
#include "RequestHandlers.h"

class Parser
{
    RequestHandler* chain;
public:
    Parser()
    {
        //a chain of handlers
        chain = new EmptyStringHandler(
                    new DivisorStringHandler(
                        new SingleNumberStringHandler(
                            new InequalityStringHandler(
                                new ListStringHandler(
                                    nullptr)))));
    }

    RequestValue parse(const std::string& value, bool preprocess = true) const
    {
        if (preprocess)
        {
            std::string text = RequestPreprocessor::changePeriodsToSpaces(value);
            text = RequestPreprocessor::removeTrailingSpaces(text);
            return chain->handle(text);
        }
        else
        {
            return chain->handle(value);
        }
    }

    ~Parser()
    {
        delete chain;
    }

};

#endif

RequestPreprocessor.h

Helper class for string operations.

#ifndef STRING_SUBPROCESSOR_H
#define STRING_SUBPROCESSOR_H

#include <string>
#include <algorithm>

class RequestPreprocessor
{
public:
    //as the range where the numbers are valid is symmetrical,
    //store only one number
    static const int maxNumber = 7;

    //check if integer r is in range specified as a const class member
    static bool isInRangeInclusive(int r)
    {
        return r >= -maxNumber && r <= maxNumber;
    }

    //as periods doesn't matter, they can be changed into spaces
    static std::string changePeriodsToSpaces(std::string input)
    {
        std::replace(input.begin(), input.end(), ',', ' ');
        return input;
    }

    //remove unnecessary space prefixes and suffixes
    static std::string removeTrailingSpaces(const std::string& input)
    {
        if (input.empty()) return input;

        //seek start
        unsigned start = 0;
        while (start < input.size() && input[start] == ' ') start++;

        //seek end
        unsigned end = static_cast<unsigned int>(static_cast<int>(input.size()) - 1);
        while (end > start && input[end] == ' ') end--;

        return input.substr(start, end - start + 1);
    }

    //used in Division input Acase
    static bool hasSlash(const std::string& input)
    {
        return input.find('/') != std::string::npos;
    }

    //used in inequality input cases
    static bool hasInequalityCharacters(const std::string& input)
    {
        return input.find('>') != std::string::npos ||
            input.find('<') != std::string::npos;
    }

    //check if a string contains only digits or '-' sign
    static bool isANumber(const std::string& input)
    {
        std::string text = removeTrailingSpaces(input);
        //check first character
        unsigned i = 0;
        if (text[0] == '-')
        {
            if (text.size() == 1) //check if input consists of only one '-' character
            {
                return false; //"-" is not a number!
            }
            i++;
        }

        //check digits, start from i-th character
        return !std::any_of(text.begin() + i, text.end(), [](char c) { return c < '0' || c>'9'; });

    };
};

#endif

RequestHandlers.h

A collection of classes used as a links in parser chain.

#ifndef REQUEST_HANDLER_H
#define REQUEST_HANDLER_H

#include "Request.h"
#include "RequestPreprocessor.h"
#include <iterator>
#include <sstream>

//base class for handlers
class RequestHandler
{
protected:
    //next handler
    RequestHandler * succesor = nullptr;

    //check if handler can try to process the request
    virtual bool canHandleRequest(const std::string &input) const = 0;

    //process the request - we can assume that no other Handler is able to do it
    virtual RequestValue handleImplementation(const std::string &input) const = 0;

    //give up and relay the input to next handler
    RequestValue passFurther(const std::string& input) const
    {
        if (succesor == nullptr)
        {
            return { {}, ReturnCodes::SUCCESOR_NULL };
        }
        else
        {
            return succesor->handle(input);
        }
    }

public:
    //constructor - if successor is nullptr, it means that it is the last element
    explicit RequestHandler(RequestHandler* succesor)
    {
        this->succesor = succesor;
    }

    //check if input can be handled ? handle it : pass further
    RequestValue handle(const std::string& input) const
    {
        if (canHandleRequest(input))
        {
            return handleImplementation(input);
        }
        else
        {
            return passFurther(input);
        }
    }


    //take care for its successors
    virtual ~RequestHandler()
    {
        delete succesor;
    }
};

//check is input is just ""
class EmptyStringHandler : public RequestHandler
{
public:
    explicit EmptyStringHandler(RequestHandler *succesor) : RequestHandler(succesor) { }

protected:
    bool canHandleRequest(const std::string& input) const override
    {
        return input.empty();
    }

    RequestValue handleImplementation(const std::string& input) const override
    {
        return { {}, ReturnCodes::EMPTY };
    }
};

//check for input being a number between -7 and 7, inclusively
class SingleNumberStringHandler : public RequestHandler
{
public:
    explicit SingleNumberStringHandler(RequestHandler *succesor) : RequestHandler(succesor) { }

protected:
    bool canHandleRequest(const std::string& input) const override
    {
        return !input.empty() &&
            !RequestPreprocessor::hasInequalityCharacters(input) &&
            !RequestPreprocessor::hasSlash(input) &&
            RequestPreprocessor::isANumber(input);
    }

    RequestValue handleImplementation(const std::string& input) const override
    {
        try
        {
            //check for incorrect characters
            if (!RequestPreprocessor::isANumber(input))
            {
                return { {}, ReturnCodes::NOT_A_NUMBER };
            }
            int p = stoi(input);
            //check range
            if (RequestPreprocessor::isInRangeInclusive(p))
            {
                return { { p }, ReturnCodes::NUMBERS };
            }
            else
            {
                return { { p }, ReturnCodes::OUT_OF_RANGE };
            }
        }
        //stoi errors
        catch (std::invalid_argument &invalidArgumentException)
        {
            return passFurther(input);
        }
        catch (std::out_of_range &outOfRangeException)
        {
            return { {}, ReturnCodes::OUT_OF_INT_RANGE };
        }
    }
};

//check input with '<'
class InequalityStringHandler : public RequestHandler
{
public:
    explicit InequalityStringHandler(RequestHandler *succesor) : RequestHandler(succesor) { }

protected:
    bool canHandleRequest(const std::string& input) const override
    {
        //the characters after then inequality sign cannot be other inequality
        return input.size() > 1 && (input[0] == '<' || input[0] == '>') &&
            !RequestPreprocessor::hasSlash(input) &&
            !RequestPreprocessor::hasInequalityCharacters(input.substr(1));
    }

    RequestValue handleImplementation(const std::string& input) const override
    {
        try
        {
            //check for incorrect characters
            if (!RequestPreprocessor::isANumber(input.substr(1)))
            {
                return { {}, ReturnCodes::NOT_A_NUMBER };
            }
            int p = stoi(input.substr(1));
            //check range
            if (!RequestPreprocessor::isInRangeInclusive(p))
            {
                return { { p }, ReturnCodes::OUT_OF_RANGE };
            }

            if (input[0] == '<')
            {
                //grab items <p
                std::vector<int> result;
                for (int i = -RequestPreprocessor::maxNumber; i < p; i++)
                {
                    result.push_back(i);
                }
                return { result, ReturnCodes::NUMBERS };
            }
            //provided by canHandleRequest, there're no other cases than '>'
            else
            {
                //grab items >p
                std::vector<int> result;
                for (int i = p + 1; i <= RequestPreprocessor::maxNumber; i++)
                {
                    result.push_back(i);
                }
                return { result, ReturnCodes::NUMBERS };
            }
        }
        //stoi errors
        catch (std::invalid_argument &invalidArgumentException)
        {
            return passFurther(input);
        }
        catch (std::out_of_range &outOfRangeException)
        {
            return { {}, ReturnCodes::OUT_OF_INT_RANGE };
        }
    }
};

//check for space-separated input
class ListStringHandler : public RequestHandler
{
public:
    explicit ListStringHandler(RequestHandler *succesor) : RequestHandler(succesor) { }

protected:
    bool canHandleRequest(const std::string& input) const override
    {
        return input.size() > 1 &&
            !RequestPreprocessor::hasSlash(input) &&
            !RequestPreprocessor::hasInequalityCharacters(input);
    }

    RequestValue handleImplementation(const std::string& input) const override
    {
        std::vector<int> v;
        try
        {
            //split input by spaces
            std::vector<std::string> results = tokenize(input);

            for (auto&& result : results)
            {
                //check for incorrect characters
                if (!RequestPreprocessor::isANumber(result))
                {
                    return { { v }, "Not a number @" + std::to_string(v.size() + 1) + "!" };
                }
                int p = stoi(result);
                //check range
                if (RequestPreprocessor::isInRangeInclusive(p))
                {
                    //no duplicates!
                    if (find(v.begin(), v.end(), p) == v.end()) {
                        v.push_back(p);
                    }
                }
                else {
                    return { v, "Out of range @" + std::to_string(v.size() + 1) + "!" };
                }
            }
            sort(v.begin(), v.end());
            return { v, ReturnCodes::NUMBERS };
        }
        //stoi errors
        catch (std::invalid_argument &invalidArgumentException)
        {
            return { {}, "Invalid character @" + std::to_string(v.size() + 1) + "!" };
        }
        catch (std::out_of_range &outOfRangeException)
        {
            return { {}, ReturnCodes::OUT_OF_INT_RANGE };
        }
    }

private:
    static std::vector<std::string> tokenize(const std::string& input)
    {
        std::istringstream iss(input);
        return std::vector<std::string>(
            std::istream_iterator<std::string>(iss),
            std::istream_iterator<std::string>());
    }
};

//check for number with '/' operator
class DivisorStringHandler : public RequestHandler
{
public:
    explicit DivisorStringHandler(RequestHandler *succesor) : RequestHandler(succesor) { }

protected:
    bool canHandleRequest(const std::string& input) const override
    {
        return input.size() > 1 &&
            input[0] == '/' &&
            !RequestPreprocessor::hasInequalityCharacters(input);
    }

    RequestValue handleImplementation(const std::string& input) const override
    {
        try
        {
            std::string text = input.substr(1);
            //check for incorrect characters
            if (!RequestPreprocessor::isANumber(text))
            {
                return { {}, ReturnCodes::NOT_A_NUMBER };
            }
            int p = stoi(text);
            //obvious division by zero
            if (p == 0)
            {
                return { { p }, ReturnCodes::DIVISION_BY_ZERO };
            }
            //check range
            return { { p }, ReturnCodes::DIVISOR };
        }
        //stoi errors
        catch (std::invalid_argument &invalidArgumentException)
        {
            return passFurther(input);
        }
        catch (std::out_of_range &outOfRangeException)
        {
            return { {}, ReturnCodes::OUT_OF_INT_RANGE };
        }
    }
};

#endif

main.cpp Entry point for program, it only runs a series of tests on various input.

#include <iostream>
#include <cassert>
#include "Parser.h"

//go through a set of cases
void runTests()
{
    Parser *parser = new Parser();

    //empty input 
    RequestValue r = parser->parse("");
    assert(r.isValid() && r.result.empty());

    //single-number input
    r = parser->parse("-0");
    assert(r.isValid() && r.result[0] == 0);
    r = parser->parse("7");
    assert(r.isValid() && r.result[0] == 7);
    r = parser->parse("8");
    assert(!r.isValid() && r.message == ReturnCodes::OUT_OF_RANGE);
    r = parser->parse("-7");
    assert(r.isValid() && r.result[0] == -7);
    r = parser->parse("-8");
    assert(!r.isValid() && r.message == ReturnCodes::OUT_OF_RANGE);
    r = parser->parse("9");
    assert(!r.isValid() && r.message == ReturnCodes::OUT_OF_RANGE);
    r = parser->parse("-9");
    assert(!r.isValid() && r.message == ReturnCodes::OUT_OF_RANGE);

    //inequality input
    r = parser->parse("<2");
    assert(r.isValid() && r.result.size() == 9 && r.result[1] == -6);
    r = parser->parse("<-6");
    assert(r.isValid() && r.result.size() == 1 && r.result[0] == -7);
    r = parser->parse(">6");
    assert(r.isValid() && r.result.size() == 1 && r.result[0] == 7);
    r = parser->parse(">7");
    assert(r.isValid() && r.result.empty());
    r = parser->parse("<-7");
    assert(r.isValid() && r.result.empty());
    r = parser->parse("<<2");
    assert(!r.isValid());
    r = parser->parse("     <    -2 2     2    ");
    assert(!r.isValid());

    //list input
    r = parser->parse("1 2");
    assert(r.isValid() && r.result.size() == 2);
    r = parser->parse("-1, -2 -4");
    assert(r.isValid() && r.result.size() == 3 && r.result[2] == -1);
    r = parser->parse("-2, -2 -2, -3, -4 1 2 2");
    assert(r.isValid() && r.result.size() == 5);

    //division input
    r = parser->parse("/2");
    assert(r.isValid());
    r = parser->parse("/");
    assert(!r.isValid());
    r = parser->parse("/4/");
    assert(!r.isValid());
    r = parser->parse("/-1231");
    assert(r.result.size() == 1 && r.result[0] == -1231);
    r = parser->parse("//1");
    assert(r.isValid() == false);
    r = parser->parse("/0");
    assert(!r.isValid() && r.message == ReturnCodes::DIVISION_BY_ZERO);

    //mixed / random
    r = parser->parse("/2 3, -2");
    assert(r.isValid() == false);
    r = parser->parse("sink");
    assert(r.isValid() == false);
    r = parser->parse("111111111111111111111");
    assert(!r.isValid() && r.message == ReturnCodes::OUT_OF_INT_RANGE);

}

int main() {
    std::cout << "Testing..." << std::endl;

    runTests();

    std::cout << "We are here, so the tests are complete" << std::endl;

    system("pause");
    return 0;
}

Answer 1

About the design pattern

The chain-of-responsibility pattern is one way to deal with having multiple request handlers, but is it really necessary? While it allows Parser to just store a pointer to the first RequestHandler, now each RequestHandler has to deal with being part of a chain. You can remove that responsibility from the RequestHandlers, as they already have enough to do, and put it back in Parser.

Parser could just use std::list or std::vector to store the chain. Or since you hardcoded the list of handlers in the constructor, you could just as well store it in a fixed-size array:

class Parser {
    RequestHandler *const chain[5] = {
        new EmptyStringHandler,
        new DivisorStringHandler,
        new SingleNumberStringHandler,
        new InequalityStringHandler,
        new ListStringHandler,
    };

public:
    RequestValue parse(const std::string& value, …) const {
        …
        for (auto* handler: chain) {
            if (handler.canHandleRequest(value)
                return handler.handle(value);
        }

        return {{}, ReturnCodes::SUCCESOR_NULL};
    }

    ~Parser() {
         for (auto* handler: chain)
             delete handler;
    }
};

The GoF design patterns are mostly focussed on object-oriented ways to solve problems, and ignore generic programming. This might be due to the age of the book; OOP was very popular then, and C++'s standard library did not offer a lot of support for generic programming. Nowadays you could write the code like so:

class Parser {
    std::tuple<
        EmptyStringHandler,
        DivisorStringHandler,
        SingleNumberStringHandler,
        InequalityStringHandler,
        ListStringHandler,
    > chain;

public:
    RequestValue parse(const std::string& value, …) const {
        …
        RequestValue result = {{}, ReturnCodes::SUCCESSOR_NULL};

        auto handle = [&](auto& handler) {
            if (handler.canHandleRequest(value)) {
                result = handler.handle(value);
                return true;
            } else {
                return false;
            }
        };

        std::apply([&](auto&... handlers) {(handle(handlers) || ...);}, chain);
        return result;
    }
};

That looks a bit strange if you are not used to generic programming, but it's not that much more work than the version using a list of pointers to base classes. The advantage of the generic approach is that we no longer need to use pointers, so we also no longer need to worry about destructors. You can still have a base class RequestHandler, but the methods no longer have to be virtual, since parse() sees the derived type of each element of the chain.

Don't use strings as return codes

It's nice for the end user that a text can be displayed describing what error happened, but having return codes be strings is very inefficient. Consider RequestValue::isValid(): it has to do up to three string comparisons to check if the value is valid. Consider using an enum class instead:

enum class ReturnCode {
    NOT_A_NUMBER,
    INVALID_INPUT,
    …
};

struct RequestValue {
    std::vector<int> result;
    ReturnCode status;

    bool isValid() const {
        return status == ReturnCode::NUMBERS
            || status == ReturnCode::DIVISOR
            || status == ReturnCode::EMPTY;
    }
};

Now it's just a few integers to compare, and since they are consecutive the compiler could even optimize this to return status >= ReturnCode::NUMBERS && status <= ReturnCode::EMPTY.

Note that you could add a std::string anyway to RequestValue which supports passing arbitrary error messages.

Consider throwing exceptions on parse errors

Instead of overloading RequestValue to store both results and a possible error message, you could instead have it only store valid results, and use exceptions to deal with errors. You can create your own custom exception types derived from the standard exceptions.

struct OutOfRangeError: public std::runtime_error {
    using std::runtime_error::runtime_error; // make the base class constructor visible
};

class SingleNumberStringHandler: … {
    …
    if (!RequestPreprocessor::isInRangeInclusive(p)) {
        throw OutOfRangeError("Single number is out of range");
    }
    …
};

void runTests() {
    …
    try {
        r = parser->parse("8");
        assert(false); // we should never reach this line
    } catch(OutOfRangeError& ex) {
        // this is fine
    }
    // any other exception will cause the program to abort as well
    …
}