A string may use more than one type of delimiter to bracket information into \"b

Question

A string may use more than one type of delimiter to bracket information into "blocks." For example, A string may use braces { }, parentheses (), and brackets [ ] as delimiters. A string is properly delimited if each right delimiter is matched with a preceding left delimiter of the same type in such a way that either the resulting blocks of information are disjoint, or one of them is completely nested within the other. Write a program that uses a single stack to check whether a string containing braces, parentheses, and brackets is properly delimited.

Answer in c++ please!

Explanation / Answer

The fallowimg Code will help you in a single Stack to check whether a string containing braces, parentheses, and brackets is properly delimited.

Code::

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

}

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:

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.

Use std::string::find_first_of().

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

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.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.