(19) Matching Brackets - C

Back to General discussions forum

magickarp     2017-05-08 22:35:14
    I can't get it: when i push test input - it is wrong, when i push it one by one - everything is correct
    Is there something wrong with my output or what?

#include<iostream> #include<vector> using namespace std;

int main(void) { int cases; cin >> cases;

for (int i = 0; i < cases; i++)
{
    vector<char> open;
    vector<char> close;
    char op, cl;
    bool problem = false;
    char line[80];
    cin.getline(line, 80);
    int t = 0;
    for (int i = 0; line[i] != '\0' && !problem; i++)
    {

        char symb = line[i];
        switch (symb)
        {

        case('('): case('['): case('{'): case('<'):
            open.push_back(symb);
            break;

        case(')'): case(']'): case('}'): case('>'):
            close.push_back(symb);
            op = open.back() - t;
            cl = close.front() + t;
            if (open.empty()) problem = true;

            else if ((op == '(') && (cl != ')') || (op == '[') && (cl != ']') ||
                (op == '{' && cl != '}') || (op == '<' && cl != '>')) problem = true;

            else t++;

            break;

        default:
            break;
        }
    }
    cout << !problem << " ";
}
return 0;

}

Quandray     2017-05-09 07:25:47
User avatar

Hi,

Here's one thing that needs fixing.

After cin>>cases, the first cin.getline will not read the second line, it will read the end of the first line. Suggest you add a cin.getline, immediately after cin>>cases.

Your code still gives the wrong answer for the third example test case.

magickarp     2017-05-10 12:06:40

Thank you for your suggestion. I've added some changes and now it works well (in Ideone, for example) but it doesn't work in CodeAbbey compiler.

    GDB trace:Reading symbols from solution...done.[New LWP 23176]Core was generated by `solution'.
    Program terminated with signal SIGSEGV, Segmentation fault.#0  main () at solution.cc:3737                  
    op = open.back();#0  main () at solution.cc:37

Here is new code

#include <iostream> 
#include <vector>

using namespace std;

int main(void)
{
int cases;
cin >> cases;
cin.clear();
cin.ignore();
for (int i = 0; i < cases; i++)
{
    vector<char> open;
    vector<char> close;
    char op, cl;
    bool correct = true;
    char line[128];
    cin.getline(line, 128);
    int c = 0;

    do
    {
        char symb;
        symb = line[c];
        if (symb == '\0') break;
        c++;

        switch (symb)
        {
        case('('): case('['): case('{'): case('<'):
            open.push_back(symb);
            break;

        case(')'): case(']'): case('}'): case('>'):
            close.push_back(symb);
            op = open.back();
            cl = close.back();
            if (open.empty()) correct = false;
            else if ((op == '(') && (cl != ')') || (op == '[') && (cl != ']') ||
                (op == '{' && cl != '}') || (op == '<' && cl != '>')) correct = false;
            else open.pop_back(), close.pop_back();
            break;

        default:
            break;
        }
    } while (correct);

    if(!open.empty() && close.empty()) correct = false;
    std::cout << correct << " ";
}
return 0;
}
magickarp     2017-05-10 12:08:19

Is it because of cin.funtions?

magickarp     2017-05-10 13:21:52

Oh, finaly solved it. There appear problem in case when "open" vector was empty so i've changed it:

    //OLD
    close.push_back(symb);
        op = open.back();
        cl = close.back();
        if (open.empty()) correct = false;
        else if ((op == '(') && (cl != ')') || (op == '[') && (cl != ']') ||
            (op == '{' && cl != '}') || (op == '<' && cl != '>')) correct = false;
        else open.pop_back(), close.pop_back();
        break;


    //NEW   
    close.push_back(symb);
            if (open.empty()) correct = false;
            else
            {
                op = open.back();
                cl = close.back();
            }

            if ((op == '(') && (cl != ')') || (op == '[') && (cl != ']') ||
                (op == '{' && cl != '}') || (op == '<' && cl != '>')) correct = false;
            else open.pop_back(), close.pop_back();
            break;  

Thank you

ahsan_gh     2020-08-12 06:28:28

how did you ignore the characters between the brackets?

Rodion (admin)     2020-08-12 09:08:16
User avatar

There are many ways usually. In C you can use ctype or anything else. You can, for example, copy the line skipping any character which is not one of the allowed types of brackets. And then work on this new string.

ahsan_gh     2020-08-16 23:13:02

tried to top and pop from a stack for each test case, and store the true / false boolen in a vector<bool> getting the following error: EXC_BAD_ACCESS (code=EXC_I386_GPFLT)

is it a memory leak?

Rodion (admin)     2020-08-17 06:00:17
User avatar

I think not "memory leak" but rather "memory violation". You are working with memory which you either haven't claimed (allocated) or already released (freed), or by constructing wrong pointer at all.

ahsan_gh     2020-08-18 03:03:57

memory violation is correct sir and a bunch of edge cases, figured it out though where can i show you my code

Please login and solve 5 problems to be able to post at forum