CODEWITHSUNDEEP
c++stack
Rahul Patil
Rahul Patil

Reputation: 1

I have solved Balanced Brackets on Hackerrank and i encountered this error... can someone help me understand this?

https://www.hackerrank.com/challenges/balanced-brackets/problem This is the question link

and here is my code :

 #include <bits/stdc++.h>

using namespace std;

// Complete the isBalanced function below.
string isBalanced(string s) {
    stack<char> st;
    for(int i=0;i<(int)s.size();i++)
    {
        switch(s[i])
        {
            case  '(' :
            case  '{' :
            case  '[' :
                st.push(s[i]);
                break;
            case ')' :
                **if(st.top()!='(' || st.empty())**
                {
                    return "NO";
                }
                st.pop();
                break;
            case '}' :
                **if(st.top()!='{' || st.empty())**
                {
                    return "NO";
                }
                st.pop();
                break;
            case ']' :
                **if(st.top()!='[' || st.empty())**
                {
                    return "NO";
                }
                st.pop();
                break;
        }
    }
    return st.empty() ? "YES" : "NO";
}
int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int t;
    cin >> t;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int t_itr = 0; t_itr < t; t_itr++) {
        string s;
        getline(cin, s);

        string result = isBalanced(s);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}

This code is not working. So I googled to find out the correct code.
See the correct code here:

#include <bits/stdc++.h>

using namespace std;

// Complete the isBalanced function below.
string isBalanced(string s) {
    stack<char> st;
    for(int i=0;i<(int)s.size();i++)
    {
        switch(s[i])
        {
            case  '(' :
            case  '{' :
            case  '[' :
                st.push(s[i]);
                break;
            case ')' :
                if(st.empty() || st.top()!='(')
                {
                    return "NO";
                }
                st.pop();
                break;
            case '}' :
                if(st.empty() || st.top()!='{')
                {
                    return "NO";
                }
                st.pop();
                break;
            case ']' :
                if(st.empty() || st.top()!='[')
                {
                    return "NO";
                }
                st.pop();
                break;
        }
    }
    return st.empty() ? "YES" : "NO";
}
int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int t;
    cin >> t;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int t_itr = 0; t_itr < t; t_itr++) {
        string s;
        getline(cin, s);

        string result = isBalanced(s);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}

This is the correct code and see the only difference is the condition in the if bracket.
I am not understanding what I have done wrong?

Upvotes: 0

Views: 674

Answers (3)

Shivam Nad
Shivam Nad

Reputation: 1

string isBalanced(string s) {
      std::vector<char> stack;
      bool isBalanced = true;

    for (char ch : s) {
        switch (ch) {
            case '{':
            case '(':
            case '[':
                stack.push_back(ch);
                break;
            case '}':
                if (!stack.empty() && stack.back() == '{')
                    stack.pop_back();
                else
                    isBalanced = false;
                break;
            case ')':
                if (!stack.empty() && stack.back() == '(')
                    stack.pop_back();
                else
                    isBalanced = false;
                break;
            case ']':
                if (!stack.empty() && stack.back() == '[')
                    stack.pop_back();
                else
                    isBalanced = false;
                break;
        }
    }

    if (isBalanced && !stack.empty())
        isBalanced = false;

    return isBalanced ? "YES" : "NO";
}

Upvotes: 0

Lionell Loh Jian An
Lionell Loh Jian An

Reputation: 138

if(st.top()!='{' || st.empty())

The compiler compiles this line down to two separate checks. As these two separate checks are probably two (or even more) instructions, one has to take precedence over the other.

In this case, st.top() != '{' is evaluated before st.empty().

Upvotes: 0

Lukas-T
Lukas-T

Reputation: 11340

The difference between

if(st.top()!='{' || st.empty())

and

if(st.empty() || st.top()!='{')

is the order of evaluation and short circuiting.

The first line will evaluate st.top()!='{' first. If st is empty at this point you get undefined behaviour that might manifest as crash.

The second line will first evaluate st.empty() and only if this is false it will go on to evaluate st.top()!='{'.

That's called short-circuit evaluation or just short-circuiting.

Upvotes: 1

Related Questions