题目描述

如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。

花括号展开的表达式可以看作一个由 花括号、逗号 和 小写英文字母 组成的字符串，定义下面几条语法规则：

• 如果只给出单一的元素 x，那么表达式表示的字符串就只有 "x"。R(x) = {x}
  • 例如，表达式 "a" 表示字符串 "a"。
  • 而表达式 "w" 就表示字符串 "w"。
• 当两个或多个表达式并列，以逗号分隔，我们取这些表达式中元素的并集。R({e_1,e_2,...}) = R(e_1) ∪ R(e_2) ∪ ...
  • 例如，表达式 "{a,b,c}" 表示字符串 "a","b","c"。
  • 而表达式 "{{a,b},{b,c}}" 也可以表示字符串 "a","b","c"。
• 要是两个或多个表达式相接，中间没有隔开时，我们从这些表达式中各取一个元素依次连接形成字符串。R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)}
  • 例如，表达式 "{a,b}{c,d}" 表示字符串 "ac","ad","bc","bd"。
• 表达式之间允许嵌套，单一元素与表达式的连接也是允许的。
  • 例如，表达式 "a{b,c,d}" 表示字符串 "ab","ac","ad"。
  • 例如，表达式 "a{b,c}{d,e}f{g,h}" 可以表示字符串 "abdfg", "abdfh", "abefg", "abefh", "acdfg", "acdfh", "acefg", "acefh"。

给出表示基于给定语法规则的表达式 expression，返回它所表示的所有字符串组成的有序列表。

样例

输入：expression = "{a,b}{c,{d,e}}"
输出：["ac","ad","ae","bc","bd","be"]

输入：expression = "{{a,z},a{b,c},{ab,z}}"
输出：["a","ab","ac","z"]
解释：输出中 不应 出现重复的组合结果。

限制

• 1 <= expression.length <= 60
• expression[i] 由 '{'、'}'、',' 或小写英文字母组成。
• 给出的表达式 expression 用以表示一组基于题目描述中语法构造的字符串。

算法

(栈/表达式求值) $O(n)$

1. 为了处理方便，先将原表达式按照一下步骤转化为标准表达式：
   • 在每个小写字母的两侧添加 {}。
   • 在每一处 }{ 中间插入 *。
   • 在开头和结尾分别加入 { 和 }。
2. 将花括号看作小括号，* 看作乘号，, 看作加号，计算该表达式的值。
3. 值不再是数字，而是一个集合。乘号的优先级高于加号。
4. 定义集合栈和符号栈两个栈来求值。

C++ 代码

class Solution {
private:
    void add(unordered_set<string> &x, const unordered_set<string> &y) {
        for (const auto &s : y)
            x.insert(s);
    }

    void mul(unordered_set<string> &x, const unordered_set<string> &y) {
        unordered_set<string> z;
        for (const auto &a : x)
            for (const auto &b : y)
                z.insert(a + b);

        x = z;
    }

    void init(string &expression) {
        string t;
        for (char c : expression) {
            if (c >= 'a' && c <= 'z') {
                t += "{"; t += c; t += "}";
            } else {
                t += c;
            }
        }

        expression = "";
        for (int i = 0; i < t.size(); i++) {
            expression += t[i];
            if (i < t.size() - 1 && t[i] == '}' && t[i + 1] == '{')
                expression += '*';
        }

        expression = "{" + expression + "}";
    }

public:
    vector<string> braceExpansionII(string expression) {
        init(expression);

        stack<unordered_set<string>> e;
        stack<char> op;

        for (char c : expression) {
            if (c == '{') {
                op.push(c);
            } else if (c == '}') {
                while (!op.empty() && op.top() != '{') {
                    unordered_set<string> top = e.top();
                    e.pop();

                    if (op.top() == ',') add(e.top(), top);
                    else if (op.top() == '*') mul(e.top(), top);

                    op.pop();
                }
                op.pop();
            } else if (c == ',') {
                while (!op.empty() && (op.top() == ',' || op.top() == '*')) {
                    unordered_set<string> top = e.top();
                    e.pop();

                    if (op.top() == ',') add(e.top(), top);
                    else if (op.top() == '*') mul(e.top(), top);

                    op.pop();
                }
                op.push(c);
            } else if (c == '*') {
                while (!op.empty() && op.top() == '*') {
                    unordered_set<string> top = e.top();
                    e.pop();

                    mul(e.top(), top);

                    op.pop();
                }
                op.push(c);
            } else {
                string t = string(1, c);
                unordered_set<string> r;
                r.insert(t);
                e.push(r);
            }
        }

        vector<string> ans(e.top().begin(), e.top().end());
        sort(ans.begin(), ans.end());

        return ans;
    }
};