How to verify all matching Brackets

Question

Implement function verify(text) which verifies whether parentheses within text are correctly nested. You need to consider three kinds: (), [], <> and only these kinds. Examples:

verify("---(++++)----")  -> 1 
verify("") -> 1 
verify("before ( middle []) after ") -> 1  
verify(") (") -> 0 
verify("<(   >)") -> 0 
verify("(  [   <>  ()  ]  <>  )") -> 1 
verify("   (      [)") -> 0

I tried to do it as below but the interviewer told that there was an error and is giving me a second chance.

function verify(text) {
  const stack = [];
  for (const c of text) {
    if (c === '(') stack.unshift(')')
    else if (c === '[') stack.unshift(']')
    else if (c === '<') stack.unshift('>')
    else if (c === stack[0]) stack.shift()
    else if (c === ')' || c === ']' || c === '>') return 0
  }
  return 1
}


const test_inputs = ["---(++++)----", "", "before ( middle []) after ", ") (", "<( >)", "( [ <> () ] <> )", " ( [)"]
for (const i in test_inputs) {
  console.log(verify(i))
}

The output is:

The test code is wrong. `for (const i in test_inputs)` should be `for (const i of test_inputs)` — Barmar, Dec 22 '21 at 21:00
No-one is going to solve an interview question for you. What have you tried? What is not working? What do you think is not working, or what don't you understand? If you have specific questions we can help. — Kevin Hooke, Dec 22 '21 at 21:00
Your function has no `return 1` statement, I don't see how it could ever produce the result you say. — Barmar, Dec 22 '21 at 21:00
Your logic is very wrong. You should return `0` if `stack` is empty when you try to unshift. After the loop is done, return `1` if the array is empty, otherwise return `0`. — Barmar, Dec 22 '21 at 21:02
@KevinHooke His attempt is shown, it just doesn't do what OP claims it does. — gre_gor, Dec 22 '21 at 21:02

score 0 · Answer 1 · answered Dec 22 '21 at 22:02

The only thing wrong with your code is, that you used in int the for loop instead of of.
Or forgot to do verify(test_inputs[i]) instead of verify(i).

Fixing that, it produces the right result:

function verify(text) {
  const stack = [];
  for (const c of text) {
    if (c === '(') stack.unshift(')')
    else if (c === '[') stack.unshift(']')
    else if (c === '<') stack.unshift('>')
    else if (c === stack[0]) stack.shift()
    else if (c === ')' || c === ']' || c === '>') return 0
  }
  return 1
}


const test_inputs = [
    "---(++++)----",
    "",
    "before ( middle []) after ",
    ") (",
    "<( >)",
    "( [ <> () ] <> )",
    " ( [)"
]
for (const s of test_inputs) {
  console.log(verify(s), s)
}

score -1 · Accepted Answer · answered Dec 22 '21 at 21:33

We can use the pop and push functions of Array. When we encounter with '(', '[', '<' characters, we push to the stack. On the other hand, when we encounter ')', ']', '>', we pop the last element of stack. If we can't find the equivalents of these characters, we determine that the string is not valid. Finally, if there are no elements left in the stack, this means the string is valid.

function verify(text) {
    let stack = [];
    for (const c of text) {
        if (c === '(' || c == '[' || c == '<') {
            stack.push(c);
        } else if (c === ')' || c == ']' || c == '>') {
            if (stack.length == 0) {
                return 0;
            }
            const popValue = stack.pop();
            if (c === ')' && popValue != '(') {
                return 0;
            } else if (c === ']' && popValue != '[') {
                return 0;
            } else if (c === '>' && popValue != '<') {
                return 0;
            }
        }

    }

    if (stack.length > 0) {
        return 0;
    }

    return 1;
}

OP is already using a stack. And why did you just provide your own solution instead of explaining what's wrong with OP's? — gre_gor, Dec 22 '21 at 21:57
Thanks for the help. I guess my mistake was using unshift instead of push and pop and for not checking whether the stack is empty or not? — , Dec 22 '21 at 22:05

How to verify all matching Brackets

2 Answers2