通過翻譯的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"]
最後一部分是有點劈十歲上下,因爲它依賴於µ
字符串(不是我的問題),在沒有被解決了一個錯誤,其中)
在輸入字符串的結束是導致不正確的輸出,在每個字符串的末尾插入一個µ
,然後從結果中剝離它。我會很高興有人提出更好的方法來處理這些問題,因此它可以作爲更一般的解決方案。
這個代碼,因爲它代表了我所需要的一切。感謝你的幫助!
你可以爲你自己的正則表達式編寫一個解析器,然後遍歷所有的可能性。但是,杜克林給出的鏈接有一個現有的圖書館來完成這一代。 – nhahtdh 2013-02-10 14:04:23
@Dukeling:他有正則表達式,他想要生成所有匹配它的字符串。 – nhahtdh 2013-02-10 14:04:52
@billy ...只是讓你知道,我在下面更新了我的答案 - 我的本地解析器爲「?」現在似乎產生了比賽...有趣的挑戰。 – 2013-02-11 06:50:44