HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Matching parenthesis

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
matchingparenthesisstackoverflow

Problem

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 
#include 
#include 
#include
#include 
#include 

bool contains(std::set & 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 input(inputArg.begin(), inputArg.end());

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

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

  std::stack 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  input;
  int num;std::string inputString;
  std::cin >> num;
  for (int i = 0; i > inputString;
        process(inputString);
    }
  return 0;
}


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

Solution

Let's go top down:

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

-
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 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) {
    ....


-
closeParen is never used and can be removed.

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

-
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.

-
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.

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

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

-
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.

Code Snippets

std::set<char> openParen = { '(', '[', '{' };
for (auto inputChar : inputArg) {
    ....
bool parenMatch(char left, char right)
{
    switch (left)
    {
        case '(': return right == ')';
        case '[': return right == ']';
        case '{': return right == '}';
    }
    return false;
}

Context

StackExchange Code Review Q#119908, answer score: 4

Revisions (0)

No revisions yet.