Codility : Brackets Determine whether a given string of parentheses is properly nested

brackets codility python
determine whether a given string of parentheses multiple types is properly nested
fish codility java
brackets start determine whether a given string of parentheses multiple types is properly nested
word machine emulator codility
codility lesson 8
codility test questions and answers c# pdf
codility r

Problem description from codility :

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

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. For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

class Solution { public int solution(String S); }

that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.

Assume that:

N is an integer within the range [0..200,000]; string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")". Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

I get 87% I cant seem to figure out the problem.

Here is my code :

   // you can also use imports, for example:
// import java.util.*;
import java.util.Stack;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
   public int solution(String s) {

        if (s.length() % 2 != 0) {
            return 0;
        }

        Character openingBrace = new Character('{');
        Character openingBracket = new Character('[');
        Character openingParen = new Character('(');
        Stack<Character> openingStack = new Stack<Character>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == openingBrace || c == openingBracket || c == openingParen) {
                openingStack.push(c);
            } else  {
                if (i == s.length()-1 && openingStack.size() != 1) {
                    return 0;
                }
                if (openingStack.isEmpty()) {
                    return 0;
                }
                Character openingCharacter = openingStack.pop();
                switch (c) {
                case '}':
                    if (!openingCharacter.equals(openingBrace)) {
                        return 0;
                    }
                    break;
                case ']':
                    if (!openingCharacter.equals(openingBracket)) {
                        return 0;
                    }
                    break;
                case ')':
                    if (!openingCharacter.equals(openingParen)) {
                        return 0;
                    }
                    break;

                default:
                    break;
                }
            } 
        }

        return 1;

    }
}

Your first condition in the closing brackets block checks whether your stack has the size != 1. I assume this is meant to check that you don't have any leftover opening brackets, which is a good idea. However, you'll miss this entire check if your last char isn't a closing bracket/paren/..

This for example would fail for an input like (((.

A simple fix would be replacing this condition with a check after the loop ends that the stack is indeed empty.

Brackets coding task - Learn to Code, Determine whether a given string of parentheses (multiple types) is properly nested. Programming language: C, C++, C#, Go, Java 11, Java 8  Brackets – Codility – Solution. Java solution to Codility Brackets problem (Lesson 7 – Stacks and Queues) which scored 100%. The problem is to determine whether a given string of multiple types of parentheses is properly nested. The strategy is to store opening brackets on a stack and pop elements off stack when encounter closing bracket

Passed codility test 100/100 in java.

public static int solution(String S){
    Stack<Character> stack = new Stack<Character>();
    if(null == S){
        return 0;
    }else if(S.isEmpty()){
        return 1;
    }
    for (Character C : S.toCharArray()) {

        switch (C) {
        case ')':
            pops(stack, '(');
            break;
        case '}':
            pops(stack, '{');
            break;
        case ']':
            pops(stack, '[');
            break;

        default:
            stack.push(C);
            break;
        }

    }
    return stack.isEmpty() ? 1 : 0;
}

private static void pops(Stack<Character> s, Character  C){

        while(!s.isEmpty() && s.peek() != C){
            s.pop();
        }
        if(!s.isEmpty()){
            s.pop();
        }else{
            s.push(C);
        }
}

Brackets - Codility - Solution, The problem is to determine whether a given string of multiple types of parentheses is properly nested. The strategy is to store opening brackets on a stack and  Short Problem Definition: Determine whether a given string of parentheses is properly nested. Link Brackets Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(N) Execution: Put every opening bracket on a stack. If a closing bracket is not the same as the top stack bracket, the string is not properly nested. Solution:

Short and clean Python solution to this problem. 100% in Codility

def solution(S):

    matches, stack = dict(['()', '[]', '{}']), []

    for i in S:
        if i in matches.values():
            if stack and matches[stack[-1]] == i:
                stack.pop()
            else:
                return 0
        else:
            stack.append(i)

    return int(not stack)

Codility 'Brackets' Solution, Short Problem Definition: Determine whether a given string of parentheses is properly nested. Link Brackets Complexity: expected worst-case  Codility : Brackets Determine whether a given string of parentheses is properly nested. Tag: java,stack,brackets

100% simple JavaScript 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;
}

Codility 'Nesting' Solution, Just check if there is always a opening bracket before a closing one. Determine whether given string of parentheses is properly nested. codility test for whether given string parentheses are properly nested or not using javascript or jquery with full explaination.

This is my C# simple solution which got 100% for Correctness and 100% Performance. Time Complexity is O(N). https://codility.com/demo/results/trainingRVS3SF-DC6/

using System;
using System.Collections.Generic;

class Solution {

    public int solution(string S) {

        // Return 1 if string size is 0 
        if(S.Length==0) return 1;

        Stack<char> brackets = new Stack<char>();

        foreach(char c in S){
            if(c=='['||c=='{'||c=='('){
                brackets.Push(c);
            }
            else{
                // return 0 if no opening brackets found and 
                // first bracket is a closing bracket
                if(brackets.Count==0) return 0;

                if(c==')'){
                    if(brackets.Peek()=='(') brackets.Pop();
                    else return 0;
                }

                if(c=='}'){
                    if(brackets.Peek()=='{') brackets.Pop();
                    else return 0;
                }

                if(c==']'){
                    if(brackets.Peek()=='[') brackets.Pop();
                    else return 0;
                }
            }
        }

        if(brackets.Count==0) return 1;

        return 0;
    }
}

Codility-Stacks and Queues-Determine whether a given string of , Codility-Stacks and Queues-Determine whether a given string of parentheses is properly nested - Brackets.md. Task:Brackets: Determine whether a given string of parentheses (multiple types) is properly nested. A string S consisting of N characters is considered to be properly nested if any of the following conditions is true: S is empty; S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;

java: Codility : Brackets Determine whether a given string of , Problem description from codility : A string S consisting of N characters is considered to be properly nested if any of the following conditions is  The problem is to determine whether a given string of single type of parentheses is properly nested. The strategy (very similar to the Brackets problem) is to store opening brackets on a stack and pop elements off stack when encounter closing bracket and check that it’s a proper open bracket-close bracket match.

CODILITY: Determine whether given string of parentheses is , Codility : Brackets Determine whether a given string of parentheses is a string S consisting of N characters, returns 1 if S is properly nested  A string S consisting of N characters is considered to be properly nested if any of the following conditions is true: 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.

Codility solution: Brackets, class Solution { public int solution(String S); }. that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0  Brackets. You are given a string S containing a collection of N brackets. You must determine whether the brackets are properly nested; this is the case 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.

Comments
  • Do you have an example of the input that your code is failing to properly validate?
  • I'm getting horrible interview flashbacks from this question.
  • I do not have the input, codiliy does not provide that. I dont know what they mean by "negative_match invalid structures"
  • You can do the test here codility.com/c/intro/demo7MQR6Q-232
  • "negative_match" is ))((
  • fails on solution('a(b)'), why?
  • I make same solution but with php and the performance is different. I create the stack myself ih php since there is no built in stack app.codility.com/demo/results/trainingFR4VME-Q88 Can u recommend any improvement plz
  • I think this fails for '[((())])'. Possibly Codility doesn't properly check nesting. This answer - stackoverflow.com/a/45858026/2734863 - suggests an O(N^2) time algorithm is the only way to do this question in O(1) space if nesting is a concern.
  • I submitted a solution of just System.out.println(S);return 0; and that was the output for that test.
  • @Trengot - Very clever, the simple solution is sometimes the easiest to overlook.
  • It appears they randomly generate test cases. Running it again gave ())((). I wonder if that was the cause of OP's problem.
  • It might or might not be the right answer, but you can make it better by explaining why and how this works.