#include <iostream>
#include <vector>
#include <regex>
#include <algorithm>//copy ,
#include <iterator>//std::back_inserter
#include <stack>

struct Node {
    int val;
    Node * left;
    Node * right;
    Node(int v) { val = v; left = nullptr; right = nullptr; };
};

void stringSplit(const std::string & rawData, std::vector<std::string> & Result, char delim)
{
    // std::regex_token_iterator 是访问底层字符序列内每个正则表达式匹配的单独子匹配的只读老式向前迭代器 (LegacyForwardIterator) 。
    // 它亦可用于访问不为给定的正则表达式所匹配的序列部分（例如作为记号化器）。
    // 构造时，它构造一个 std::regex_iterator ，而在每次自增时，它走过请求的来自当前 match_results 的子匹配，并在自增离开上个子匹配时自增底层的 regex_iterator 。
    // 默认构造的 std::regex_token_iterator 是序列尾迭代器。在抵达最后匹配的最后子匹配自增合法的 std::regex_token_iterator 时，它变得等于序列尾迭代器。进一步解引用或自增它引发未定义行为。
    // 在恰好变为序列尾迭代器前，若请求的子匹配下标列表中出现 -1 （非匹配碎片），则 std::regex_token_iterator 可成为后缀迭代器。若解引用这种迭代器，则返回对应最后匹配和序列结尾之间的字符序列的 match_results 。
    // std::regex_token_iterator 的典型实现保有底层的 std::regex_iterator 、请求的子匹配下标的容器（例如 std::vector<int> ）、等于子匹配下标的内部计数器、指向当前匹配的当前子匹配的指向 std::sub_match 指针和含有最近非匹配字符序列的 std::match_results 对象（用于记号化器模式）。
    std::regex rgx(",");//正则表达式对象
                        //std::sregex_token_iterator iter();
                        /*std::copy(std::sregex_token_iterator(rawData.begin(), rawData.end(), rgx, -1), std::sregex_token_iterator(),
                        std::ostream_iterator<std::string>(std::cout, "\n"));*/
    std::copy(std::sregex_token_iterator(rawData.begin(), rawData.end(), rgx, -1), std::sregex_token_iterator(), std::back_inserter(Result));
}

//前序序列化，中序无序列化，会导致歧义。
void PreOrderSerial(Node * node, std::string & Ret, char sep)
{
    if (node == nullptr)
    {
        Ret.append("null");
        Ret.push_back(sep);
        return;
    }
    Ret.append(std::to_string(node->val));
    Ret.push_back(sep);//加分隔符
    PreOrderSerial(node->left, Ret, sep);
    PreOrderSerial(node->right, Ret, sep);
}

void buildPreOrderSerial(std::string & raw, Node  * & node, char sep)
{
    std::vector<std::string> NodeList_str;
    stringSplit(raw,NodeList_str,sep);//按照sep切割原有的string
    std::stack<Node * > node_STK;
    Node * nowNode = nullptr;
    node = nullptr;
    char flag = 0x00;
    for (auto d:NodeList_str)
    {
        try
        {
            int tempVal = std::stoi(d);
            if (node == nullptr)//初始化节点
            {
                nowNode = new Node(tempVal);
                node = nowNode;
            }
            else if (flag == 0x01)
            {
                nowNode->right = new Node(tempVal);
                nowNode = nowNode->left;
                flag = 0x00;
            }
            else if (flag == 0x00)
            {
                nowNode->left = new Node(tempVal);
                nowNode = nowNode->left;
            }
            node_STK.emplace(nowNode);
        }
        catch (std::invalid_argument&) { //null情况。
            // if no conversion could be performed
            //std::cout << "Invalid_argument" << std::endl;
            flag = 0x01;
            if (!node_STK.empty())
            {
                nowNode = node_STK.top();
                node_STK.pop();
            }
        }
        catch (std::out_of_range&) {
            // if the converted value would fall out of the range of the result type 
            // or if the underlying function (std::strtol or std::strtoull) sets errno 
            // to ERANGE.
            std::cout << "Out of range" << std::endl;
        }
        catch (...) {
            // everything else
            std::cout << "Something else" << std::endl;
        }
    }
}

int main()
{
    Node * begin = new Node(1);
    Node * nowpos = begin;
    nowpos->left = new Node(2);
    nowpos->left->left = new Node(3);
    nowpos->right = new Node(3);
    begin->right = new Node(4);
    std::string Res;
    PreOrderSerial(begin, Res, ',');
    Node * buidNode = nullptr;
    buildPreOrderSerial(Res,buidNode,',');
    
    std::string compStr;
    PreOrderSerial(buidNode, compStr, ',');
    std::cout << Res << std::endl << compStr;
    return 0;
}