Codility : Supports de Déterminer si une chaîne de parenthèses est correctement imbriquées

Votre première condition dans la parenthèse bloc vérifie si votre pile a la taille != 1. Je suppose que c'est là pour vérifier que vous n'avez pas de restes de l'ouverture des crochets, ce qui est une bonne idée. Cependant, vous allez manquer toute cette case si votre dernier char n'est pas une parenthèse fermante/parenthèse/..

Ce, par exemple, ferait échouer pour une entrée comme (((.

Une solution simple serait de remplacer cette condition par un chèque de après la boucle se termine que la pile est en effet vide.

OriginalL'auteur Leeor

100% JavaScript simple solution

function solution(S) {
S = S.split("");
var stack = [];
for (var i = 0; i < S.length; i++) {
var c = S[i];
if (c == '{' || c == '(' || c == '[')
stack.push(c);
else if (c == '}' || c == ')' || c == ']') {
var t = stack.pop() + c;
if (t != "{}" && t != "()" && t != "[]")
return 0;
}
else 
return 0;
}
if (stack.length > 0)
return 0;
return 1;
}

OriginalL'auteur Jung Oh

Je suis à 100% avec la solution suivante en java. Le temps de la complexité est O(N)

 class Solution {
public int solution(String S) {        
char[] charArray=S.toCharArray();
//This array works as stack
char[] stack=new char[charArray.length];        
//currently stack is empty
int stackSize=0;
for(int i=0;i<charArray.length;i++){
//Check start characters and add it to stack
if(charArray[i]=='{' ||charArray[i]=='(' || charArray[i]=='['){                
stack[stackSize++]=charArray[i];                                
}else{
//This section checks for end character. 
//End characters with stack being empty confirms not nested
if(stackSize==0){
result=0;
break;
}
//Pop stack
char ch=stack[--stackSize];   
//check
if((charArray[i]=='}' && ch=='{') || (charArray[i]==']' && ch=='[') ||(charArray[i]==')' && ch=='(')){                     
continue;
}else{
//if pop character not matching, confirms non nesting 
result=0;
break;
}                   
}
}
//if stack is not empty indicates non nested, otherwise result 
return stackSize==0?result:0;
}

}

OriginalL'auteur krishna

Votre meilleur pari avec ce genre d'erreurs est de s'asseoir et écrit quelques tests unitaires (JUnit est un bon framework) pour vérifier votre compréhension du fonctionnement de l'algorithme.

Dans ce cas, comme Trengot a compris que le "negative_match" entrée ))((, vous aurez envie au moins de ces cas de test:

• ))(( : C'est votre base de test, une fois que ce passage vous êtes remplit les conditions, et peut déclarer au moins partielle de la victoire.
• }}{{ : Est-ce une erreur d'ordre général, ou seulement liées à une mauvaise manipulation d'un personnage en particulier?
• })({ : Est-il lié à la répétition de caractère, ou qu'il ne montre en mixte d'entrée ainsi?
• (}{) : Est-ce un bord de cas liés à avoir une ouverture jeton au début de la chaîne, ou ce comportement ne se présentent plus généralement?

Une fois que vous comprenez ce que c'est fait faire, au lieu de ce que votre cerveau vous dit qu'il est en train de faire (et de votre cerveau sera vous mentir à ce sujet), la correction devrait être assez simple.

OriginalL'auteur Morgen

Code: 06:12:11 UTC, c, final score: 100.00

int solution(char *S) {
//write your code in C99
int len;
if((len=strlen(S))==0) return 1;
char stuck[len];
char open[]="([{";
char close[]=")]}";
int top=0;
for (int i=0;i<len;i++)
{
if (strchr(open,S[i])!=NULL)
{
stuck[top]=S[i];
top++;
} 
else if (strchr(close,S[i])!=NULL)
{
if ((top>0)&&((strchr(open,stuck[top-1])-open)==(strchr(close,S[i])-close)))
top--;
else
return 0;
}
}
if (top==0)
return 1;
return 0;
}

OriginalL'auteur David Yachnis

ici vous avez mon 100% de la solution en java:
https://codility.com/demo/results/training2C7U2E-XM3/

/**
*  https://codility.com/demo/results/training2C7U2E-XM3/100%
*  
* Problem facts:
* 1) A string S consisting of N characters is given
* 2) S is properly nested if:
*      -S is empty;
*      -S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
*      -S has the form "VW" where V and W are properly nested strings.
* 3) N is an integer within the range [0..200,000];
* 4) string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".
* 5) expected worst-case time complexity is O(N);
* 6) expected worst-case space complexity is O(N)
* 
* Solution:
* The idea is to iterate over the string and push opening brackets, then each time a closing bracket appears
* it will be matched with the last opening match stacked, if both are of the same type, then pop that char,
* otherwise return 0.
* If the string S is properly nested the remaining stack will be empty. 
* 
* There are three cases to analize:
* 1) The stack is empty, push the first char.
* 2) The stack is not empty, peek the last char and it is the opening bracket of current closing bracket, then
* pop the char from the stack.
* 3) The stack is not empty, peek the last char and it isn't the opening bracket of current closing bracket, 
* return 0, because the string is malformed.
* 
* @param S
* @return 1 if S is properly nested and 0 otherwise.
*/
public static int solution(String S) {      
if(S.isEmpty()) return 1; //pay attention to corner case 1
if(S.length()==1) return 0; //and 2
Stack<Character> stack = new Stack<>();     
for(int i=0; i<S.length(); i++) {
char current = S.charAt(i);
switch (current) {
case '}':
if (!stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} 
else return 0;
break;
case ']':
if (!stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} 
else return 0;
break;
case ')':
if (!stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} 
else return 0;
break;
default:
stack.push(current);
break;
}   
}
return stack.size()==0 ? 1 : 0;
}

OriginalL'auteur Caesar Avgvstvs

100% Java

public int solution(String S) {
Stack<Character> stack = new Stack<>();    
for(int i=0; i<S.length(); i++) {
char c = S.charAt(i);
if (c == '[' || c == '{' || c == '(' || c == 'V') {
stack.push(c);
} else if (c == ']' || c == '}' || c == ')' || c == 'W') {
if (checkBracket(stack, c)) {
stack.pop();
} else {
return 0;
}  
} else {
return 0;
}
}   
if (stack.empty()) {
return 1;
}
return 0;  
}
private boolean checkBracket(Stack<Character> stack, char bracket) {
if (stack.empty()) return false;
char lastStackBracket = stack.peek();
if (lastStackBracket == '{' && bracket == '}') {
return true;
} else if (lastStackBracket == '[' && bracket == ']') {
return true;
} else if (lastStackBracket == '(' && bracket == ')') {
return true;
} else if (lastStackBracket == 'V' && bracket == 'W') {
return true;
}
return false;
}

bien sûr, vous avez besoin d'importer java.util:

import java.util.*;

OriginalL'auteur Dario Sagud

Ma solution rapide. Devrait fonctionner correctement

public func Brackets(_ S : inout String) -> Int {
var Stack = [Character]()
let matching : [Character:Character] = ["(":")", "[":"]", "{":"}"]
for s in S {
let char = S.removeFirst()
if "({[".contains(char) {
print(char)
Stack.append(char)
}
if( "]})".contains(char)) {
print(char)
let bracket = Stack.removeLast()
if matching[bracket] != char {
return 0
}
}
}
return 1
}
var S1 = "{[()()]}"
var S2 = "([)()]"
print("Brackets: ", Brackets(&S1))
print("Brackets: ", Brackets(&S2))

OriginalL'auteur Michał Ziobro

Ne pouvais pas trouver toutes les scripts python... mais ici il est! Essayé de le garder aussi simple que possible.

def solution(S):
# write your code in Python 3.6
arr = []
if len(S) < 1:
return 1
if not isinstance(S, str):
return 0
for i in range(0, len(S)):
# print(S[i])
if startSym(S[i]):
arr.append(value(S[i]))
# print(arr)
elif endSym(S[i]):
if len(arr) > 0 and value(S[i]) == arr[len(arr) - 1]:
# print(S[i])
# print(arr)
del arr[len(arr) - 1]
else:
return 0
else:
return 0
if len(arr) == 0:
return 1
else:
return 0
def startSym(x):
if x == '{' or x == '[' or x == '(':
return True
else:
return False
def endSym(x):
if x == '}' or x == ']' or x == ')':
return True
else:
return False
def value(x):
if x == '{' or x == '}':
return 1
if x == '[' or x == ']':
return 2
if x == '(' or x == ')':
return 3

OriginalL'auteur TheoreticallyNick