# Validating opening and closing bracket pairs

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!";
}

-
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. –  Michael Urman Jan 31 at 13:50
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. –  cHao Jan 31 at 20:15

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);
}


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
-

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

-
Mixing 0, 1, {, [, and ( as values feels a bit hackish, though it does work. –  200_success Jan 31 at 9:22
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. –  Loki Astari Jan 31 at 9:28

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;
}

-

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.

-

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.

-
Yeah, I was a bit hasty with the naming. I'll go back and fix some of them. –  Jamal Jan 31 at 8:35