AddressSanitizer:DEADLYSIGNAL error when trying to run code using stack for valid parenthesis problem set

Question

I was trying this problem called valid parenthesis on leetcode.com when an error popped up saying this:

AddressSanitizer:DEADLYSIGNAL
=================================================================
==30==ERROR: AddressSanitizer: SEGV on unknown address (pc 0x0000003783d6 bp 0x7ffe68231e10 sp 0x7ffe68231ca0 T0)
==30==The signal is caused by a READ memory access.
==30==Hint: this fault was caused by a dereference of a high value address (see register values below).  Dissassemble the provided pc to learn which register was used.
    #3 0x7f427121b0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
AddressSanitizer can not provide additional info.
==30==ABORTING

This is the code which generated the error

#include <stack>

using namespace std;

class Solution {
public:
    bool isValid(string str) {
        stack<char> s;
        bool val=true;
        for(int i=0;i<str.length();i++){
            if(str[i]=='(') s.push(')');
            else if(str[i]=='{') s.push('}');
            else if(str[i]=='[') s.push(']');
            else if(str[i]==')'||str[i]=='}'||str[i]==']'){
                if(str[i]==s.top()) s.pop();
                else if(str[i]!=s.top()) {
                    val=false;
                    break;
                }
            }
        }
        if(s.empty()) val=true;
        else if(!s.empty()) val=false;
        
        return val;
    }
};

I don't understand this error and would be really helpful if someone gives a solution for this

Answer 1

Consider what would happen on this simple input ).

Your program would call s.top() on an empty stack. That's an illegal operation and would explain why your program crashes.

You should perhaps rewrite your code like this so you check whether the stack is empty before you call s.top()

if (!s.empty() && str[i] == s.top())
{
    s.pop();
}
else
{
    val=false;
    break;
}

although I haven't tested this.

Answer 2

This is Runtime error occurred because of TLE ..

Here because of this lines of code:

else if(str[i]==')'||str[i]=='}'||str[i]==']'){
                if(str[i]==s.top()) s.pop();
                else if(str[i]!=s.top()) {
                    val=false;
                    break;
                }
            }

what you are doing is randomly popping the top element before that you should check if the specified type of parenthesis is a available in the stack

for example , if I encountered ')' then I should check if the top element is '(' or not , it is an edge case

Answer 3

This could also occur when a recursion function runs indefinitely or referring to an element by the index that is out of bounds.