Matching parenthesis

Question

This is a simple implementation of a parenthesis-matcher. Given an expression, I want to find out if it is balanced.For example, the expression '{{[[()]]}}' is balanced while '{]{{}}]]' is not. I will output a simple 'NO' is the expression is not balanced and 'YES' if it is.

The algorithm is to push every opening parenthesis into a stack and match it against every closing when when pop-ed.

#include <iostream>
#include <vector>
#include <set>
#include<stack>
#include <utility>
#include <string>

bool contains(std::set<char> & inset, char elem){
  return inset.find(elem) != inset.end();
}

bool charmatch(char a,char b){
  return ((a == '(' && b == ')') ||
          (a == '{' && b == '}') ||
          (a == '[' && b == ']'));
}

void process(std::string inputArg){
  std::vector<char> input(inputArg.begin(), inputArg.end());

  std::set<char> openParen;
  openParen.insert('(');openParen.insert('{');openParen.insert('[');

  std::set<char> closeParen;
  closeParen.insert(')');closeParen.insert('}');closeParen.insert(']');


  std::stack<char> exprStack;
  for (auto i : input){
    char inputChar = i;
    if (contains(openParen, inputChar))
      {
        exprStack.push(inputChar);
        continue;
      }

    else if (exprStack.empty() || !charmatch(exprStack.top(),inputChar)){
      std::cout << "NO" <<std::endl;
      return;
    }

    exprStack.pop();


  }
  if (exprStack.empty())  {std::cout << "YES" << std::endl; return;}
  else {std::cout << "NO" << std::endl; return;}
}


int main()
{
  std::vector<char> input;
  int num;std::string inputString;
  std::cin >> num;
  for (int i = 0; i < num; i++){
      std::cin >> inputString;
        process(inputString);
    }
  return 0;
}

I'm practicing Data Structures questions on HackerRank, any suggestions to improve code quality appreciated!

Answer 1

Let's go top down:

1. charmatch is a bad name for the function. parenMatch would make much more sense.

2. Judging by the one range-based for loop, you're using C++11 - so might as well use it to the full extend:

   • You can use range-based for loops directly on a std::string. There is no need to copy it into a vector. So the input vector can be removed.

   • You can initialize a std::set with an initializer list:

     std::set<char> openParen = { '(', '[', '{' };
     

   • Not sure why the range based loop variable is called i just to be copied into a loop-local variable called inputChar. You might as well name the loop variable that way.

     for (auto inputChar : inputArg) {
         ....
     

3. closeParen is never used and can be removed.

4. exprStack is not really the best name - parenStack would be more appropriate.

5. You should use spaces more consistently. Your indent is off here and there and you often omit a space before the opening brace which doesn't help readability. Also a lot of people prefer 4 spaces indent but YMMV.

6. Use a consistent bracing style. Sometimes you put the opening brace on it's own line and sometimes it's on the previous one and sometimes the entire block is on one line.

7. I'd return a bool from process instead of writing directly to std::out - let the caller deal with the output concern (Single Responsibility Principle).

8. input in main is never used and should be removed.

9. You don't have to explicitly return 0 from main.

---

Update

Regarding your question of making charmatch more efficient: charmatch is already pretty efficient - at most 8 compares and 3 ANDs. You could turn it into a switch:

bool parenMatch(char left, char right)
{
    switch (left)
    {
        case '(': return right == ')';
        case '[': return right == ']';
        case '{': return right == '}';
    }
    return false;
}

However this is a micro-optimization which will probably have close to no effect on the execution speed, in fact I wouldn't be surprised if the generated code is almost the same.