Syntax Checker C++ Data Structure - Stack

Question

Syntax Checker is a very common question of c++ programming using the data structure stack. However, this is the advanced level base on this question I found in a reference book. Here is the question:

Base on the question checking the string parentheses balance, the output is to print “Success” if all the brackets [] {} () are matched. Otherwise, print "fail"

Sample Input:
{[()]()}[] //Output:Success
{}([[] //Output:3
{}([[]}] //Output:7
{}{(]} //Output:5
{}{](} //Output:4
( [43]( i++ ; ) ) { lol = 3 ; }  //Output:Success

My code as follow:

#include<iostream>
#include<stack>
#include<string>

bool arePair(char start, char end)
{
    if (start == '(' && end == ')') return true;
    else if (start == '{' && end == '}') return true;
    else if (start == '[' && end == ']') return true;
    return false;
}
bool areParanthesesBalanced(std::string exp)
{
    std::stack<char>  S;
    for (int i = 0; i < exp.size(); i++)
    {
        char c = exp.at(i);
        if (c == '(' || c == '{' || c == '[')
            S.push(exp.at(i));
        else if (c == ')' || c == '}' || c == ']')
        {
            if (S.empty()|| !arePair(S.top(), c)) {
                return false;
            }
            else {
                S.pop();
            }
        }
    }
    return S.empty() ? true : false;
}
int main(){
    std::string input;
    while (std::getline(std::cin, input)) {
        if (areParanthesesBalanced(input))
            std::cout << "Success"<< std::endl;
        else
            std::cout << "Fail" << std::endl;
    }
    return 0;
}

Answer 1

Ok, first things first, there are a couple of formatting points that would make your code a little nicer to read:

• Be consistent with your curly braces {}. In a couple of places, you have the opening brace on the same line as the thing before it whereas you don't in others.
• Be consistent with your naming too. I would name your stack s because it fits better with the camelCase used elsewhere.
• Spaces on your #include <header>s too please. It's just nitpicking but it's what most other programmers will be doing / used to.

That aside, lets get into the body of the code itself:

• bool arePair(char, char) is very verbose in it's definition. You could turn the entire function into a single boolean expression of the form:

return (start == '(' && end == ')')
    || (start == '{' && end == '}')
    || (start == '[' && end == ']');

An alternative would be to use a switch statement:

switch (start) {

case '(': return end == ')';
case '{': return end == '}';
case '[': return end == ']';

default:
    return false;
}

What you choose is a matter of preference. I would probably go for the switch approach, however, because to me it is clearer what is intended.

• areParanthesesBalanced is badly named. There is a typo in "parentheses" and parentheses refers specifically to () not {}, [] or <>. areBracketsBalanced would be more appropriate.

• One idea would be to pass const std::string& exp to the function rather than std::string. This prevents the program having to make a copy of the entire string in case you modify it.

• Your for loop for (int i = 0; i < exp.size(); i++) { ... } never actually makes use of the value of i. Instead you could use a range for like this for (char c : exp) which just gives you each character in turn.

• Your else is unnecessary because you've already returned execution from the function at that point.

• The line return s.empty() ? true : false; is bad because stack<>::empty() returns a boolean! Therefore, just use return s.empty();.

Overall this gives:

bool arePair(char start, char end)
{
    switch (start) {

    case '(': return end == ')';
    case '{': return end == '}';
    case '[': return end == ']';

    default:
        return false;
    }
}

bool areBracketsBalanced(const std::string& exp)
{
    std::stack<char>  s;
    for (char c : exp)
    {
        if (c == '(' || c == '{' || c == '[')
            s.push(c);
        else if (c == ')' || c == '}' || c == ']')
        {
            if (s.empty() || !arePair(s.top(), c))
                return false;
            s.pop();
        }
    }
    return s.empty();
}

But...

That covers a lot of smaller points but having constants defining your pairs of brackets in multiple places seems messy. Here's one possible solution but there might well be a nicer one I haven't thought of:

int isBracket(char c)
{
    switch (c) {

    case '(': return  1;
    case ')': return -1;

    case '{': return  2;
    case '}': return -2;

    case '[': return  3;
    case ']': return -3;

    default:
        return 0;
    }
}

bool areBracketsBalanced(const std::string& exp)
{
    std::stack<char>  s;
    for (char c : exp)
    {
        if (isBracket(c) > 0) // Opening brackets
            s.push(c);
        else if (isBracket(c) < 0) // Closing brackets
        {
            if (s.empty() || isBracket(s.top()) + isBracket(c))
                return false;
            s.pop();
        }
    }
    return s.empty();
}

Instead of printing fail...

You want to know the position of the failing bracket? Try changing the return type of areBracketsBalanced to int. You're already determining at what position it fails implicitly by returning false.