Algorithm 202 (Interview Question): Matching Parenthesis in 2 Ways
Tags: javascript, algorithms, beginners, bracket
Published: 2020-04-03 23:08:06

This is a very common interview question. However, this article moves a little advanced as it will not just consider a string of parenthesis (braces or brackets), but a string of any kind of character.

```javascript
matchingParenthesis("Njoku Samson Ebere")
/*
  'No parenthesis found'
*/
matchingParenthesis("{Ebere")
/*
  {
  'parenthesis should be in two(s)'
*/
matchingParenthesis("}{Njoku] (){{}}Samson Ebere")
/*
  }{](){{}}
  'Cannot begin with closing parenthesis'
*/
matchingParenthesis("{Njoku{ (Samson) Ebere[")
/*
  {{()[
  'Cannot end with opening parenthesis'
*/
matchingParenthesis("((() (Samson)") 
/*
  ((()()
  'braces do not match'
*/
matchingParenthesis("{(Ebere) [Njoku](Samson)}")
/*
  {()[]()}
  'All openning brace has a closing brace to match'
*/
```
### Prerequisite
This article assumes that you have basic understanding of javascript's string, array and object methods.

### Let's do this!

* filter(), join(), includes(), spread operator, if...statment, for...of, indexOf(), push(), pop()

```javascript
      function matchingParenthesis(string) {
        const parenthesis = "(){}[]",
          openingParenthesis = "({[",
          closingParenthesis = ")}]";
        let stack = [];

        // extract all parenthesis
        let filteredString = [...string].filter((char) =>
          [...parenthesis].includes(char)
        );
        console.log(filteredString.join(""));

        // terminate if there is no parenthesis found
        if (filteredString.length === 0) return "No parenthesis found";

        // terminate if there is just one parenthesis
        if (filteredString.length === 1)
          return "parenthesis should be in two(s)";

        // terminate if it starts with a closing parenthesis
        if (closingParenthesis.includes(filteredString[0]))
          return "Cannot begin with closing parenthesis";

        // terminate if it ends with an opening parenthesis
        if (
          openingParenthesis.includes(filteredString[filteredString.length - 1])
        )
          return "Cannot end with opening parenthesis";

        // terminate if length is not even number
        if (filteredString.length % 2 === 1) {
          return "unequal openning and closing tags";
        }

        // loop through the filteredString
        for (char of filteredString) {
          // add the current char to the stack if it is an openning brace
          if (openingParenthesis.includes(char)) {
            stack.push(char);
          } else {
            let lastStack = stack[stack.length - 1];

            // if a closing brace match the last opening brace in the stack, 
            // pop the last opening brace from the stack
            if (
              closingParenthesis.indexOf(char) ===
              openingParenthesis.indexOf(lastStack)
            ) {
              stack.pop(lastStack);
            } else {
              return "closing brace does not match opening brace";
            }
          }
        }

        if (stack.length !== 0) return "braces do not match";
        return "All openning brace has a closing brace to match";
      }
```

* filter(), join(), hasOwnProperty(), split(""), if...statment, for...of, match(), push(), pop()

```javascript
      function matchingParenthesis(string) {
        const regEx = /[[\](){}]/gi;
        let stack = [];
        const parenthesisMap = { "(": ")", "{": "}", "[": "]" };

        // extract all parenthesis
        let filteredString = string
          .split("")
          .filter((char) => char.match(regEx));
        console.log(filteredString.join(""));

        // terminate if there is no parenthesis found
        if (filteredString.length === 0) return "No parenthesis found";

        // terminate if there is just one parenthesis
        if (filteredString.length === 1)
          return "parenthesis should be in two(s)";

        // terminate if it starts with a closing parenthesis
        if (!parenthesisMap.hasOwnProperty(filteredString[0]))
          return "Cannot begin with closing parenthesis";

        // terminate if it ends with an opening parenthesis
        if (
          parenthesisMap.hasOwnProperty(
            filteredString[filteredString.length - 1]
          )
        )
          return "Cannot end with opening parenthesis";

        // terminate if length is not even number
        if (filteredString.length % 2 === 1) {
          return "unequal openning and closing tags";
        }

        // loop through the filteredString
        for (char of filteredString) {
          // add the current char to the stack if it is an openning brace
          if (parenthesisMap.hasOwnProperty(char)) {
            stack.push(char);
          } else {
            let lastStack = stack[stack.length - 1];

            // if a closing brace match the last opening brace in the stack, 
            // pop the last opening brace from the stack
            if (char === parenthesisMap[lastStack]) {
              stack.pop(lastStack);
            } else {
              return "closing brace does not match opening brace";
            }
          }
        }

        if (stack.length !== 0) return "braces do not match";
        return "All openning brace has a closing brace to match";
      }
```

### Conclusion
Interview questions like this one we just solved tends to test how far you have dived into algorithm. Starting from the basics is very important.

There are many ways to solve problems programmatically. I will love to know other ways you solved yours in the comment section.

> Up Next: [Algorithm 202: Sock Merchant](https://dev.to/ebereplenty/hackerrank-sock-merchant-1cgh)

If you have questions, comments or suggestions, please drop them in the comment section.

You can also follow and message me on social media platforms. 

**[Twitter](https://twitter.com/eberetwit) | [LinkedIn](https://www.linkedin.com/in/samson-ebere-njoku-profile/) | [Github](https://github.com/EBEREGIT)**

Thank You For Your Time.