0

I was doing parenthesis checker using the stack. One of the if else statement containing a break; statement is causing segment fault.

I tried removing the break program runs fine but prints the wrong answer as that break is needed to print correct output. What is the cause of such a segment fault? the break doesn't access any memory unit.right?

Questions link

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

int main() {
//code
int n;
char c,comp;
cin>>n;
while(n--)
{
   stack<char>s;
   while(cin>>c)
   {
       if(c=='(' || c=='{'|| c=='[')
       s.push(c);
       else
       {
           comp=s.top();
           if(c==')' && comp=='(')
           s.pop();  
           else if(c==')' && comp!='(')
           {
               cout<<"not balanced"<<endl;
               break;  //this one, if i remove this no SIGSEGV
           }


           if(c=='}' && comp=='{')
            s.pop();
           else if(c=='}' && comp!='{')
           {
               cout<<"not balanced"<<endl;
               break;
           }


           if(c==']' && comp=='[')
           s.pop();
           else if(c==']' && comp!='[')
           {
               cout<<"not balanced"<<endl;
               break;
           }


       }

   }

       if(s.empty())
       cout<<"balanced"<<endl; 
}

return 0;
 }
Harshal Sharma
  • 98
  • 1
  • 9
  • 2
    Can you post the input string that causes the seg fault? Also, don't you need to pop the first element if it is balanced? – Blue Granny Aug 07 '19 at 05:27
  • @ArikRinberg Thanks for reminding I edited the code still segment fault. – Harshal Sharma Aug 07 '19 at 05:31
  • @HarshalSharma Your `if(s.empty())` statement is in the wrong place (it should be outside of the while loop). Please make sure you post the correct code, I don't have the confidence to work on this if I think I'm working on the wrong code. – john Aug 07 '19 at 05:34
  • Btw. your comparisons could be done a little bit more elegant: `if (c == ')') { if (comp == '(') s.pop(); else std::cout << "not balanced\n"; }` not to mention that you could use a `switch ()` for checking `c`. – Scheff's Cat Aug 07 '19 at 05:35
  • 1
    Unrelated: Looks like you've picked up a bit of [Cargo Cult](https://en.wikipedia.org/wiki/Cargo_cult_programming) behaviour. `#include ` includes freaking everything in the C++ Standard library, making `#include` pointless. That said, as with a lot of things Cargo Cult, [you do not want to `#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – user4581301 Aug 07 '19 at 05:36

2 Answers2

1

The crash is caused because you have no termination to your loop in the case of a balanced input. So you are going to end up popping something from an empty stack.

You should code this with a do while loop

do
{
    ...
    if (c == ')' && comp != '(')
        break;
    ...
}
while (!s.empty());
if (s.empty())
   cout << "balanced\n";
else
   cout << "not balanced\n";

Although even then you need to synchonise your input. Probably you should read the whole input (one string per line maybe?) and then work on the input string. In that case you could replace the do while loop with a for loop, e.g. for (char c : input)

john
  • 85,011
  • 4
  • 57
  • 81
1

So, first some background information on std::stack that will become relevant later:

The programming-by-contract style would be that having a non-empty stack is a precondition of calling pop, and that calling a method without meeting its preconditions has an undefined outcome.

Please note that while I couldn't find a source that said s.top() is bad when there are 0 elements in a stack, I'm going to assume it would also be bad for the same reason.

Why is that important? Well, undefined behavior can do anything, including segfault. Just keep that in the back of your head.

So, this code right here:

comp=s.top();

What happens if you ever run into a situation where s is empty, you have something else coming in from std::cin? For instance, what if you had an extra ) at the end of a parenthesis set like this:

()()) // <-- extra )

The ()s cancel out, but that ) is still there. So, when you try to reference the top, nothing is there. This is probably what is causing the crash.

You need a check around this line to make sure s isn't empty before you try to reference the top:

if(!s.empty()) {
    comp=s.top();
}

You should also probably do this around pop() as well:

if(c==')' && comp=='(' && !s.empty())
           s.pop();

Or something to that effect. Your logic may need some reworking, but hopefully that gives you the idea.