Under the grammar given below, strings can represent a set of lowercase words. Let&nbsp;R(expr)&nbsp;denote the set of words the expression represents.

The 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 two 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 three rules for our grammar:


	For every lowercase letter x, we have R(x) = {x}.
	For expressions e1, e2, ... , ek with k &gt;= 2, we have R({e1, e2, ...}) = R(e1) ∪ R(e2) ∪ ...
	For expressions e1 and e2, we have R(e1 + e2) = {a + b for (a, b) in R(e1) × R(e2)}, 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.

&nbsp;
Example 1:

Input: expression = "{a,b}{c,{d,e}}"
Output: ["ac","ad","ae","bc","bd","be"]


Example 2:

Input: expression = "{{a,z},a{b,c},{ab,z}}"
Output: ["a","ab","ac","z"]
Explanation: Each distinct word is written only once in the final answer.


&nbsp;
Constraints:


	1 &lt;= expression.length &lt;= 60
	expression[i] consists of '{', '}', ','or lowercase English letters.
	The given&nbsp;expression&nbsp;represents a set of words based on the grammar given in the description.


class Solution:
    def braceExpansionII(self, expression: str) -> List[str]:
        s = list(reversed("{" + expression + "}"))
        
        def full_word(): 
            cur = [] 
            while s and s[-1].isalpha():    
                cur.append(s.pop())            
            return "".join(cur)
        
        def _expr(): 
            res = set()    
            if s[-1].isalpha(): 
                res.add(full_word())    
            elif s[-1] == "{":   
                s.pop() # remove open brace
                res.update(_expr()) 
                while s and s[-1] == ",": 
                    s.pop() # remove comma 
                    res.update(_expr())    
                s.pop() # remove close brace 
            while s and s[-1] not in "},": 
                res = {e + o for o in _expr() for e in res}
            return res    
        
        return sorted(_expr()) 
class Solution {
    // To Get the value of index traversed in a recursive call.
    int index = 0;

    public List<String> braceExpansionII(String expression) {
        List<String> result = util(0, expression);
        Set<String> set = new TreeSet<>();
        set.addAll(result);
        return new ArrayList<>(set);
    }

    List<String> util(int startIndex, String expression) {
        // This represents processed List in the current recursion.
        List<String> currentSet = new ArrayList<>();
        boolean isAdditive = false;
        String currentString = "";
        // This represents List that is being processed and not yet merged to currentSet.
        List<String> currentList = new ArrayList<>();

        for (int i = startIndex; i < expression.length(); ++i) {

            if (expression.charAt(i) == ',') {
                isAdditive = true;
                if (currentString != "" && currentList.size() == 0) {
                    currentSet.add(currentString);
                }

                else if (currentList.size() > 0) {
                    for (var entry : currentList) {
                        currentSet.add(entry);
                    }
                }

                currentString = "";
                currentList = new ArrayList<>();
            } else if (expression.charAt(i) >= 'a' && expression.charAt(i) <= 'z') {
               if (currentList.size() > 0) {
                  List<String> tempStringList = new ArrayList<>();
                   for (var entry : currentList) {
                       tempStringList.add(entry + expression.charAt(i));
                   }
                   currentList = tempStringList;
               } else {
                currentString = currentString + expression.charAt(i);
               }
            } else if (expression.charAt(i) == '{') {
                List<String> list = util(i + 1, expression);
                // System.out.println(list);
                // Need to merge the returned List. It could be one of the following.
                // 1- ..., {a,b,c}
                // 2- a{a,b,c}
                // 3- {a,b,c}{d,e,f}
                // 3- {a,b,c}d
                if (i > startIndex && expression.charAt(i - 1) == ',') {
                    // Case 1
                    currentList = list;
                } else {
                    if (currentList.size() > 0) {
                        List <String> tempList = new ArrayList<>();
                        for (var entry1 : currentList) {
                            for (var entry2 : list) {
                                // CASE 3
                                tempList.add(entry1 + currentString + entry2);
                            }
                        }

                        // System.out.println(currentList);
                        currentList = tempList;
                        currentString = "";
                    }

                    else if (currentString != "") {
                        List<String> tempList = new ArrayList<>();
                        for (var entry : list) {
                            // case 2
                            tempList.add(currentString + entry);
                        }

                        currentString = "";
                        currentList = tempList;
                    } else {
                        // CASE 1
                        currentList = list;
                    }
                }

                // Increment i to end of next recursion's processing.
                i = index;
            } else if (expression.charAt(i) == '}') {
                if (currentString != "") {
                    currentSet.add(currentString);
                }

                // {a{b,c,d}}
                if (currentList.size() > 0) {
                    for (var entry : currentList) {

                        currentSet.add(entry + currentString);
                    }
                    currentList = new ArrayList<>();
                }

                index = i;
                return new ArrayList<>(currentSet);
            }
        }

        if (currentList.size() > 0) {

            currentSet.addAll(currentList);
        }

        // {...}a
        if (currentString != "") {

            List<String> tempSet = new ArrayList<>();
            if (currentSet.size() > 0) {
            for (var entry : currentSet) {
                tempSet.add(entry + currentString);
            }

            currentSet = tempSet;
            } else {
                currentSet = new ArrayList<>();
                currentSet.add(currentString);
            }
        }

        return new ArrayList<>(currentSet);
    }
}
class Solution {
public:
    vector<string> braceExpansionII(string expression) {
        string ss;
        int n = expression.size();
        for(int i = 0; i < n; i++){
            if(expression[i] == ','){
                ss += '+';
            }
            else{
                ss += expression[i];
                if((isalpha(expression[i]) || expression[i] == '}') && i+1 < n && (isalpha(expression[i+1]) || expression[i+1] == '{')){
                    ss += '*';
                }
            }
        }
        
        stack<char>stk1;
        vector<string>postfix;
        for(char c:ss){
            if(c == '{'){
                stk1.push(c);
            } else if(c == '}') {
                while(stk1.top() != '{'){
                    postfix.push_back(string(1, stk1.top()));
                    stk1.pop();
                }
                stk1.pop();
            } else if(c == '+'){
                while(!stk1.empty() && (stk1.top() == '+' || stk1.top() == '*')){
                    postfix.push_back(string(1, stk1.top()));
                    stk1.pop();
                }
                stk1.push(c);
            } else if(c == '*'){
                while(!stk1.empty() && stk1.top() == '*'){
                    postfix.push_back(string(1, stk1.top()));
                    stk1.pop();
                }
                stk1.push(c);
            } else {
                postfix.push_back(string(1, c));
            }
        }
        while(!stk1.empty()){
            postfix.push_back(string(1, stk1.top()));
            stk1.pop();
        }
        /*for(string sp:postfix){
            cout << sp << " ";
        }
        cout << endl;*/
        stack<vector<string>>cont;
        for(string s:postfix){
            if(isalpha(s[0])){
                cont.push({s});
            } else {
                vector<string>second = cont.top();
                cont.pop();
                vector<string>first = cont.top();
                cont.pop();
                
                if(s[0] == '+'){
                    for(string sec:second){
                        first.push_back(sec);
                    }
                    cont.push(first);
                } else {
                    vector<string>cartesian;
                    for(string fst:first){
                        for(string sec:second){
                            cartesian.push_back(fst + sec);
                        }
                    }
                    cont.push(cartesian);
                }
            }
        }
        set<string>sstr;
        for(string sc:cont.top()){
            sstr.insert(sc);
        }
        
        vector<string>ret(sstr.begin(), sstr.end());
        return ret;
    }
};```
var braceExpansionII = function(expression) { // , mutiplier = ['']
    const char = ('{' + expression + '}').split('').values()
    const result = [...rc(char)];
    result.sort((a,b) => a.localeCompare(b));
    return result;
};

function rc (char) {
    const result = new Set();  
    
    let resolved = ['']
    let chars = '';
    let currentChar = char.next().value; 
   
    while (currentChar !== '}' && currentChar) {
        if (currentChar === '{') {
            resolved = mix(mix(resolved, [chars]), rc(char));
            chars = '';
        } else if (currentChar === ',') {
            for (const v of mix(resolved, [chars])) {
                result.add(v);
            }
            chars = '';
            resolved = [''];
        } else {
            chars += currentChar;
        }
        currentChar = char.next().value;
    }
    
    for (const v of mix(resolved, [chars])) {
        result.add(v);
    }
    
    return result; // everything
}

function mix (a, b) {
    const result = [];
    for (const ca of a) {
        for (const cb of b) {
            result.push(ca + cb);
        }
    }
    return result;
}
Brace Expansion II