28
\$\begingroup\$

I have refactored one of my old homework assignments (mainly to utilize std::stack and some C++11), and I'm still having trouble making it less repetitive.

It reads in a text file, character by character, and determines whether all of the opening and closing brackets ({}, (), and []) match properly. All other characters are ignored.

If a mismatch is found, an error message will be displayed to specify the specific one, and the program will terminate. Otherwise, at the end, a message will be displayed to indicate that they all match.

Here are the possible error types:

  • missing opening bracket:

    int main() { /*...*/ } ] // missing [
    
  • missing closing bracket:

    int main() { /*...*/     // missing }
    
  • opening bracket closed with the wrong closing bracket:

    int main() { /*...*/ ]   // should close with }
    

My questions:

  1. Is pushing each opening bracket onto a stack a practical way of doing this? I feel that my approach with it isn't too practical as it involves a lot of conditionals. When a closing bracket is found, there has to be some way to determine if they match properly.
  2. Would an std::map be beneficial in serving as a look-up table for associating the opening and closing brackets with each other? I feel that it may help with DRY here.
  3. Although it may seem easy to maintain all the error-checking in one function, should they still be split into separate functions? If so, should the messages be displayed in them or in main()?
  4. Does it make sense to return EXIT_SUCCESS if the program terminated from a matching error but not a file error? I'm not sure if I should return EXIT_FAILURE instead, even though it already does that if the file cannot be opened.

I don't mind following an entirely different procedure if this one isn't very practical. If you have something more complicated in mind, please share it. I want to approach this the right way.

#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <string>

typedef std::stack<char> Brackets;

void pushOpeningBrackets(Brackets& opening, char ch)
{
    if (ch == '{')
        opening.push('{');
    else if (ch == '(')
        opening.push('(');
    else if (ch == '[')
        opening.push('[');
}

bool errorsFound(Brackets& stack, char openingBracket, char closingBracket)
{
    // unmatched?
    if (stack.empty())
    {
        std::cerr << "Unmatched " << closingBracket;
        return true;
    }

    char topBracket = stack.top();
    stack.pop();

    // not a match?
    if (topBracket != openingBracket)
    {
        if (topBracket == '{')
            std::cerr << "Expected } but found " << closingBracket;
        else if (topBracket == '(')
            std::cerr << "Expected ) but found " << closingBracket;
        else if (topBracket == '[')
            std::cerr << "Expected ] but found " << closingBracket;

        return true;
    }

    return false;
}

int main()
{   
    std::cout << "Enter a text file name: ";
    std::string filename;
    std::getline(std::cin, filename);

    std::ifstream inFile(filename.c_str(), std::ios::in);

    if (!inFile) return EXIT_FAILURE;

    Brackets stack;
    std::string fileLine;

    while (inFile >> fileLine)
    {
        for (char ch : fileLine)
        {
            pushOpeningBrackets(stack, ch);

            if (ch == '}')
            {
                if (errorsFound(stack, '{', '}'))
                {
                    return EXIT_SUCCESS;
                }
            }
            else if (ch == ')')
            {
                if (errorsFound(stack, '(', ')'))
                {
                    return EXIT_SUCCESS;
                }
            }
            else if (ch == ']')
            {
                if (errorsFound(stack, '[', ']'))
                {
                    return EXIT_SUCCESS;
                }
            }
        }
    }

    // checks for missing bracket or full match
    if (!stack.empty())
    {
        char topBracket = stack.top();
        stack.pop();

        if ('{' == topBracket)
            std::cerr << "Missing }";
        else if ('(' == topBracket)
            std::cerr << "Missing )";
        else if ('[' == topBracket)
            std::cerr << "Missing ]";
    }
    else
        std::cout << "All brackets match!";
}
\$\endgroup\$
2
  • 5
    \$\begingroup\$ Since this is covered by "All other characters are ignored" I just wanted to comment that it's not unusual for languages that match brackets to use them in scenarios that don't require matches (i.e. quoted or in comments). That might be a good extension to consider. \$\endgroup\$ Jan 31, 2014 at 13:50
  • \$\begingroup\$ It'd be all but mandatory to handle string and char literals, at least. Note that your code almost certainly wouldn't be able to validate itself due to the literals. \$\endgroup\$
    – cHao
    Jan 31, 2014 at 20:15

6 Answers 6

14
\$\begingroup\$

Instead of ...

void pushOpeningBrackets(Brackets& opening, char ch)
{
    if (ch == '{')
        opening.push('{');
    else if (ch == '(')
        opening.push('(');
    else if (ch == '[')
        opening.push('[');
}

... use ...

void pushOpeningBrackets(Brackets& opening, char ch)
{
    switch (ch)
    {
        case '{':
        case '(':
        case '[':
            opening.push(ch);
            break;
    }
}

Or using a std:map:

std::map<char,char> charmap;
charmap['('] = ')';
...etc...

void pushOpeningBrackets(Brackets& opening, char ch)
{
    if (charmap.find(ch) != charmap.end())
        opening.push(ch);
}

Similarly, instead of ...

if (topBracket != openingBracket)
{
    if (topBracket == '{')
        std::cerr << "Expected } but found " << closingBracket;
    else if (topBracket == '(')
        std::cerr << "Expected ) but found " << closingBracket;
    else if (topBracket == '[')
        std::cerr << "Expected ] but found " << closingBracket;

    return true;
}

... you could ...

if (topBracket != openingBracket)
{
    char expected;
    switch (topBracket)
    {
        case '{': expected = '}'; break;
        case '(': expected = ')'; break;
        case '[': expected = ']'; break;
        default: ; // WHAT TO DO HERE?!
    }
    std::cerr << "Expected " << expected << " but found " << closingBracket;
    return true;
}

... or ...

if (topBracket != openingBracket)
{
    std::cerr << "Expected " << charmap[topBracket] << " but found " << closingBracket;
    return true;
}

In your existing code you have three different places where you define the pairs: e.g. here ...

if (errorsFound(stack, '{', '}'))

... and here ...

    if ('{' == topBracket)
        std::cerr << "Missing }";

... and here ...

    if (topBracket == '{')
        std::cerr << "Expected } but found " << closingBracket;

You can fix that by making a subroutine, char getCloseOf(char) { ... } and/or by defining it in data using a std::map or similar container.


You haven't implemented escaping strings and comments in the source; also C++ macros in the text being parsed could mess it up, e.g. #define FOO a(


Although it may seem easy to maintain all the error-checking in one function, should they still be split into separate functions? If so, should the messages be displayed in them or in main()?

I didn't like your subroutines much. For example pushOpeningBrackets is only called once and its implementation is short (and it's easier to understand it by reading its implementation than by reading its name). So you might as well have that code inline instead of as a subroutine, perhaps with a comment // push opening brackets.


Does it make sense to return EXIT_SUCCESS if the program terminated from a matching error but not a file error? I'm not sure if I should return EXIT_FAILURE instead, even though it already does that if the file cannot be opened.

You could document several return codes, e.g.:

  • 0: source parses - OK
  • 1: source parses - BADLY
  • -1: couldn't parse source - file error
  • -2: couldn't parse source - memory error
\$\endgroup\$
18
\$\begingroup\$

I'd rewrite it with three main changes:

  1. Keep main() minimal and improve the user interface.

    By the Single Responsibility Principle, it's a good idea to limit main() to just calling the primary function with the appropriate parameters. In this case, the functionality splits very cleanly.

    Being a Unix/Linux user, I would prefer to see tools that adhere to some Unixy conventions:

    • Take input from a file named on the command line, or from standard input if there is no command-line parameter.
    • On success, remain silent and return 0 (unless you add support for a --verbose flag, which I haven't bothered to implement).

    In the context of this program, I would consider failure to open the input file as an error condition to be reported to std::cerr, and a delimiter mismatch to be normal output to be reported to std::cout. (To answer your question 3, I've just taken the easy route and printed the errors as I encounter them. That may not be the most elegant method, but it saves me the trouble of encoding the mismatch into some kind of representation. When in doubt, keep it simple, I think.)

    To answer your question 4 about the exit status of the program: 0 means success; beyond that there is no universal convention.

  2. Use std::string::find_first_of().

    That saves you from the tedium of iterating character by character.

  3. Keep the expected closing delimiters in the stack.

    That seems to reduce redundancy in the code. This addresses your questions 1 and 2.

In addition, I've enhanced it to keep track of line and column numbers to help find the location of the mismatch. The diagnostics could be even more informative if you kept track of the location of every delimiter you push onto the stack.

#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <stack>
#include <string>

bool bracketsMatch(std::istream &in) {
    std::stack<char> expectedDelimiters;
    int lineNum = 0;
    std::string line;
    while (std::getline(in, line)) {
        lineNum++;
        size_t pos = 0; 
        while (std::string::npos != (pos = line.find_first_of("(){}[]", pos))) {
            int colNum = pos + 1;
            switch (line[pos]) {
              case '(': expectedDelimiters.push(')'); break;
              case '{': expectedDelimiters.push('}'); break;
              case '[': expectedDelimiters.push(']'); break;

              case ']':
              case '}':
              case ')':
                if (expectedDelimiters.empty()) {
                    std::cout << "Mismatched " << line[pos]
                              << " at line " << lineNum << ", col " << colNum
                              << std::endl;
                    return false;
                }
                if (line[pos] != expectedDelimiters.top()) {
                    std::cout << "Expected " << expectedDelimiters.top()
                              << ", found " << line[pos]
                              << " at line " << lineNum << ", col " << colNum
                              << std::endl;
                    return false;
                }
                expectedDelimiters.pop();
            }
            pos = colNum;
        }
    }
    // Should check for a possible input error here, but I didn't bother.
    if (!expectedDelimiters.empty()) {
        std::cout << "Expected " << expectedDelimiters.top()
                  << " at end of file" << std::endl;
        return false;
    }
    return true;
}

int main(int argc, const char *argv[]) {
    // The command-line parsing below is a bit sloppy (no validation,
    // help message, or option handling, for example).
    std::ifstream f;
    std::istream &in = (argc > 1) ? (f.open(argv[1]), f) : std::cin;
    if (!in) {
        std::cerr << argv[0] << ": " << argv[1] << ": "
                  << std::strerror(errno) << std::endl;
        return 2;   // A rather arbitrary error code
    }
    return bracketsMatch(in) ? EXIT_SUCCESS : EXIT_FAILURE;
}
\$\endgroup\$
16
\$\begingroup\$

The technique you are looking for is called "Data Driven" programming:

static char map[256]  = {0}; // init all the data to 0.

map['{']   = 1;
map['[']   = 1;
map['(']   = 1;
map['}']   = '{';
map[']']   = '[';
map[')']   = '(';

for(char ch: data) {
    char action = map[ch];
    if (action == 0) {
         /* do nothing */
    }
    else if (action == 1) {
         stack.push(ch);
    }
    else {
         if (stack.empty()) {
             // Error
         } else {
             char open = stack.top();
             stack.pop();
             if (open != action) {
                 // Error
             }
         }
     }
}
if (!stack.empty()) {
    // Error
}

Is pushing each opening bracket onto a stack a practical way of doing this?

Yes

I feel that my approach with it isn't too practical as it involves a lot of conditionals. When a closing bracket is found, there has to be some way to determine if they match properly.

Yes you are doing way too much programming that would involve change the code if your requirements changed a little bit. By using a data driven approach your code becomes more flexible and you can get your code to behave correctly with minor modifications to the data structure used to drive your code.

Would an std::map be beneficial in serving as a look-up table for associating the opening and closing brackets with each other? I feel that it may help with DRY here.

Overkill.
But a data structure is required.
I used an array of character to hold my decision state. If you were using unicode or some other larger character type then a vector. The size of your decision set is small so a linear scan would not cost much, either. \$O(ln(n)) + K1\$ is probably larger than \$O(n) + K2\$ for small values of n. Your n is 6.

Although it may seem easy to maintain all the error-checking in one function, should they still be split into separate functions?

I like the concept of a single log function. You can maintain a consistent way of formatting the message in a single location.

If so, should the messages be displayed in them or in main()?

You could move messages to a resource file for easier L10N and I18N.

Does it make sense to return EXIT_SUCCESS if the program terminated from a matching error but not a file error? I'm not sure if I should return EXIT_FAILURE instead, even though it already does that if the file cannot be opened.

Think about usage in a UNIX environment. Any error should return EXIT_FAILURE so that the command using forces the script to stop correctly (or not continue with invalid input).

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Mixing 0, 1, {, [, and ( as values feels a bit hackish, though it does work. \$\endgroup\$ Jan 31, 2014 at 9:22
  • 1
    \$\begingroup\$ By hackish you mean C like. Yes. If the problem was more complex then I would not do this. But no point getting complex on such a trivial problem. \$\endgroup\$ Jan 31, 2014 at 9:28
  • \$\begingroup\$ @LokiAstari: I've just looked at this again, and I pretty much understand it, except for if (action == 0). Is there any significance to it? It doesn't correspond to any of the pre-set error conditions, and it isn't triggered by adding a non-bracket character (which is what I've tried based on how it looks). \$\endgroup\$
    – Jamal
    Apr 26, 2014 at 1:26
  • \$\begingroup\$ @Jamal: if (action == 0) is the default action. If it is not an open or close (so the most common situation). It is mostly there as documentation to say "If we don't see any of the expected situations then do nothing" \$\endgroup\$ Apr 26, 2014 at 3:31
  • 1
    \$\begingroup\$ @AkshatAgarwal: That initializes all positions to 0; \$\endgroup\$ May 29, 2016 at 3:47
11
\$\begingroup\$

Let's answer the questions you have first:

  1. Using a stack is fine for this. You need to keep track of the ordering of the tokens you encounter, removing them in a LIFO manner - pretty much the definition of a stack.

  2. std::map is overkill for 3 tokens. I would store them, but in a (gasp!) plain stack allocated array. Because of the way std::map is implemented, the constant factors it has for a lookup are much much higher than for a plain array. Of course, dealing with large numbers, the fact that it is O(log n) instead of O(n) to search kicks in, however, that crossover point is likely to be (depending on a whole bunch of factors) somewhere in the thousands. Not that speed matters much here (it doesn't), but searching this is arguably simpler anyway.

  3. I think having the error functionality in one function is perfectly fine. As much as splitting things into separate functions is good, in something this simple, I find there is little point. Actually outputting the error is again fine within the function - it has all the information it needs at this point. If you handled this in main instead, you'd have to figure out a return value that said either "here's what I was expecting, here's what I found, there's an error" or "everything is ok". That's almost certainly going to be uglier than what you've got here already.

  4. Personally, I think it should be returning EXIT_SUCESS if everything is good (everything matches properly), and EXIT_FAILURE otherwise. Think of using this in some kind of pipeline where the file has to undergo a bunch of checks, one after the other - you'd then want it to have no errors before continuing. Best way to signal everything is good? Using EXIT_SUCCESS.

Ok, a few other suggestions:

Keep a list of tokens (as a simple array):

constexpr char tokenList[] = {'{', '(', '['};

You can then change pushOpeningBrackets to:

void pushOpeningBrackets(Brackets& opening, char ch)
{
    for(char tok : tokenList)
    {
        if(ch == tok) 
            opening.push(tok);
    }
}

This has the added benefit that if you want to add another token, you only have to add it to your tokenList, instead of having to add another else if statement.

One place you could potentially use a map (for simplicity) is in errorsFound, where you want the associated closing brace with an opening brace:

const std::map<char, char> closing = {{'{', '}'}, {'(', ')'}, {'[', ']'}};

bool errorsFound(Brackets& stack, char openingBracket, char closingBracket)
{
    if(stack.empty()) 
    {
        std::cout << "Unmatched " << closingBracket;
        return true;
    }

    char topBracket = stack.top();
    stack.pop();

    if(topBracket != openingBracket) {
        auto expectedClosing = closing.find(topBracket);
        std::cout << "Expected " << expectedClosing->second << " but found "
                  << closingBracket;
        return true;
    }

    return false;
} 

This could also be used to simplify your check at the bottom of main in a similar way.

\$\endgroup\$
11
\$\begingroup\$

Your typedef

typedef std::stack<char> Brackets;

… seems awkward to me.

Without the typedef, your stack would probably have been declared as

std::stack<char> brackets;

However, with the typedef, that ends up being Brackets stack, which feels unfortunately backwards, since I expect stack to be a type rather than a variable name.

\$\endgroup\$
1
  • \$\begingroup\$ Yeah, I was a bit hasty with the naming. I'll go back and fix some of them. \$\endgroup\$
    – Jamal
    Jan 31, 2014 at 8:35
2
\$\begingroup\$

First, to make it really useful add the original line that you parsed into the mix

typedef std::pair<std::string, size_t> lineNumber
std::vector<lineNumber> readFile(const std::string &fileName) {
    std::ifstream fileStream(fileName.c_str(), std::ios::in);
    if (fileStream.fail()) {
        throw std::runtime_error("Cannot open file " + fileName + "\n");
    }

    std::vector<lineNumber> lines;
    std::string temp;
    while (getline(fileStream, temp)) {
        lines.push_back(std::make_pair(temp, lines.size()+1));
    }

    if (lines.empty()) {
        throw std::runtime_error("Empty file " + fileName + "\n");
    }
    fileStream.close();

    return lines;
}

That way the user doesnt have to manually scan a possibly huge document by hand.


I would say, that you should put the error checking into one single function. Also i would strongly recommend to keep track of the position of the error. Nothing makes more fun as manually parsing a very long line for a tiny mistake, similar to parsing a huge file for a certain line.

void checkBrackets(const std::vector<lineNumber> &lines) {
    std::map<char, char> bracketPairs= {std::make_pair(')', '('),
                                        std::make_pair(']', '['),
                                        std::make_pair('}', '{')};
    std::stack<std::pair<char, size_t>> brackets;
    for (lineNumber line : lines) {
        for (auto it = line.first.begin(); it != line.first.end(); ++it) {
            switch (*it) {
            case '(':
            case '[':
            case '{':
                brackets.push(std::make_pair(*it, std::distance(line.first.begin(), it)));
                break;
            case ')':
            case ']':
            case '}':
                if (brackets.empty()) {
                    throw bracketException(MISSING_OPENING_BRACKET, line, 
                                           std::distance(line.first.begin(), it));
                } else if (brackets.top().first != bracketPairs[*it]) {
                    throw bracketException(MISSING_CLOSING_BRACKET, line,
                                             brackets.top().second);
                }
                brackets.pop();
                break;
            default:
                continue;
            }
        }
        if (!brackets.empty()) {
            throw bracketException(MISSING_CLOSING_BRACKET, line,
                                     brackets.top().second);
        }
    }
}

Now you can add a custom exception to tell your user what is wrong with the code and standardize your error warnings. This might obviously be an overkill, but i used it for a parser I wrote and naturally the number of different errors increases.

enum bracketError {
    MISSING_CLOSING_BRACKET,
    MISSING_OPENING_BRACKET
}
class bracketException : public std::exception {
private:
    std::string m_msg;
public:
    explicit bracketException(const bracketError errorType,
                              const lineNumber &line,
                              const size_t pos)
    {
        switch (errorType) {
        case MISSING_CLOSING_BRACKET:
            m_msg = std::string("Cannot find closing bracket");
            break;
        case MISSING_OPENING_BRACKET:
            m_msg = std::string("Cannot find opening bracket");
            break;
        }
        m_msg += " in line " + std::to_string(line.second) + ":\n";
        m_msg += line.first + "\n";
        m_msg += std::string(pos, ' ') + "^\n";
    }

    virtual const char* what() const throw()
    {
        return m_msg.c_str();
    }
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.