CODEWITHSUNDEEP
c++c++11
TheKingSid
TheKingSid

Reputation: 39

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

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;
}

Upvotes: 1

Views: 1723

Answers (3)

Emma
Emma

Reputation: 27723

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;
    }
};

Upvotes: 0

Allan
Allan

Reputation: 140

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.

Upvotes: 0

Ayan Bhunia
Ayan Bhunia

Reputation: 549

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;
}

Upvotes: 2

Related Questions