Why am I unable to add elements to this stack?

Question

The following code is giving me a runtime error for some reason I'm unable to figure out. We are iterating over the string a and whenever we encounter a char = (, we push 1 into the stack and whenever we encounter ) we remove an element from the stack.

#include <bits/stdc++.h>
using namespace std;
int main() {
    string a= ")()())";
    stack<int> st;

    for(int z = 0; z < a.length(); z++){
        if(a[z] == '(') st.push(1);
        else st.pop();   
                                                              
        }
    
}

Can someone please explain why is it giving me a runtime error?

It is because you are removing elements from the stack before inserting. you should also check for the empty-stack condition. — Aarsh, May 24 '22 at 04:25
You are popping from the stack unconditionally, check if there's something to pop at all first. — πάντα ῥεῖ, May 24 '22 at 04:25

wohlstad · Answer 1 · 2023-03-01T12:34:05.560

2

At the first iteration (z==0) you will encounter a ')' character.
Since it is != '(', you will atempt to pop a stack which is still empty.
This is the cause for your runtime error.

Side notes:

edited Mar 01 '23 at 12:34

answered May 24 '22 at 04:27

wohlstad

12,661
10
26
39

score 1 · Answer 2 · answered May 24 '22 at 04:31

You are popping from the stack even if the stack is empty.

Your code should be something like this.

#include <bits/stdc++.h>
using namespace std;
int main() {
    string a= ")()())";
    stack<int> st;

    for(int z = 0; z < a.length(); z++){
        if(a[z] == '('){ 
            st.push(1);
        }
        else if(!st.empty()){
            st.pop();
        }
        else{ 
            cout<<"The Stack is empty. Nothing can be poped out"<<endl;
            break;
        }
                                                              
    }
    
}

score 0 · Answer 3 · answered May 24 '22 at 05:08

You need to check the stack size before popping. Let's walk through your input -

string a= ")()())";

When z is 0 in the first iteration, a[z] = ')', so it will go the else condition of your below code -

#include <bits/stdc++.h>
using namespace std;
int main() {
    string a= ")()())";
    stack<int> st;

    for(int z = 0; z < a.length(); z++){
        if(a[z] == '(') st.push(1);
        else st.pop(); // The root cause of the issue is here
                                                              
        }
    
}

That means it will try to pop the top element of your stack, but your stack is empty since you are yet to push anything on it. Popping from an empty stack is undefined behavior. You can fix the error by checking the size of the stack before popping from it like the below -

#include <bits/stdc++.h>
using namespace std;
int main() {
    string a= ")()())";
    stack<int> st;

    for(int z = 0; z < a.length(); z++){
        if(a[z] == '(') st.push(1);
        else if (!st.empty()) st.pop();   
                                                              
        }
}

I am not sure what your program intends to do, but this will definitely fix the undefined behavior.

Why am I unable to add elements to this stack?

3 Answers3