解析字符串

水深无声 2023-03-04 05:28 12阅读 0赞

## 一、前言 ##

昨天一个朋友在应聘一家公司，公司给了他一道字符串解析的问题，按照自己的思路记录一下。

## 二、题目 ##

/**
    * 目标：解析字符串(完成时间48小时内)
    * 格式: src="t1a=t1b&t2a=t2b&t3a=t3b"
    * 结果: map[t1a]=t1b,map[t2a]=t2b,map[t3a]=t3b
    * 要求: 1>使用辅助类型TokenizerEx(测试源文件中包含Tokenizer.h Tokenizer.cpp),可以使用STL中任何数据结构和算法
    *      2>由于格式中有'='和'&',但是要求t1a和t1b中可能也会有这两个字符,于是用 "\=" "\&" 代替 '=' '&'
    *      3>需要转义的字符不限于 "\=" "\&", 有可能会增加 "\?" 等其他字符
    *      4>支持容错处理并过滤掉'\0'字符,比如 src="&t1a=t1b&t2a=t2b" 或 src="&t1a=t1b&" 或 src="" 的情况均可正常运行
    *      5>代码注释齐全,代码逻辑简洁,尽可能考虑效率问题
    * 示例: "\\?124\0=34\\&5\\&&xy\0\\&=45\\=\n\\?" 应被解析为 map["?124"]="34&5&",map["xy&"]="45=\n?"
    * 说明: 这是当前项目中的一个实际问题，考察面试者
    *      1>代码阅读能力
    *      2>独立解决问题的能力
    *      3>代码质量(可阅读性,效率)
    *      4>做事的认真程度以及耐心程度
    * 建议: 如果代码逻辑考虑不周全，提前时间完成并不会得到更好的测试成绩
    * 后续: 此测试通过后,来项目组阅读项目中关于这个问题的实现代码并进一步面试(面试时间可能会比较久，请面试者做好心理准备)
    */

##  ##

## 三、需求分析 ##

接下来说到的 = &，指划分字符。

### 3.1 题意中需求 ###

1.  对字符串进行解析，解析成多组数据，每组数据由key—value构成数据对
2.  每组数据划分是通过 & 进行划分，如果 & 是转义字符，则 \\& 只能看着普通的字符&
3.  每组数据对是通过 = 进行划分，如果 = 是转义字符，则 \\= 只能看着普通的字符=
4.  过滤掉 ‘\\0’
5.  支持转义字符定义
6.  支持容错处理

### 3.2 待确定需求 ###

由于题目是朋友给的，里面有一些情况无法通过题意和实例进行确认，待确定的问题如下：

1.  如果key值有重复需要怎样处理？
2.  对于正常的字符格式应该是 = & = & 交替出现，如果 = = 或者 & & 连续出现，需要怎样处理？
3.  对于正常的字符格式应该是 = & = & 交替出现，= 前面为空，或者 = 与 & 之间为空，或者 & 与 = 之间为空 需要怎样处理？

自己暂时处理方法：

1.  问题一，key值重复出现后面的会覆盖掉前面的value值，并打印提示信息
2.  问题二，若 = 或 & 重复出现，根据当前遍历终止节点进行查找，若需要遍历一个key值则需要遍历到=为止，若为空则当前数据组无效，例如 a=b&=c，第一组数据是(a,b), 第二组数据key为空，value为c，第二组数据无效
3.  问题三，处理方法和问题二一样

### 3.3 闲谈 ###

在实际工作中，需要先明确需求，再开始设计和编码。需求不明确一切都白忙。这里无法询问不确定需求就先按照自己的理解进行实现。

## 四、思路 ##

接下来说到的 = &，指划分字符。

### 4.1 初步设计方案 ###

上面需求分析完，思路基本也就清晰了。

1.  按照 & 进行划分 获得一组有效的数据组
2.  对一组数据进按照 = 划分获得 key-value
3.  过滤key-value值中的 ‘\\0’ 和 转义字符
4.  循环执行这个过程即可

### 4.2 优化方案 ###

1.  按照 = 和 & 划分获取 key值和 value值
2.  过滤key-value值中的 ‘\\0’ 和 转义字符
3.  循环执行这个过程

由于 = & 是交替出现了，那么我们可以将4.1中的步骤1和步骤2进行合并，也就是实现一个函数它们在遇到 = 或者 & 时 终止遍历并返回字符串。程序实现如下：

// 解析一对数据
        pair<string, string> parseAPairOfData()
        {
            string lstr = parseAData('=');  // key值
            string rstr = parseAData('&');  // value值
            return make_pair(lstr, rstr);
        }

复杂度分析：

时间复杂度 O(n)，从前往后扫描n个字符，过滤掉无效字符和转义字符执行n次，总共执行的次数是 2n ，时间复杂度O(n)。

空间复杂度 O(n)，用到了辅助空间。

### 4.3 优化版本2 ###

1.  在一次遍历中找到一个有效的key和value值
2.  循环执行步骤1

4.2中在计算key或value进行了两次计算，这里将其合并为一次。

复杂度分析：

时间复杂度 O(n)，从前往后扫描1次，扫描n个字符。

空间复杂度 O(n)，用到了辅助空间。

## 五、总结 ##

1.  先确定需求再设计编码
2.  优化过程需要逐步进行，如果功力深厚一次优化到位当然是最棒的。不能一步到位就逐渐优化，先满足基本功能再优化
3.  测试用例还不够多，可能会存在没有考虑到的情况

## 六、编码实现 ##

//==========================================================================
    /*
    * @file    : EscapeStringParse.h
    * @label   : 解析字符串
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107730530
    * @author  : niebingyu
    * @date    : 2020/07/31
    * @title   : 解析字符串
    * @purpose :  目标：解析字符串(完成时间48小时内)
    * 格式: src="t1a=t1b&t2a=t2b&t3a=t3b"
    * 结果: map[t1a]=t1b,map[t2a]=t2b,map[t3a]=t3b
    * 要求: 1>使用辅助类型TokenizerEx(测试源文件中包含Tokenizer.h Tokenizer.cpp),可以使用STL中任何数据结构和算法
    *      2>由于格式中有'='和'&',但是要求t1a和t1b中可能也会有这两个字符,于是用 "\=" "\&" 代替 '=' '&'
    *      3>需要转义的字符不限于 "\=" "\&", 有可能会增加 "\?" 等其他字符
    *      4>支持容错处理并过滤掉'\0'字符,比如 src="&t1a=t1b&t2a=t2b" 或 src="&t1a=t1b&" 或 src="" 的情况均可正常运行
    *      5>代码注释齐全,代码逻辑简洁,尽可能考虑效率问题
    * 示例: "\\?124\0=34\\&5\\&&xy\0\\&=45\\=\n\\?" 应被解析为 map["?124"]="34&5&",map["xy&"]="45=\n?"
    * 说明: 这是当前项目中的一个实际问题，考察面试者
    *      1>代码阅读能力
    *      2>独立解决问题的能力
    *      3>代码质量(可阅读性,效率)
    *      4>做事的认真程度以及耐心程度
    * 建议: 如果代码逻辑考虑不周全，提前时间完成并不会得到更好的测试成绩
    * 后续: 此测试通过后,来项目组阅读项目中关于这个问题的实现代码并进一步面试(面试时间可能会比较久，请面试者做好心理准备)
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <map>
    #include <vector>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_ESCAPESTRINGPARSE namespace NAME_ESCAPESTRINGPARSE {
    #define NAMESPACE_ESCAPESTRINGPARSEEND }
    NAMESPACE_ESCAPESTRINGPARSE
    
    // 校验key值是否重复
    #define DUPLICATION_CHECK 
    
    // 时间复杂度 O(n)。从前往后扫描1次，扫描n个字符。
    // 空间复杂度 O(n)。用到了辅助空间。
    class escape_str_parse
    {
    private:
        char m_EscapeChar[CHAR_MAX];        // 转义字符
        size_t m_CurIndex;                  // 当前遍历下标
        string m_EscapeString;              // 待转义的字符串
    
    public:
        map<string, string> operator()(string src, const std::initializer_list<char>& escape_char)
        {
            Init(src, escape_char);
            map<string, string> ans;
            while (m_CurIndex < m_EscapeString.size())
            {
                pair<string, string> ret = parseAPairOfData();
                if (!ret.first.empty() && !ret.second.empty())
                {
    #ifdef DUPLICATION_CHECK
                    // key 重复校验
                    if (ans.find(ret.first) != ans.end())
                    {
                        cout << "字符key值出现重复，后面的会覆盖前面值，待转义字符串："<< src << "，key:" << ret.first << endl;
                    }
    #endif // DUPLICATION_CHECK
                    ans[ret.first] = ret.second;
                }
            }
    
            return move(ans);
        }
    
    private:
        // 初始化
        void Init(string src, const std::initializer_list<char>& escape_char)
        {
            m_CurIndex = 0;
            m_EscapeString = src;
            memset(m_EscapeChar, 0, sizeof(m_EscapeChar));
            for (auto c : escape_char)
                ++m_EscapeChar[c];
        }
    
        // 解析一对数据
        pair<string, string> parseAPairOfData()
        {
            string lstr = parseAData('=');  // key值
            string rstr = parseAData('&');  // value值
            return make_pair(lstr, rstr);
        }
    
        // 解析一对数据，优化后的版本
        // 在一次遍历过中，就可以找到key值或者value值，执行次数为 n 次
        string parseAData(char esc)
        {
            if (m_CurIndex >= m_EscapeString.size() || m_EscapeString[m_CurIndex] == esc)
            {
                ++m_CurIndex;
                return "";
            }
    
            string ret;
            size_t ei = m_CurIndex;
            for (; ei < m_EscapeString.size() - 1; ++ei)
            {
                if (m_EscapeString[ei] == '\0')
                    continue;
    
                if (m_EscapeString[ei] == esc)
                    break;
    
                if (m_EscapeString[ei] == '\\' && m_EscapeChar[m_EscapeString[ei + 1]] > 0)
                    ++ei;
    
                ret += m_EscapeString[ei];
            }
    
            // 如果是字符最后一个字符, 有两种情况不能包含
            // 1.最后一个字符是空字符需要过滤掉
            // 2.最后一个字符是 ‘&’也就是下一个数据组划分，不能计算在上一个字符中，例如 a=b&, 数据组为(a,b),只有一个有效的数据组。  
            if (ei == m_EscapeString.size() - 1 && m_EscapeString[ei] != '\0' && m_EscapeString[ei] != '&')
                ret += m_EscapeString[ei++];
    
            m_CurIndex = ei + 1;
            return ret;
        }
    
        // 解析一对数据，老版本
        // 先找到key或者value值，之后再去掉需要过滤的字符和转义字符，执行次数为 2n 次
        string parseAData_old(char esc)
        {
            if (m_CurIndex >= m_EscapeString.size() || m_EscapeString[m_CurIndex] == esc)
            {
                ++m_CurIndex;
                return "";
            }
    
            size_t ei = m_CurIndex;
            for (; ei < m_EscapeString.size(); ++ei)
            {
                if (m_EscapeString[ei] == esc)
                {
                    if (ei - 1 >= m_CurIndex && m_EscapeString[ei - 1] == '\\' && m_EscapeChar[esc] != 0)
                        continue;
                    break;
                }
            }
    
            // 返回：去掉无效字符, 过滤掉'\0'字符 和 转义字符
            string str = removeInvalidCharacters(m_CurIndex, ei);
            m_CurIndex = ei + 1;
            return str;
        }
    
        // 去掉无效字符, 过滤掉'\0'字符 和 转义字符
        // 字符串范围[si, ei), 可以减少拷贝 
        string removeInvalidCharacters(size_t si, size_t ei)
        {
            if (si >= ei)
                return "";
    
            string ret;
            size_t i = si;
            while (i < ei - 1)
            {
                if (m_EscapeString[i] == '\0')
                {
                    ++i;
                    continue;
                }
    
                if (m_EscapeString[i] == '\\' && m_EscapeChar[m_EscapeString[i + 1]] > 0)
                    ++i;
    
                ret += m_EscapeString[i++];
            }
    
            if (i == ei - 1 && m_EscapeString[i] != '\0')
                ret += m_EscapeString[i];
    
            return ret;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, string src, const std::initializer_list<char>& escape_char, map<string, string>& expect)
    {
        escape_str_parse parse;
        map<string, string> result = parse(src, escape_char);
    
        if (result == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        char _src[] = "t1a=t1b&t2a=t2b&t3a=t3b";
        string src(_src, _src + sizeof(_src) - 1);
        const std::initializer_list<char> escape_char = { '?', '&', '=' };
    
        map<string, string> expect =
        {
            make_pair("t1a", "t1b"),
            make_pair("t2a", "t2b"),
            make_pair("t3a", "t3b"),
    
        };
        test("Test1()", src, escape_char, expect);
    }
    
    void Test2()
    {
        char _src[] = "\\?124\0=34\\&5\\&&xy\0\\&=45\\=\n\\?";
        string src(_src, _src + sizeof(_src) - 1);
        const std::initializer_list<char> escape_char = { '?', '&', '=' };
    
        map<string, string> expect = 
        {
            make_pair("?124", "34&5&"),
            make_pair("xy&", "45=\n?"),
        };
        test("Test2()", src, escape_char, expect);
    }
    
    void Test3()
    {
        char _src[] = "&t1a=t1b&t2a=t2b";
        string src(_src, _src + sizeof(_src) - 1);
        const std::initializer_list<char> escape_char = { '?', '&', '=' };
    
        map<string, string> expect =
        {
            make_pair("&t1a", "t1b"),
            make_pair("t2a", "t2b"),
        };
        test("Test3()", src, escape_char, expect);
    }
    
    void Test4()
    {
        char _src[] = "&t1a=t1b&";
        string src(_src, _src + sizeof(_src) - 1);
        const std::initializer_list<char> escape_char = { '?', '&', '=' };
    
        map<string, string> expect =
        {
            make_pair("&t1a", "t1b"),
        };
        test("Test4()", src, escape_char, expect);
    }
    
    void Test5()
    {
        char _src[] = "1=&&=1";
        string src(_src, _src + sizeof(_src) - 1);
        const std::initializer_list<char> escape_char = { '?', '&', '=' };
    
        map<string, string> expect =
        {
            make_pair("&", "1"),
        };
        test("Test5()", src, escape_char, expect);
    }
    
    void Test6()
    {
        char _src[] = "1==&&=1";
        string src(_src, _src + sizeof(_src) - 1);
        const std::initializer_list<char> escape_char = { '?', '&', '=' };
    
        map<string, string> expect =
        {
            make_pair("1", "="),
            make_pair("&", "1"),
        };
        test("Test6()", src, escape_char, expect);
    }
    
    void Test7()
    {
        char _src[] = "\\aa\\=b=ab\\a&cd\\===k\\&&&=h\\a";
        string src(_src, _src + sizeof(_src) - 1);
        const std::initializer_list<char> escape_char = { '?', '&', '=', 'a' };
    
        map<string, string> expect =
        {
            make_pair("aa=b", "aba"),
            make_pair("cd=", "=k&"),
            make_pair("&", "ha"),
        };
        test("Test7()", src, escape_char, expect);
    }
    NAMESPACE_ESCAPESTRINGPARSEEND
    // 测试 用例 END
    //
    void EscapeStringParse_Test()
    {
        cout << "------ start 解析字符串 ------" << endl;
        NAME_ESCAPESTRINGPARSE::Test1();
        NAME_ESCAPESTRINGPARSE::Test2();
        NAME_ESCAPESTRINGPARSE::Test3();
        NAME_ESCAPESTRINGPARSE::Test4();
        NAME_ESCAPESTRINGPARSE::Test5();
        NAME_ESCAPESTRINGPARSE::Test6();
        NAME_ESCAPESTRINGPARSE::Test7();
        cout << "------ end 解析字符串 --------" << endl;
    }

**执行结果：**

![20200801144248375.png][]

[20200801144248375.png]: /images/20230208/29a92b6591f646118212c06ac3b06908.png