terça-feira, 19 de novembro de 2019

Java code duel - Balanced strings


oBomProgramador hashtagcodeDuel hashtagcodeChallenge hashtagjava Balanced strings! Você tem um texto marcado com delimitadores: um esquerdo e outro direito. Verifique se, para cada delimitador esquerdo (início) há um delimitador direito e na ordem esperada. Podem estar entrelaçados e aninhados e os delimitadores podem ter qualquer tamanho e diferentes entre si.




Você pode navegar caractere a caractere no String, mas eu escolhi uma abordagem mais rápida: Eu uso substring para ir buscando os próximos tokens diretamente. Isso é o que o método checkNext() faz:

/*
 * Here we have to get the next token. We begin from the end position of the last token.
 * We return the position of the next token (tokens can be of different sizes) or -1.
 * 
 */
private int checkNext(int origin, String text, String left, String right) {
int pos,pos2 = -1;
int returnValue = -1;
pos = text.indexOf(left, origin);
pos2 = text.indexOf(right, origin);
if(pos > -1) {
if(pos2 > -1) {
returnValue = pos < pos2 ? pos : pos2;
}
}
else {
if(pos2 > -1) {
returnValue = pos2;
}
}
return returnValue;
}

Uma vez identificada a posição do próximo token, eu uso uma função para obtê-lo:

/* * Here we get the token  */private String getToken(int pos, String text, String left, String right) { String token = text.substring(pos, pos + left.length()); if(!token.equals(left)) { token = text.substring(pos, pos + right.length()); } return token;}

O método principal é simples: Pega um token, se for delimitador esquerdo, empilha, se for direito, desempilha. A situação da pilha vazia indica se há ou não balanço, ou seja, há um direito para cada esquerdo, mesmo dentro de aninhamentos..

public boolean isBalanced(String text, String left, String right) {
boolean result = true;
Stack<String> stack = new Stack<String>();
int pos = 0;
/*
* Get each token in the text, no matter is left or right.
* If it is a left token, then push it to the stack.
* If it is a right token, then there must be a left token in the stack. Pop it.
* At the end, the stack must be empty.
*/
while ((pos = checkNext(pos, text, left, right))>-1) {
String token = getToken(pos,text,left,right);
if(token.equals(left)) {
stack.push(token);
}
else {
if(stack.isEmpty()) {
result = false;
break;
}
stack.pop();
}
// Lets increment position to avoid loop
pos += token.length();
if(pos >= text.length()) {
break;
}
}
if(!stack.isEmpty()) {
result = false;
}
return result;
}

Para testar, temos o método main:

public static void main (String [] args) {
CheckBalance cb = new CheckBalance();
String testCaseBalanced1 = "<this is a <balanced< string>> ok>";
String testCaseUnbalanced1 = "<this is not a <balanced>> <String>>>";
System.out.println(testCaseBalanced1 + " (balanced): " + cb.isBalanced(testCaseBalanced1, "<", ">"));
System.out.println(testCaseUnbalanced1 + " (unbalanced): " + cb.isBalanced(testCaseUnbalanced1, "<", ">"));

// More cases
String testCaseBalanced2 = "This is a <begin>Balanced<begin>text<end>ok<end> end";
System.out.println(testCaseBalanced2 + " (balanced): " + cb.isBalanced(testCaseBalanced2, "<begin>", "<end>"));
String testCaseUnbalanced2 = "This is a <begin>Balanced<begin>text<end><begin>ok<end> end";
System.out.println(testCaseUnbalanced2 + " (unbalanced): " + cb.isBalanced(testCaseUnbalanced2, "<begin>", "<end>"));
}


Cleuton Sampaio, M.Sc.



Nenhum comentário:

Postar um comentário