如何检查字符串中左括号和右括号的顺序？

Question

需要找到左括号和右括号，如果违反了左括号和右括号的顺序，则返回false。

但是如果不恢复右数组与左数组进行比较，我不会在这里做检查括号{[(3+1)+2]+}。如果像现在这样反转，那么我无法在这里检查[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

Answer 1

在最短的时间内，对可能让您感到困惑的行进行注释。

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

Answer 2

这可能是一个更简单的解决方案：

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;
}

结果：

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

Answer 3

现在，您将每个开括号放入一个数组中，然后将每个闭括号的开括号推入另一个数组，然后比较它们。那有点浪费。

相反，您可以维护一个堆栈。将一个开放标签推入堆栈，如果您找到一个右括号 - 从堆栈中弹出

• 如果弹出时堆栈中没有匹配项或任何内容，则以失败终止
• 如果您以零堆栈大小结束，那么您就成功了

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

我使用了一个对象来查找值，但它不一定是一个。另一种方法是使用两个必须保持同步的数组

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

另一方面，如果您有这些，您可以将if检查缩短为if (open.includes(current))和if (closing.includes(current))。