6
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ This is a rather old question, but with expression parsing you usually want your grammar to consist only of numbers and (unary/binary) operators, so that you can express it as a tree. In your case you would have two general types of expressions: 1) vectors (a list of one or more numbers) and 2) binary or unary operators. The idea is to be able to rewrite ( (0,1,2,3)>2 ) / 2 as an expression tree: Divide(LargerThan(List(0,1,2,3), List(2)), List(2)), because it gives you far greater flexibility for representing expressions, and makes it easy to evaluate them. \$\endgroup\$ – Groo Nov 16 '18 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.