Переводя код Java сформировать ссылку, предоставленную @Dukeling в JavaScript, я думаю, что решить мою проблему ...
var Node = function(str){
this.bracket = false;
this.children = [];
this.s = str;
this.next = null;
this.addChild = function(child){
this.children.push(child);
}
}
var printTree = function(root,prefix){
prefix = prefix.replace(/\./g, "");
for(i in root.children){
var child = root.children[i]
printTree(child, prefix + root.s);
}
if(root.children.length < 1){
console.log(prefix + root.s);
}
}
var Stack = function(){
this.arr = []
this.push = function(item){
this.arr.push(item)
}
this.pop = function(){
return this.arr.pop()
}
this.peek = function(){
return this.arr[this.arr.length-1]
}
}
var createTree = function(s){
// this line was causing errors for `a(((b|c)d)e)f` because the `(((` was only
// replacing the forst two brackets.
// var s = s.replace(/(\(|\||\))(\(|\||\))/g, "$1.$2");
// this line fixes it
var s = s.replace(/[(|)]+/g, function(x){ return x.split('').join('.') });
var str = s.split('');
var stack = new Stack();
var root = new Node("");
stack.push(root); // start node
var justFinishedBrackets = false;
for(i in str){
var c = str[i]
if(c == '('){
stack.peek().next = new Node("Y"); // node after brackets
stack.peek().bracket = true; // node before brackets
} else if (c == '|' || c == ')'){
var last = stack.peek(); // for (ab|cd)e, remember b/d so we can add child e to it
while (!stack.peek().bracket){ // while not node before brackets
stack.pop();
}
last.addChild(stack.peek().next); // for (b|c)d, add d as child to b/c
} else {
if (justFinishedBrackets){
var next = stack.pop().next;
next.s = "" + c;
stack.push(next);
} else {
var n = new Node(""+c);
stack.peek().addChild(n);
stack.push(n);
}
}
justFinishedBrackets = (c == ')');
}
return root;
}
// Test it out
var str = "a(c|mo(r|l))e";
var root = createTree(str);
printTree(root, "");
// Prints: ace/amore/amole
Я только изменил одну строку, чтобы дать больше двух последовательные скобки должны быть обработаны, и оставили оригинальный перевод в комментариях
Я также добавил функцию возвращает массив результатов, вместо того, чтобы печатать их ...
var getTree = function(root,prefix){
this.out = this.out || []
prefix = prefix.replace(/\./g, "");
for(i in root.children){
var child = root.children[i]
getTree(child, prefix + root.s, out);
}
if(root.children.length < 1){
this.out.push(prefix + root.s);
}
if(!prefix && !root.s){
var out = this.out;
this.out = null
return out;
}
}
// Test it
var str = "a(b|c)d";
var root = createTree(str);
console.log(getTree(root, ""));
// logs ["abd","acd"]
Последняя часть, чтобы для пустых строк тоже, так что ... (ab|c|) означает ab или c или nothing, и удобство клавиш, так что ab?c переводится в a(b|)c.
var getMatches = function(str){
str = str.replace(/(.)\?/g,"($1|)")
// replace all instances of `(???|)` with `(???|µ)`
// the µ will be stripped out later
str = str.replace(/\|\)/g,"|µ)")
// fix issues where last character is `)` by inserting token `µ`
// which will be stripped out later
str = str+"µ"
var root = createTree(str);
var res = getTree(root, "");
// strip out token µ
for(i in res){
res[i] = res[i].replace(/µ/g,"")
}
// return the array of results
return res
}
getMatches("a(bc|de?)?f");
// Returns: ["abcf","adef","adf","af"]
Последняя часть немного хак-иш, как он полагается на µ не будучи в строке (не проблема для меня) и решает одну ошибку, когда ) в конце на входной строке приводившая неверный вывод, вставив µ в конце каждой строки и затем удалив его из результатов. Я был бы рад, если бы кто-то предложил лучший способ справиться с этими проблемами, поэтому он может работать как более общее решение.
Этот код в его нынешнем виде делает все, что мне нужно. Спасибо за вашу помощь!
Вы можете написать парсер для своего собственного регулярного выражения, а затем пройти через все возможности. Но ссылка Dukeling дала имеющуюся библиотеку, чтобы сделать поколение. – nhahtdh
@Dukeling: У него есть регулярное выражение, и он хочет сгенерировать все строки, которые соответствуют ему. – nhahtdh
@billy ... просто чтобы вы знали, я обновил свой ответ ниже - мой доморощенный парсер для «?» теперь, похоже, создает матчи ... Интересный вызов. –