Parenthesis checker is working for individual test case perfectly but for all test case together it is giving segmentation fault?

Question

I have written code for parenthesis checker using stack in c++ ,it is working perfectly fine for all test cases individually but when I perform test case simultaneously in one go then it is giving error of segmentation fault.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;

    while (t--) {
        string str;
        cin >> str;

        stack<char> box;

        int len = str.size();
        box.push(str[0]);

        for (int i = 1; i < len; i++) {
            char temp = str[i];
            char tp = box.top();

            if (((tp == '{' && temp == '}') || (tp == '[' && temp == ']') || (tp == '(' && temp == ')')) && (!box.empty())) {
                box.pop();
            }
            else {
                box.push(temp);
            }
        }

        if (box.empty() == true)
            cout << "balanced" << endl;
        else
            cout << "not balanced" << endl;
    }

    return 0;
}

Answer 1

Basically your approach is very good. This is also the method used by parsers to match opening and closing tokens: A stack.

There are some improvements that should be done. You are shifting everything on the stack. You should just put the braces on the stack. Then you can do exact matches. Then you should put your braces in some container, e.g. a std::vector or a std::map or a std::string as I do in the following example.

For your seg fault. This hapens, when you try to access elements from an empty stack. One solution for that could be, to take advantage from C++' so called boolean short cut evaluation. Meaning, the evaluation of a boolean expression (for example, in an if statement) stops, as soon as the result is known.

So if you write (!braceStack.empty() && (braceStack.top() == openingBraces[position])) and the stack would be empty, then the stack.top function would not be invoked. Nothing would happen. You would be on the save side.

In the real world, you would NEVER do that, because then you would rely on side effects. You would simply put an additional if.

In your code you are calling top before checking, if the stack is empty. This results in undefined behaviour (UB).

In addition to the improvments made before, I also added comments, better variable names, usage of the containers algorithms and so on.

Please see.

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

// We define 2 strings with braces
// With that, searching is easier
const std::string openingBraces("([{<");

// Closing brace position must match to openeing brace position
const std::string closingBraces(")]}>");

int main()
{
    // Get number of test rund from user
    int numberOfTestRuns{ 0 };
    std::cin >> numberOfTestRuns;

    // Perform as many as tests, as user wants
    while (numberOfTestRuns--) {

        // Get string to analyze from user
        std::string stringToAnalyze;
        std::cin >> stringToAnalyze;

        // Define a stack for braces
        std::stack<char> braceStack{};

        // Check all charcters in test string. From beginning to end
        for (char currentCharToCheck : stringToAnalyze) {

            // If there is an opening brace
            if(openingBraces.find(currentCharToCheck) != std::string::npos) {

                // Then put this on the stack. Do not push other element on the stack
                braceStack.push(currentCharToCheck);
            }
            else {

                // It was no opening brace
                // Now we check, if it was a closing brace
                if (size_t position = closingBraces.find(currentCharToCheck); position != std::string::npos) {

                    // CLosing brace found. First check, if there are elements on the stack
                    // And then check, if we have a fmatching brace on the stack top
                    if (!braceStack.empty() && (braceStack.top() == openingBraces[position])) {
                        // In this case we remove the stacke top. ELse not. Will lead to no match
                        braceStack.pop();
                    }
                }
                // Else Nothing: It was any other character, no brace
            }
        }

        // If the stack is empty, then we could find a match for everything
        if (braceStack.empty() == true)
            std::cout << "balanced" << '\n';
        else
            std::cout << "not balanced" << '\n';
    }
    return 0;
}