Lisp Parser and Interpreter, takes string of lisp code and runs it.

enum.hpp

// Copyright 2017, Victor R. Cabrera
#ifndef D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_ENUM_HPP_
#define D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_ENUM_HPP_

/* 
 * enum's needed in order to tell the TaggedUnion value's 
 * type as well as it's label for lisp parsing 
 */

enum class Type { Char, Int, Double, String, List };

/* I got the label names through an article that I read about the terminology used in Lisp. This is the article if you are interested:
 * http://groups.engin.umd.umich.edu/CIS/course.des/cis400/lisp/lisp.html
 */
enum class Label { Atom, Identifier, Neither };

#endif  // D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_ENUM_HPP_

main.cpp

// Copyright 2017, Victor R. Cabrera
#include <iostream>
#include <vector>
#include <cassert>
#include "./include/Parser.hpp"

using list = std::vector<TaggedUnion>;
using string = std::string;

/* My code currently assumes that the lisp you are printing is valid.
 * It also assumes you are giving it lisp code that is structured in a certain
 * way (for ex without spaces like ( first ( list 1 ( + 2.40 3 )  9   ) ).
 * That will be a future task since I figured just getting it to work should
 * be enough for now. 
 */
int main(void) {
    Parser tester;
    string lisp = "(first (list 1 (+ 2.40 3) 9))";
    list arr = tester.parse(lisp);
    tester.printList(arr);
    std::cout << std::endl;
    return 0;
}

/* compile using: g++ -std=c++14 main.cpp src/Parser.cpp src/Utils.cpp src/TaggedUnion.cpp -o main
 * folder structure should be as follows:
 * Lisp Interpreter:
 *     include:
 *         enum.hpp
 *         Parser.hpp
 *         TaggedUnion.hpp
 *         Utils.hpp
 *     src:
 *         Parser.cpp
 *         TaggedUnion.cpp
 *         Utils.cpp
 *     main.cpp
 */

Parser.cpp

// Copyright 2017, Victor R. Cabrera
#include "../include/Parser.hpp"

using string_array = std::vector<std::string>;
using list = std::vector<TaggedUnion>;
string_array Parser::split(const std::string & lisp_list) {
    /* create a new list that'll hold each string value in a vector. */
    string_array split_list;
    /* if it's empty, there is nothing to compute. */
    if (!lisp_list.empty()) {
        auto curr_val = "";
        auto new_list = lisp_list;

        /* add whitespace to every parentheses, remove every instace of double whitespace, 
         * and then split the list based on whitespace.
         */
            Utils::replaceAll(new_list, "(", " ( ");
            Utils::replaceAll(new_list, ")", " ) ");
            Utils::replaceAll(new_list, "  ", " ");

        /* split the list based on whitespace. */
        split_list = Utils::split(new_list, ' ');

        /* If the value is a list and not an atom, the first parentheses will have a trailing whitespace
         * and that will store into the first pos in the vector as an empty string. Deleting that will
         * make the list validly split.
         */
        if (split_list[0] == "") {
            split_list.erase(split_list.begin());
        }
    }
    return split_list;
}

list Parser::parse(const std::string & lisp_list) {
    string_array split_list = split(lisp_list);
    list parsed_list;

    /* If the split list isn't empty, it is time to parse it. */
    if (!split_list.empty()) {
        int i = 0;

        /* Use a helper function to recursely parse the vector. */
        parsed_list = parseHelper(split_list, i);
    }
    return parsed_list;
}

list Parser::parseHelper(const string_array & split_list,
                         int & i) {
    /* Create a new list to represent the current list. */
    list new_list;

    for (i; i < split_list.size(); ++i) {
        /* If the string is "(", then it signifies a new list. */
        if (split_list[i] == "(") {
            /* recursively call this function on the new list, and then push it back to represent
             * a nested list.
             */
            new_list.push_back(TaggedUnion(parseHelper(split_list, ++i)));
        /* If the string is ")", this signifies the end of a list. */
        } else if (split_list[i] == ")") {
            return new_list;
        /* Otherwise, you should categorize the value. */
        } else {
            categorize(new_list, split_list[i]);
        }
    }
}


void Parser::categorize(list & list, const std::string & str) {
	/* If it's an int, store it as an int constant.
	 * Else if it's a double, store it as an float constant.
	 * Else if it's a string with quotes around it, store it as a string constant.
	 * Else, the string is an identifier for a function, so store it as that.
	 */
    if (Utils::isInt(str)) {
        list.push_back(TaggedUnion(std::stoi(str), Label::Atom));
    } else if (Utils::isFloat(str)) {
        list.push_back(TaggedUnion(std::stof(str), Label::Atom));
    } else if (str[0] == '"' && str[str.size() - 1] == '"') {
        list.push_back(TaggedUnion(str.substr(1, str.size() - 2), Label::Atom));
    } else {
        list.push_back(TaggedUnion(str, Label::Identifier));
    }
}

void Parser::printList(const list & list) {
    /* Print out the list and then show the type of label it is
	 * for debugging.
	 */
    std::cout << "[";
    for (const auto & value : list) {
        switch (value.getType()) {
            case Type::List:
                std::cout << "list ";
                printList(value.getList());
                std::cout << ", ";
                break;
            case Type::String:
                std::cout << "string ";
                std::cout << value.getString() << ": ";
                value.printLabel();
                std::cout << ", ";
                break;
            case Type::Double:
                std::cout << "float ";
                std::cout << value.getDouble() << ": ";
                value.printLabel();
                std::cout << ", ";
                break;
            case Type::Int:
                std::cout << "int ";
                std::cout << value.getInt() << ": ";
                value.printLabel();
                std::cout << ", ";
                break;
        }
    }
    std::cout << "\b\b";
    std::cout << "]";
}

Parser.hpp

// Copyright 2017, Victor R. Cabrera
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include "TaggedUnion.hpp"
#include "Utils.hpp"
#include "enum.hpp"

#ifndef D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_PARSER_HPP_
#define D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_PARSER_HPP_

using string_array = std::vector<std::string>;
using list = std::vector<TaggedUnion>;

/** Parser class
  *
  * CONSTRUCTION: Takes a lisp-like string and parses it into a vector of different types and labels to reflect the value's use in Lisp.
  *
  * ************************************************************************PUBLIC OPERATIONS***************************************************************************
  * vector<string> split(lisp_list)                             		                   --> Split lisp string into an array for each separate string to perform recursion.
  * vector<TaggedUnion> parse(lisp_list)                   				                   --> Parse a lisp string into an array that represents an abstract syntax tree of the lisp code.
  * vector<TaggedUnion> parseHelper(list, i)         					                   --> Recursively establishes the value of each string in lisp in order to parse into a AST.           							
  * void categorize(list, i)                			                                   --> Give a description for the lisp command ("s" is a constant, first is an identifier).
  * void printList(list)						                                           --> prints the values in the list, used as a debugger/proof of concept for the algorithm.
  * 
**/

class Parser {
 public:
    string_array split(const std::string & lisp_list);
    list parse(const std::string & lisp_list);
    list parseHelper(const string_array & list,
                     int & i);
    void categorize(list & list, const std::string & i);
    void printList(const list & list);
};

#endif  //  D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_PARSER_HPP_

TaggedUnion.cpp

// Copyright 2017, Victor R. Cabrera
#include "../include/TaggedUnion.hpp"
using string = std::string;
using list = std::vector<TaggedUnion>;

/* Uninitialized Unions require that you define the constructor, copy constructor, and destructor of 
 * any potential types that contain a non-trivial constructor. This is done for strings and vector<TaggedUnion>'s in this case
 */
TaggedUnion::TaggedUnion(const list& value) :
                         type_(Type::List), label_(Label::Neither) {
    new (&list_value) list(value);
}

TaggedUnion::TaggedUnion(const list&& value) :
                         type_(Type::List), label_(Label::Neither) {
    new (&list_value) list(std::move(value));
}

TaggedUnion::TaggedUnion(const string& value, const Label& label) :
                         type_(Type::String), label_(label)   {
    new (&string_value) string(value);
}

TaggedUnion::TaggedUnion(const string&& value, const Label& label) :
                         type_(Type::String), label_(label) {
    new (&string_value) string(std::move(value));
}

TaggedUnion::TaggedUnion(const char& value, const Label& label) :
                         type_(Type::Char), label_(label) {
    char_value = value;
}

TaggedUnion::TaggedUnion(const int& value, const Label& label) :
                         type_(Type::Int), label_(label) {
    int_value = value;
}

TaggedUnion::TaggedUnion(const double& value, const Label& label) :
                         type_(Type::Double), label_(label) {
    double_value = value;
}

TaggedUnion::TaggedUnion(const TaggedUnion& rhs) :
                         type_(rhs.type_), label_(rhs.label_) {
    switch ( type_ ) {
        case Type::List:
            new (&list_value) list(rhs.list_value);
            break;
        case Type::String:
            new (&string_value) string(rhs.string_value);
            break;
        case Type::Double:
            double_value = rhs.double_value;
            break;
        case Type::Int:
            int_value = rhs.int_value;
            break;
        case Type::Char:
            char_value = rhs.char_value;
            break;
    }
}

TaggedUnion & TaggedUnion::operator=(const TaggedUnion& rhs) {
    if (this != &rhs) {
        if (type_ == Type::String) {
            string_value.~string();
        } else if (type_ == Type::List) {
            list_value.~list();
        }
        type_ = rhs.type_;
        label_ = rhs.label_;
        switch ( type_ ) {
            case Type::List:
                new (&list_value) list(rhs.list_value);
                break;
            case Type::String:
                new (&string_value) string(rhs.string_value);
                break;
            case Type::Double:
                double_value = rhs.double_value;
                break;
            case Type::Int:
                int_value = rhs.int_value;
                break;
            case Type::Char:
                char_value = rhs.char_value;
                break;
        }
    }
    return *this;
}

TaggedUnion::~TaggedUnion() {
    if (type_ == Type::String) {
        string_value.~string();
    } else if (type_ == Type::List) {
        list_value.~list();
    }
}

void TaggedUnion::printLabel() const {
    switch ( label_ ) {
        case Label::Atom:
            std::cout << "atom";
            break;
        case Label::Identifier:
            std::cout << "identifier";
            break;
    }
}

Type TaggedUnion::getType() const {
    return type_;
}

Label TaggedUnion::getLabel() const {
    return label_;
}

char TaggedUnion::getChar() const {
    assert(getType() == Type::Char); return char_value;
}

int TaggedUnion::getInt() const {
    assert(getType() == Type::Int);  return int_value;
}

double TaggedUnion::getDouble() const {
    assert(getType() == Type::Double);  return double_value;
}

string TaggedUnion::getString() const {
    assert(getType() == Type::String); return string_value;
}

list TaggedUnion::getList() const {
    assert(getType() == Type::List); return list_value;
}

TaggedUnion.hpp

// Copyright 2017, Victor R. Cabrera
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include "enum.hpp"

#ifndef D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_TAGGEDUNION_HPP_
#define D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_TAGGEDUNION_HPP_

/** TaggedUnion class
  *
  * CONSTRUCTION: Creates a TaggedUnion class that is able to handle multiple types through an unrestricted union, for the sake of created a nested list of different types in C++
  *
  * ************************************************************************PUBLIC OPERATIONS***************************************************************************
  * void printLabel() const;                                                               --> Prints the TaggedUnion's lisp label_, used for debugging.
  * Type getType() const;                                                                  --> Gets the Type of the TaggedUnion, used to decide which value to return.
  * Label getLabel() const;                                                                --> Gets the Label of the TaggedUnion, used to retrieve the purpose of the value for lisp interpretation.
  * char getChar() const;                                                                  --> Gets the char value stored in the TaggedUnion.
  * int getInt() const;                                                                    --> Gets the int value stored in the TaggedUnion.
  * double getDouble() const;                                                              --> Gets the double value stored in the TaggedUnion.
  * string getString() const;                                                              --> Gets the string value stored in the TaggedUnion.
  * list getList() const;                                                                  --> Gets the list value stored in the TaggedUnion.  
  *                                            
**/

class TaggedUnion {
 private:
    using string = std::string;
    using list = std::vector<TaggedUnion>;
    union {
        char char_value;
        int int_value;
        double double_value;
        string string_value;
        list list_value;
    };
    Type type_;
    Label label_;

 public:
    explicit TaggedUnion(const list& value);
    explicit TaggedUnion(const list&& value);
    explicit TaggedUnion(const string& value, const Label& label);
    explicit TaggedUnion(const string&& value, const Label& label);
    explicit TaggedUnion(const char& value, const Label& label);
    explicit TaggedUnion(const int& value, const Label& label);
    explicit TaggedUnion(const double& value, const Label& label);
    explicit TaggedUnion(const TaggedUnion& rhs);
    TaggedUnion & operator=(const TaggedUnion& rhs);
    ~TaggedUnion();
    void printLabel() const;
    Type getType() const;
    Label getLabel() const;
    char getChar() const;
    int getInt() const;
    double getDouble() const;
    string getString() const;
    list getList() const;
};

#endif  //  D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_TAGGEDUNION_HPP_

Utils.cpp

// Copyright 2017, Victor R. Cabrera
#include "../include/Utils.hpp"

void Utils::replaceAll(std::string & str,
                       const std::string & from,
                       const std::string & to) {
    /* if there's nothing to change, return */
    if ( from.empty() ) {
        return;
    }
    size_t start_pos = 0;

    /* while you can still find instances of the 
     * string you want to change, change it 
     */
    while ((start_pos = str.find(from, start_pos)) != std::string::npos) {
        str.replace(start_pos, from.length(), to);
        start_pos += to.length();
    }
}
std::vector<std::string> Utils::split(const std::string & str, char delimiter) {
    std::vector<std::string> arr;
    std::string word;
    std::istringstream splitStream(str);

	/* use istringstream in order to read the string 
     * and end each read given the delimiter passed 
     */
    while (std::getline(splitStream, word, delimiter)) {
        arr.push_back(word);
    }
    return arr;
}

bool Utils::isInt(const std::string & str) {
    /* checks to see if there is any instance 
     * of a value that is not a number 
     */
    return str.find_first_not_of("0123456789") == std::string::npos;
}

bool Utils::isFloat(const std::string & str) {
    float buffer;
    std::istringstream iss(str);

    /* whitespace is considered invalid */
    iss >> std::noskipws >> buffer;

    /* if the line ends and the buffer didn't 
     * fail to grab the value, this is a valid float 
     */
    return iss.eof() && !iss.fail();
}

Utils.hpp

// Copyright 2017, Victor R. Cabrera
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

#ifndef D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_UTILS_HPP_
#define D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_UTILS_HPP_

/** Utils class
  *
  * CONSTRUCTION: Utility Class fused for convenience since I wanted to avoid the boost library for the sake of allowing easy compilation.
  *
  * ************************************************************************PUBLIC OPERATIONS***************************************************************************
  * vector<string> split(str, delimiter)								                   --> Splits a string into an array based on a delimiter value.
  * void replaceAll(str, from, to)                   								       --> Replaces all instances of a string with a new value.
  * bool isInt(str)         														       --> Checks to see if the tring is convertible to an integer.           							
  * bool isFloat(str)               												       --> Checks to see if the string is convertible to a float.
  * 
**/

class Utils {
 public:
    static std::vector<std::string> split(const std::string & str,
                                          char delimiter);
    static void replaceAll(std::string& str,
                           const std::string& from,
                           const std::string& to);
    static bool isInt(const std::string& str);
    static bool isFloat(const std::string& str);
};

#endif  // D__DOCUMENTS_LISP_INTERPRETER_INCLUDE_UTILS_HPP_