patterncppMinor
Matching parenthesis
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.
I'm practicing Data Structures questions on HackerRank, any suggestions to improve code quality appreciated!
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:
-
-
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 initialize a
-
Not sure why the range based loop variable is called
-
-
-
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
-
-
You don't have to explicitly
Update
Regarding your question of making
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.
-
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 theinputvector 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.