Saturday, September 18, 2010

Pairing algorithm

I cam across a very good question, I posted my anwser in java, If any one interested can post it in any other languages also.

Write a function, Brackets(n), where n is an integer, which will print all valid pairings of parenthesis. For example, Brackets(3) should print
()()()
(())()
()(())
(()())
((()))

Try not to use brute force and generate 2^n combinations.

My solution to the above question in JAVA is

package solved200;

import java.util.Stack;

public class Brackets {

private final int n;

String open = "(";
String close = ")";
String[] tokens = new String[]{open, close};

Stack mainStack;
int count;

public Brackets(int n) {
this.n = 2*n;
mainStack = new Stack
();
}

public void printBrackets(){
printBracketsHelper(this.n, 0, 0);
}

private void printBracketsHelper(int k, int numCloseBrackets, int numOpenBrackets){

if(k == 0){
if( numOpenBrackets == numCloseBrackets) {
count++;
printStack();
}
return;
}
for(int i = 0; i < tokens.length; i++){ boolean addToStack = false; String curToken = tokens[i]; if(mainStack.size() == 0) { if( curToken.equals(close)) { push(curToken); numCloseBrackets++; addToStack = true; } } else { if( curToken.equals(open)){ if( numOpenBrackets + 1 <= numCloseBrackets) { push(curToken); numOpenBrackets++; addToStack = true; } } else if( curToken.equals(close)){ if( numOpenBrackets <= numCloseBrackets + 1) { push(curToken); numCloseBrackets++; addToStack = true; } } } if( addToStack ) { printBracketsHelper(k-1, numCloseBrackets, numOpenBrackets); String popStr = mainStack.pop(); if( popStr.equals(close)) numCloseBrackets--; else if (popStr.equals(open)) numOpenBrackets--; } } } private String push(String curToken) { // System.out.println("PUSH " + curToken); return mainStack.push(curToken); } private void printStack() { System.out.print(count + ": "); for(int i = mainStack.size() - 1; i>=0; i--){
System.out.print(mainStack.get(i));
}
System.out.println();
}

public static void main(String[] args) {
Brackets b = new Brackets(15);
b.printBrackets();
System.out.println("Total : " + b.count);
}

}

No comments:

Post a Comment