What exact is segmentation fault when using Stack and how to fix it?

Question

Im writing a program to check the score of parenthesis, Leetcode Question 856. However, with the algorithm I used, I'm encountering a "Segmentation Fault (core dumped)" error. I'm unsure as to how there is a segmentation fault when using stack and how could I fix it?

string s;
   cin >> s;
   int score = 0;
   stack<int> st;
   for (int i = 0; i < s.size(); i++){
     char a = s[i];
     if (a == '('){
       st.push(score);
       score = 0;
     }
     else{
       score = st.top() + max(score*2, 1);
       st.pop();
     }
   }
   cout << score;
}

what happens in your code when the first character is not a ( ? What is st.top() in that case? — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Oct 20, 2020 at 8:18
You must always check if the stack is empty or not before calling it's top or pop functions. — Some programmer dude
– Some programmer dude, Commented Oct 20, 2020 at 8:18
It is deferencing an invalid pointer, and it doesn't have anything to do with stacks particularly. — user207421
– user207421, Commented Oct 20, 2020 at 8:37

Ayan Bhunia · Accepted Answer · 2020-10-20 08:28:12Z

2

When the stack is empty and you try .top() or .pop() then it will give segmentation fault (error caused by accessing memory ).

string s;
   cin >> s;
   int score = 0;
   stack<int> st;
   for (int i = 0; i < s.size(); i++){
     char a = s[i];
     if (a == '('){
       st.push(score);
       score = 0;
     }
     else if(!st.empty()){
       score = st.top() + max(score*2, 1);
       st.pop();
     }
   }
   cout << score;
}

answered Oct 20, 2020 at 8:28

Ayan Bhunia

5593 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

463035818_is_not_an_ai Over a year ago

the segfault is not guaranteed to happen. Anything else could happen as well. Calling top on a empty stack is undefined behavior

Allan · Accepted Answer · 2020-10-20 08:34:06Z

0

A segmentation fault occurs when your program tries to access a memory location that is out of bounds of your array's size. To fix this you have to check whether you are accessing the array within it's size (ie) from 0 to sizeOfArray-1.

You can check this using if or while conditions. Well that depends on what you'r trying to achieve with your program.

answered Oct 20, 2020 at 8:34

Allan

1401 silver badge12 bronze badges

Comments

Emma Marcier · Accepted Answer · 2020-10-20 14:02:31Z

We can also solve this problem without using stack:

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <string>


static const struct Solution {
    using ValueType = std::uint_fast16_t;
    static const int scoreOfParentheses(
        const std::string S
    ) {
        ValueType scores = 0;
        ValueType level = 0;

        for (ValueType index = 0; index < std::size(S); ++index) {
            if (S[index] == '(') {
                ++level;
            } else {
                --level;
            }

            if (S[index] == ')' && S[index - 1] == '(') {
                scores += 1 << level;
            }
        }

        return scores;
    }
};

Collectives™ on Stack Overflow

What exact is segmentation fault when using Stack and how to fix it?

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related