如何设计parser

LC726 原子的数量
LC385 迷你语法分析器

• 常用的字母/数字/大小写判断转换函数
• <charconv>的使用
• 设计parser的最佳实践

常用工具

大小写和数字

标准库头文件<ccype>

• 检查字母：isalpha
• 检查字母或数字：isalnum
• 检查大小写：islower, isupper
• 转换大小写：to_upper, to_lower
• 检查数字：isdigit

标准库头文件<charconv>

• 转换字符串到数字

  std::from_chars_result from_chars(const char* first, const char* last, auto& value, int base = 10)

  返回值类型：

  struct from_chars_result {
      const char* ptr;
      std::errc ec;
  };

• 成功时ptr指向首个不匹配的字符。ec被初始化。

• 失败时，ptr == first，且ec == std::errc::invalid_argument

• 转换数字到字符串
  to_string 或者

  std::to_chars_result to_chars(char* first, char* last,
                                auto value, int base = 10);

建议

• 写复杂的parser的时候，可以由小到大。先尝试写能parse一部分的小parser，再将这些小的parser组合成一个大的parser。
• parser的函数签名：

  [[nodiscard]]
  const char* parser(const char* first, const char* last, /*out params*/... args)

  first和last两个指针确定要parse的区间。parse的结果通过引用由outparam输出。返回已经parse的最后位置+1。这样设计parser的好处是：
• 避免使用char**，char *&等，造成不必要的麻烦。

• 和from_chars函数的返回值形式类似，整体思路更清晰。
  写每一个小parser的时候，为了方便逻辑处理，尽量对传入的内容作出假设。这些假设可以在调用小parser的大parser中保证。

• 大parser的主循环可以由下面的构成

  while(first < last)
  {
  	if(*first == /*case 1*/)
  	{
  
  	}
  	else if(*first == /*case 2*/)
  	{
  
  	}
  
  	/* ...... */
  
  	else
  	{
  
  	}
  }

原子的数量

LC726 原子的数量

统计一个给定化学式中所有原子的数量。给定的化学式一定是合法的。化学式中含有括号。
首先我们需要先写能够parse一个元素和其数量的小parser。

/* preconditions:
 *
 * !(first < last)
 * is_upper(*first) 
 */
const char* element_parser(const char* first, const char* last, string_view& element, int& number)
{
  // string is not empty, number is at least 1
  number = 1;
  // find the first lower case letter
  auto element_start = first;
  ++first;
  while(first != last && islower(*first))
  {
    ++first;
  }

  element = string_view{element_start, static_cast<size_t>(first - element_start)};

  auto [ptr, err] = from_chars(first, last, number);

  return ptr;

}

这个parser不考虑括号，并假设传入的[first, last)一定是非空的，合法的。再假设*first一定是一个大写字母。

• 因为有了字符串非空的假设，我们可以确定这个元素的数目至少为1。
• 之后我们移动first指针到下一字符。该字符可能是：
  • 一个小写字母：我们继续移动first，使first所指向的内容不是小写字母。这样我们就找到该元素的名字
  • 一个数字 或 字符串末尾：我们不再移动first，而是开始对数字进行parse
• 调用from_chars，如果first已经移动到字符串末尾 或 first所在的位置不是一个数字，from_chars的调用没有效果，number不会被修改，仍然为1。
• 利用from_chars的返回值调整first的位置。如果没有parse任何数字，则first位置保持不变。

可以观察到我们的element_parser的函数签名和设计和from_chars很相似。但是我们因为不考虑错误处理，所以实现起来会简单的很多。

---

auto formula_parser(const char* first, const char* last, str_int_map& res) -> const char *
{

  while(first != last)
  {
    if(*first == '(')
    {
      auto tmp = unordered_map<string_view, int>{};
      first = formula_parser(first + 1, last, tmp);
      for(const auto& p : tmp)
      {
        res[p.first] += p.second;
      }
      continue;
    }
    else if(*first == ')')
    {
      auto multiplier = int{0};
      ++first;
      auto [ptr, errc] = from_chars(first, last, multiplier);
      if(multiplier)
      {
        for(auto& p : res)
        {
          p.second *= multiplier;
        }
        first = ptr;
      }
      break;
    }
    else
    {
      auto element = string_view{};
      auto number = 0;
      first = element_parser(first, last, element, number);
      if(number)
      {
        res[element] += number;
      }
    }
  }
  return first;
}

接下来我们来设计大parser。这个parser的设计难点就在如何处理'('。函数签名仍然和之前的保持类似。我们用一个unordered_map<string_view, int>来储存结果。

在整个parse的过程中我们可能遇到的：

• 左括号：
  这时我们需要递归地调用一个新的parser，并将返回的结果加到当前的结果上。
• 右括号：
  这时我们需要去parse括号后的数字，并把所有结果都乘上这个数字。
• 大写英文字母
  这时我们需要调用我们的之前写的小parser，尝试parser一个element+数量，并加到结果上。

这里需要注意的是，当我们遇到右括号时，这个parse函数就结束了。因为我们调用parser时有两种可能的情况：

- 我们最初对formula调用parse
- 我们因为遇到左括号调用parse

在这两种情况中，只有因为遇到左括号而调用parse时，才可能遇到右括号。而一旦遇到右括号，我们就没必要再parse下去了，之后的parse应该交给调用他的parser。

迷你语法分析器

LC385 迷你语法分析器

仍然按照写parser的一般形式设计parser

[[nodiscard]]
const char* parser(const char* first, const char* last, /*out params*/... args)

在本题目中则是

[[nodiscard]]
const char* deserialize(const char* first, const char* last, NestedInteger& output)

• 遇到'['时，则建立一个新的NestedInteger，并将其作为output param递归调用::deserialize，将first移动到::deserialize返回的指针位置处。
• 遇到'-'或数字时，则解析该数字，并在output中add一个只有数组的NestedInteger，将first移动到from_chars返回的指针位置处。
• 遇到','，忽略，并将first往前移动一位。
• 遇到']'，忽略，将first往前移动一位，结束parse，返回。

code

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
namespace
{

[[nodiscard]]
const char* deserialize(const char* first, const char* last, NestedInteger& output)
{
  while(first < last)
  {
    if(auto c = *first;
    c == '[')
    {
      auto n = NestedInteger{};
      first = deserialize(++first, last, n);
      output.add(n);
    }
    else if(isdigit(c) || c == '-')
    {
      auto num = 0;
      auto [next, er] = from_chars(first, last, num);
      output.add(NestedInteger{num});
      first = next;
    }
    else if(c == ',')
    {
      ++first;
      continue;
    }
    // c == ']'
    else
    {
      ++first;
      break;
    }
  }

  return first;
}
}
class Solution {
public:
    NestedInteger deserialize(string_view s) {
      auto res = NestedInteger{};
      ::deserialize(s.data(), s.data() + s.size(), res);
      return res.getList().front();
    }
};

---

翻转字符串里的单词

LC151 翻转字符串里的单词

按照写parser的一般思路操作即可：

• 跳过所有前置的' '
• 遇到第一个非' '的字符后，parser进入新模式
  • 记录一开始first的位置为begin
  • 移动first直到!(first < last)或者!(*first != ' ')
  • 记录最后first的位置end
  • 以此时begin和end确定的区间构造string_view放入output之中。
• 以output中所有的string_view结果的逆序构造string即可。
• 注意output可能是空的。

code

namespace
{
  const char* parse_word(const char* first, const char* last, vector<string_view>& output)
  {
    while(first < last)
    {
      // jump over all preleading spaces
      if(*first == ' ')
      {
        ++first;
        continue;
      }
      // first non-space char
      auto begin = first;
      while(*first != ' ' && first < last)
      {
        ++first;
      }
      auto end = first;
      output.emplace_back(&*begin, end - begin);
    }
    return first;
  }
}

class Solution {
public:
    string reverseWords(string_view s) {
      auto ans = vector<string_view>{};
      for(auto i = s.data(); i < s.data() + s.size();)
      {
        i = parse_word(i, s.data() + s.size(), ans);
      }

      auto res = string{};

      for(auto it = ans.rbegin(); it != ans.rend(); ++it)
      {
        res.append(*it);
        res += ' ';
      }
      if(!res.empty())
      {
        res.pop_back();
      }
      return res;
    }
};