1096. Brace Expansion II

https://leetcode.com/problems/brace-expansion-ii/

eval针对集合的表达式，括号内代表一个完整的子表达式，","代表并，没有","隔离则代表拼接。这题和Basic Caculator III 思路是一致的，区别在于这里的基本操作数不是数字，而是字符串集合；+替换成了并操作，*成了字符串拼接。除了可以用递归做外，依然可以维持两个栈分别存操作数和操作符。当遇到{时操作符压栈，}时递归处理直到遇到{；*则一直压栈直到遇到+开始处理前面的*。 字符串拼接没有特定的操作符表示，有好几个coner case需要注意。

/*
 * @lc app=leetcode id=1096 lang=cpp
 *
 * [1096] Brace Expansion II
 *
 * https://leetcode.com/problems/brace-expansion-ii/description/
 *
 * algorithms
 * Hard (56.14%)
 * Likes:    81
 * Dislikes: 60
 * Total Accepted:    3.9K
 * Total Submissions: 6.8K
 * Testcase Example:  '"{a,b}{c,{d,e}}"\r'
 *
 * Under a grammar given below, strings can represent a set of lowercase
 * words.  Let's use R(expr) to denote the set of words the expression
 * represents.
 * 
 * Grammar can best be understood through simple examples:
 * 
 * 
 * Single letters represent a singleton set containing that word.
 * 
 * R("a") = {"a"}
 * R("w") = {"w"}
 * 
 * 
 * When we take a comma delimited list of 2 or more expressions, we take the
 * union of possibilities.
 * 
 * R("{a,b,c}") = {"a","b","c"}
 * R("{{a,b},{b,c}}") = {"a","b","c"} (notice the final set only contains each
 * word at most once)
 * 
 * 
 * When we concatenate two expressions, we take the set of possible
 * concatenations between two words where the first word comes from the first
 * expression and the second word comes from the second
 * expression.
 * 
 * R("{a,b}{c,d}") = {"ac","ad","bc","bd"}
 * R("a{b,c}{d,e}f{g,h}") = {"abdfg", "abdfh", "abefg", "abefh", "acdfg",
 * "acdfh", "acefg", "acefh"}
 * 
 * 
 * 
 * 
 * Formally, the 3 rules for our grammar:
 * 
 * 
 * For every lowercase letter x, we have R(x) = {x}
 * For expressions e_1, e_2, ... , e_k with k >= 2, we have R({e_1,e_2,...}) =
 * R(e_1) ∪ R(e_2) ∪ ...
 * For expressions e_1 and e_2, we have R(e_1 + e_2) = {a + b for (a, b) in
 * R(e_1) × R(e_2)}, where + denotes concatenation, and × denotes the cartesian
 * product.
 * 
 * 
 * Given an expression representing a set of words under the given grammar,
 * return the sorted list of words that the expression represents.
 * 
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: "{a,b}{c,{d,e}}"
 * Output: ["ac","ad","ae","bc","bd","be"]
 * 
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: "{{a,z},a{b,c},{ab,z}}"
 * Output: ["a","ab","ac","z"]
 * Explanation: Each distinct word is written only once in the final
 * answer.
 * 
 * 
 * 
 * 
 * Constraints:
 * 
 * 
 * 1 <= expression.length <= 50
 * expression[i] consists of '{', '}', ','or lowercase English letters.
 * The given expression represents a set of words based on the grammar given in
 * the description.
 * 
 * 
 * 
 */
class Solution {
public:
    vector<string> braceExpansionII(string expression) {
        const int N = expression.size();
        stack<set<string>> s;
        stack<char> ops;
        string cur;
        set<string> cur_set; 
        const auto add = [](set<string> &l1, set<string> &l2) {
            set<string> r;
            r.insert(l1.begin(), l1.end());
            r.insert(l2.begin(), l2.end());
            return r;
        };
        const auto mult = [](set<string> &l1, set<string> &l2) {
            set<string> r;
            for (const auto s1 : l1) {
                for (const auto s2 : l2) {
                    r.insert(s1 + s2);
                }
            }
            return r;
        };
        const auto operation = [&](char op, set<string> &a, set<string> &b) {
            switch (op)
            {
            case ',':
                s.push(add(a, b));
                break;
            case '*':
                s.push(mult(a, b));
                break;
            default:
                break;
            }
        };
        for (int i = 0; i < N; ++i) {
            const auto c = expression[i];
            if (c >= 'a' && c <= 'z') {
                cur.push_back(c);
                if (!(expression[i + 1] >= 'a' && expression[i + 1] <= 'z')) {
                    cur_set.insert(cur);
                    s.push(set<string>(cur_set));
                    cur_set.clear();
                    cur.clear();
                }
            } else if (c == '{') {
                if (i > 0 && expression[i - 1] != ',' && expression[i - 1] != '{' && expression[i - 1] != '}') ops.push('*');
                ops.push(c);
            } else if (c == '}') {
                while (ops.top() != '{') {
                    const auto op = ops.top(); ops.pop();
                    auto sec = s.top(); s.pop();
                    auto first = s.top(); s.pop();
                    operation(op, first, sec);
                }
                ops.pop();
                if (i < N - 1 && expression[i + 1] != ',' && expression[i + 1] != '}') ops.push('*');
            } else {
                while (!ops.empty() && ops.top() == '*' && c == ',') {
                    auto sec = s.top(); s.pop();
                    auto first = s.top(); s.pop();
                    operation(ops.top(), first, sec);
                    ops.pop();
                }
                ops.push(c);
            }
        }
        while (s.size() > 1) {
            auto sec = s.top(); s.pop();
            auto first = s.top(); s.pop();
            operation(ops.top(), first, sec);
            ops.pop();
        }
        return vector<string>(s.top().begin(), s.top().end());
    }
};