-2

Question link

In this question firstly user will give the number of test cases, for each of the test cases users enter a string like [{()}]. This code if s[i] value equal to any left bracket like '(', '[', '{' then i added it's right bracket into ans string otherwise we have to compare last added character in ans with current s[i] character.

#include <bits/stdc++.h> 
using namespace std;
string isBalanced(string s) {
    string ans;
    int j=-1;
for(int i=0; i<s.length(); i++)
{

    if(s[i]=='(' || s[i]=='[' || s[i]=='{')
    {
        if(s[i]=='(')
        ans.push_back((char)(s[i]+1));
        else ans.push_back((char)(s[i]+2));
        j++;
    } 
   else if(s[j]==s[i] && i>0){
        ans.pop_back();
        j--;
    } 

}
if(ans.empty()) return "YES";
else return "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;
}
Sunil Panchal
  • 13
  • 4

1 Answers1

1

Edit. In your code, I found three issues:

You compare s[i] with s[j], while you should made the comparaison with ans[j]

Before using index j, you should first check it is positive.

As soon as the comparaison fails, you should return "NO".

This is your code, corrected:

string isBalanced_OP(string s) {
    string ans;
    int j = -1;
    for (int i = 0; i < s.length(); i++) {
        if (s[i]=='(' || s[i]=='[' || s[i]=='{') {
            if (s[i]=='(') ans.push_back ((char)(s[i]+1));
            else ans.push_back ((char)(s[i]+2));
            j++;
        } 
        else if (j < 0) {
           return "NO";
        } else if (ans[j]==s[i]){
            ans.pop_back();
            j--;
        } else {
            return "NO";
        }
    }
    if(ans.empty()) return "YES";
    else return "NO";
}

Another important point is that your algorithm seems too complex for this problem.

If you don't have other characters than brackets, you only need to compare current first and current last characters, and no need for string ans. You can return "NO" as soon as you get a mismatch. 

string isBalanced(string s) {
    int n = s.size();
    if (n%2) return "NO";
    int i = 0;
    int j = n-1;
    while (i < j) {
        bool check;
        check = (s[i] == '(' && s[j] == ')');
        check = check || (s[i] == '[' && s[j] == ']');
        check = check || (s[i] == '{' && s[j] == '}');
        if (!check) return "NO";
        ++i;
        --j;
    }
    return "YES";
}

Edit: it appears after my first post that a sequence like ()[]{} is well balanced, which is not so clear from the question on the online site, and not mentioned originally in the question here. Therefore, I now provide this second program, based on a stack. The idea is to stack opening brackets, and to check each close bracket with the last character entered in the stack. It appears finally that this code is rather similar to yours, after correction of your code. 

string isBalanced2(string s) {
    int n = s.size();
    if (n%2) return "NO";
    std::stack<char> st;

    for (int i = 0; i < n; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            st.push (s[i]);
            continue;
        }
        if (st.empty()) return "NO";
        char mem = st.top();
        st.pop();
        bool check;
        check = (mem == '(' && s[i] == ')');
        check = check || (mem == '[' && s[i] == ']');
        check = check || (mem == '{' && s[i] == '}');
        if (!check) return "NO";
    }
    if (st.empty()) return "YES";
    else return "NO";
}
Damien
  • 4,809
  • 4
  • 15
  • 20
  • From my understanding `()[]{}` is balanced (whereas you reject it). – Jarod42 Jan 29 '20 at 15:06
  • @Jarod42 For me, your example corresponds to a set of balanced bracket sequences, not a single one. Ambiguity indeed. Before posting, I had a look on Hackerrank site, mentioned by OP. They provide different examples, no one corresponds to your example. However, the text on the site is not so clear. – Damien Jan 29 '20 at 15:14
  • @Jarod42 That being said, if you were right, the problem will be solved simply by using a stack. Maybe let us wait OP's comments about their attempt to use this code – Damien Jan 29 '20 at 15:17
  • ASC code for '(' 40 , ')' 41 , '[' 91 , ']' 93 '{' 123 and '}' 125 – Sunil Panchal Jan 29 '20 at 15:36
  • @SunilPanchal OK, I understand now. The problem is that this kind of tricks make the code not so clear, and not always portable. Did you check this code on the site? – Damien Jan 29 '20 at 15:38
  • @Jarod42 I want to know why this s[j]==s[i] condition is not working?? – Sunil Panchal Jan 29 '20 at 15:48
  • @Damien Above code is not working. I don't want code. I want to know why this condition is not working s[j]==s[i] ?? – Sunil Panchal Jan 29 '20 at 15:54
  • @SunilPanchal You initialize `j = -1`. It cannot be correct. – Damien Jan 29 '20 at 16:02
  • @Damien I have explained the code above ones more check it ?? – Sunil Panchal Jan 29 '20 at 16:09
  • @Damien it's correct to let see if user give this input () left bracket will come then its value will increase then it is j=0 and i=1 after our second condition will work s[i] == s[j] and we get output YES but it's not working – Sunil Panchal Jan 29 '20 at 16:16
  • @SunilPanchal I edited again my answer. I can see now what is the problem in your code, look at the beginning of my answer – Damien Jan 29 '20 at 16:34
  • @Damien I have written there s[j] I have to write ans[j]. It is my mistake.Sorry for that. Thank You, sir, for helping me. – Sunil Panchal Jan 29 '20 at 16:45