How to check the sequence of opening and closing brackets in string?

Question

Need to find open and closed bracket, if the sequence of opening and closing brackets is violated, then return false.

But if don't revert right array to compare with left array, i don't make check brackets here {[(3+1)+2]+}. And if reverse like now, then i fail to check here [1+1]+(2*2)-{3/3}

function brackets(expression){
    let leftArr=[];
    let rightArr = [];
    for(let i=0; i<expression.length; i++){
    		if(expression[i] === '(' || expression[i] === '[' || expression[i] === "{"){
        	leftArr.push(expression[i]);
        }
        
        
        if(expression[i] === ')'){
      
        		rightArr.push("(");
        }else if(expression[i] === '}'){
        
        		rightArr.push("{");
        } else if(expression[i] === ']'){
        
        		rightArr.push("[");
        }
   }
		
   rightArr.reverse();
    
    if(leftArr.length<rightArr.length || leftArr.length>rightArr.length){
    return false;
    }
    
    for(let k=0; k<leftArr.length; k++) {
    		if(leftArr[k] != rightArr[k]){
        		return false;
        }
    }

    return true;
}



console.log(brackets('(3+{1-1)}')); // false
console.log(brackets('{[(3+1)+2]+}')); //true
console.log(brackets('[1+1]+(2*2)-{3/3}')); //true
console.log(brackets('(({[(((1)-2)+3)-3]/3}-3)')); //false

Aseptic

so basically you want to check if every opened bracket is closed? – Stimulant

Yea, and also check their order of opening and closing brackets like in that string (3+{1-1)} – Aseptic

Possible duplicate of Missing parentheses with Regex – Bergen

Answer 1

In the shortest possible, with comments for lines that are probably confusing for you.

function check(expr){
    const holder = []
    const openBrackets = ['(','{','[']
    const closedBrackets = [')','}',']']
    for (let letter of expr) { // loop trought all letters of expr
        if(openBrackets.includes(letter)){ // if its oppening bracket
            holder.push(letter)
        }else if(closedBrackets.includes(letter)){ // if its closing
            const openPair = openBrackets[closedBrackets.indexOf(letter)] // find its pair
            if(holder[holder.length - 1] === openPair){ // check if that pair is the last element in the array
                holder.splice(-1,1) // if so, remove it
            }else{ // if its not
                holder.push(letter)
                break // exit loop
            }
        }
    }
    return (holder.length === 0) // return true if length is 0, otherwise false
}
check('[[{asd}]]') /// true

Stimulant

Answer 2

Right now you are getting every single open bracket into one array, then pushing an open bracket for every closing one into another array, then comparing them. That's a bit wasteful.

Instead, you can maintain a stack. Push an open tag onto the stack and if you find a close bracket - pop from the stack

• if there is no match or nothing on the stack when you pop, terminate with a failure
• if you finish with a stack size of zero, then you are successful

function brackets(expression) {
  let stack = [];
  let current;
  const matchLookup = {
        "(": ")", 
        "[": "]", 
        "{": "}", 
      };
                    
  for (let i = 0; i < expression.length; i++) {
    current = expression[i]; //easier than writing it over and over
    
    if (current === '(' || current === '[' || current === "{") {
      stack.push(current);
      
    } else if (current === ')' || current === ']' || current === "}") {
      const lastBracket = stack.pop();
      
      if (matchLookup[lastBracket] !== current) { //if the stack is empty, .pop() returns undefined, so this expression is still correct
      
        return false; //terminate immediately - no need to continue scanning the string
      }
    }
  }
  
  return stack.length === 0; //any elements mean brackets left open
}

console.log(brackets('(3+{1-1)}')); // false
console.log(brackets('{[(3+1)+2]+}')); //true
console.log(brackets('[1+1]+(2*2)-{3/3}')); //true
console.log(brackets('(({[(((1)-2)+3)-3]/3}-3)')); //false

I have used an object to lookup the values but it need not be one. An alternative is to use two arrays that you have to keep in sync

opening = ["(", "[", "{"]
closing = [")", "]", "}"]

On the other hand, if you have those, you can shorten your if checks to if (open.includes(current)) and if (closing.includes(current)).

Mendy

Answer 3

This can be an easier solution:

const checkBrackets = (expression) => {
  const stack = [];
  const bracketLookup = {
    '{': '}',
    '(': ')',
    '[': ']',
  };

  for (const key of expression) {
    if(Object.keys(bracketLookup).includes(key)) { // matches open brackets
      stack.push(key);
    } else if(Object.values(bracketLookup).includes(key)) { //matches closed brackets
      const lastBracket = stack.pop();
      if(bracketLookup[lastBracket] !== key) {
        return false;
      }

    }
  }
  return stack.length === 0;
}

Results:

checkBrackets('a(fg(a)}'); // false
checkBrackets('[1+1)+(2*2]-{3/3}'); // false
checkBrackets('a(d-h)+y{hh}||[hh-a-]'); // true

Rhodia

Very elegant and clean solution. – Taxeme

Answer 4

You can use stack with switch statement with a single for loop for efficient time and space complexity

function checkParantesis(str) {
    const stack = [];
    for (let s of str) {
       if (s == '(' || s == '[' || s == '{') {
          stack.push(s);
          continue; 
       }

       if (stack.length === 0) {
           return false
       }

       switch (s) {
           case ')':
                stack.pop();
                if (s == '{' || s == '[') {
                  return false  
                }
                break;
           case '}':
                stack.pop();
                if (s == '(' || s == '[') {
                  return false  
                }
                break;
           case ']':
                stack.pop();
                if (s == '{' || s == '(') {
                  return false  
                }
                break;
       }
    }
    return stack.length ? false : true
}

const output = checkParantesis('{{}}'));
console.log(output)

Omalley

switch (s) { case ')': stack.pop(); if (s == '{' || s == '[') { return false } break; Why need if statement inside case , it will always be false – Durarte

Answer 5

I hope this will solve your problem...

function brackets(expression) {
    let leftArr=[];
    
    for(let i=0; i<expression.length; i++) {
        if(expression[i] === '(' || expression[i] === '[' || expression[i] === "{") {
            leftArr.push(expression[i]);
        } 
        
        let leftArrLength = leftArr.length;
        
        if(expression[i] === ')' && leftArr[leftArrLength - 1] === '('){
            leftArr.pop();
        }else if(expression[i] === '}' && leftArr[leftArrLength - 1] === '{') {
            leftArr.pop();
        } else if(expression[i] === ']' && leftArr[leftArrLength - 1] === '[') {  
            leftArr.pop();
        }
        else if(expression[i] === ')' || expression[i] === '}' || expression[i] === ']'){
         return false;
        }
    }
	
    return leftArr.length === 0;
}



console.log(brackets('(3+{1-1)}')); // false
console.log(brackets('{[(3+1)+2]+}')); //true
console.log(brackets('[1+1]+(2*2)-{3/3}')); //true
console.log(brackets('(({[(((1)-2)+3)-3]/3}-3)')); //false
console.log(brackets('(((([[[[{{{3}}}]]]]))))')); //false

Tuberculin

crush on (((([[[{{{3}}}]]]])))) , must be false – Aseptic

Answer 6

You can use the function String.prototype.replace to gather the brackets and use a kind of stack to compare each char. The stack is useful in order to know what was the last pushed bracket.

let check = (e) => {
  let brackets = [],
      stack = [],
      map = {'}': '{', ']': '[', ')': '('};

  e.replace(/[\[\]\{\}\(\)]/g, (m) => m && brackets.push(m));

  for (let i = 0, {length} = brackets; i < length; i++) {
    if (['}', ']', ')'].includes(brackets[i])) {
      if (stack.pop() !== map[brackets[i]]) return false;
    } else stack.push(brackets[i]);
  }

  return !stack.length;
};
    
    
console.log(check('(3+{1-1)}')); // false
console.log(check('{[(3+1)+2]+}')); //true
console.log(check('[1+1]+(2*2)-{3/3}')); //true
console.log(check('(({[(((1)-2)+3)-3]/3}-3)')); //false

Cecum

This seems really complex to read and understand! – Ronni

@AsadShakeel why? – Cecum

spacing and one-liner conditions. Can you please add some comments as well in the code? – Ronni

Answer 7

My approach will be a little different. These bracket pairs lie in the ASCII pair right after there first occurence. Means '(' is placed (at 41) after ')' (at 40). So, if there is a string input {[()]} and are in order. We can divide the string by length/2 and check for ASCII value + 1

Ima

Answer 8

I think this the best solution.

const checkBracketSequenceBalance = (exp) => {

    const pairs = {
        '(': ')',
        '[': ']',
        '{': '}'
    },      
    open = []

    for (let i = 0; i < exp.length; i++)
        if (pairs[exp[i]])
            open.push(exp[i])
        else if (exp[i] === pairs[open[open.length - 1]])
            open.pop()

    return !open.length
}

Maser

Answer 9

var input = "[({([])})]";
    console.log(checkPairs(input));
    function checkPairs(input=null) {
        var arr = input.split("");
        var result = false;
        var tmpArr = [];
        if ((arr.length % 2) == 0) {
            arr.forEach(element => {
                if (tmpArr[element] == null) {
                    tmpArr[element] = 1;
                } else {
                    tmpArr[element] += 1;
                }
            });
            if (tmpArr['['] == tmpArr[']'] && tmpArr['('] == tmpArr[')'] && tmpArr['{'] == tmpArr['}']) {
                result = true;
            }
        }
        return result;
    }

Venturesome

Answer 10

const mapBac = new Map([
        ['{', '}'],
        ['(', ')'],
        ['[', ']'],
        [')', '('],
        ['}', '{'],
        [']', '[']
    ])

    const isValid = (comingString:string) => {
        const newArray: string[] = [...comingString];

        return [ ...newArray.reduce((sets, currentValue) => {

            const founded = mapBac.get(currentValue);

            if(founded){
                sets.add({
                    main: newArray.filter((value) => value == founded),
                    pair:  newArray.filter((value) => value === currentValue)
                })
            }

            return sets;

            // @ts-ignore
        },new Set())].every((value) => ( value.pair.length === value.main.length));
    };

    console.log( isValid("((())(ad///]))")); // false
    console.log( isValid("((())(ad///))")) // true
    console.log( isValid("([{()}])()[]{}")) // true

Nakamura

Judging by the following snippet (comingString:string) you seem to have provided you answer in TypeScript (or another Javascript abstraction). Please provide your answer in Vanilla Javascript. – Woodbury