需要找到左括号和右括号,如果违反左括号和右括号的顺序,则返回 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
在尽可能短的时间内,对可能令您感到困惑的行进行注释。
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
现在,您正在将每个左括号放入一个数组中,然后将每个右括号的左括号推入另一个数组中,然后对它们进行比较。有点浪费了
相反,您可以维护一个堆栈。将一个开放标签推入堆栈,如果找到右括号 - 从堆栈中弹出
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))
。
这可能是一个更简单的解决方案:
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
您可以将堆栈与带有单个 for 循环的 switch 语句结合使用,以实现高效的时间和空间复杂度
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)
您可以使用函数
String.prototype.replace
来收集括号并使用一种堆栈来比较每个字符。 为了知道最后压入的括号是什么,堆栈很有用。
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
我希望这能解决您的问题...
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
我的方法会有点不同。 这些括号对位于第一次出现之后的 ASCII 对中。 表示“(”位于“)”(第 40 处)之后(第 41 处)。 所以,如果有一个字符串输入{[()]}并且是有序的。 我们可以将字符串除以长度/2 并检查 ASCII 值 + 1
我认为这是最好的解决方案。
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
}
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;
}
const mapBac = new Map([
['{', '}'],
['(', ')'],
['[', ']'],
[')', '('],
['}', '{'],
[']', '[']
])
const isValid = (string_:string) => {
const n: string[] = [...string_];
return [ ...n.reduce((object, a, index) => {
const found = mapBac.get(a);
if(found){
object.set(a, {
pair: {value: found, count: n.filter((v) => v == found)},
count: n.filter((v) => v == a)
})
}
return object;
},new Map()).values()].every((v) => ( v.count.length === v.pair.count.length));
};
console.log( isValid("()[]{}{}{}()((((()))))["));