vector pop_back causing heap-buffer-overflow error

user_7434294 0
Viewed 207

I'm trying to make a function to validate the parenthesis problem, this function runs well on my machine, but it causing "heap-buffer-overflow" error on leetcode machine when I call vector.pop_back(). Here's the code:

int isValid(string s){
    vector<char> st;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '(') st.push_back(s[i]);
        else{
            if(st.back() == '(') st.pop_back(); //this line triggered the error
            else return 0;
                
        }
    }
    return (st.size() == 0);
}

I already solved this by changing the vector into string, but I'm still wondering how can this happened, any explanation anyone?

vector data-structures stack c++
2 Answers

Calling std::vector::back() on an empty vector is undefined behavior.

Calling back on an empty container causes undefined behavior.

(The same holds for std::vector::pop(), but at that point your program is already in an invalid state if the container was empty).

Therefore, the expression st.back() == '(' on your code might lead to an invalid program state because the container st is not sure being not empty.

Your code path needs to check the emptiness of the container before calling std::vector::back(); something like:

if (!st.empty() && st.back() == '(')
  st.pop_back();
else
  return 0;

Bonus Note: the code above exploits logical operators short circuit evaluation. It means that the second operand (i.e., the expression st.back()) will not be invoked if the container is empty.

user_60401810

maybe because you didn't assign any element in the vector before checking on the if condition. Try putting :

if(st.size()!=0)
{
 if(st.back() == '(') st.pop_back(); 
            else return 0;
}

on that piece of code

user_136134540
Related