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:

1
1
1
1
1
1
1

CodePudding user response：

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

CodePudding user response：

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