1

This is my code for checking if a string of grouping characters is properly balanced. It works fine on my local machine, but the online judge gives me a run-time error.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool balanced(string exp)
{
    stack<char> st;
    int i;
    for(i=0;i<exp.length();i++)
    {
            if(exp[i]== '{' || exp[i]=='[' || exp[i]== '(') st.push(exp[i]);
            else if(exp[i]=='}'){
                if(st.top() == '{' && !st.empty()) st.pop();
                else return false;
            }
            else if(exp[i]==')'){
                if(st.top() == '(' && !st.empty()) st.pop();
                else return false;
            }
            else if(exp[i]==']'){
                if(st.top()=='['  && !st.empty()) st.pop();
                else return false;
            }
    }
    if(st.empty())return true;
    else return false;
}

int main() {
    string exp;int n;
    cin >> n;
    cin.ignore();
    while(n--)
    {
        getline(cin,exp);
        bool balance = balanced(exp);
        if(balance == true)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}
200_success
  • 7,286
  • 1
  • 43
  • 74
Pradeep
  • 1,193
  • 6
  • 27
  • 44
  • "Works on my machine" when the intent is to make it "work on the online judge" sounds very very much like "my code isn't working as intended"... – Mathieu Guindon Dec 18 '15 at 15:33
  • @Mat'sMug Since it's not **compilation error** and not **wrong answer** I expect my answer to be correct.In fact tested it against 20 test cases and works correctly. – Pradeep Dec 18 '15 at 15:35
  • @Pradeep Does it compile *and* run correctly on your machine, and just not the online tester? – Ethan Bierlein Dec 18 '15 at 15:37
  • @EthanBierlein Yes.It Does.That's what made me curious. – Pradeep Dec 18 '15 at 15:37

2 Answers2

5
if(st.top() == '{' && !st.empty())

You should check for stack emptiness before taking the top.

if(!st.empty() && st.top() == '{')
200_success
  • 7,286
  • 1
  • 43
  • 74
  • Beautiful.Got Accepted.Why does the order matter? – Pradeep Dec 18 '15 at 16:05
  • 1
    @Pradeep if stack is empty when you are trying to get top value, undefined behavior happens. And it is a bad news. Literally anything could happen, from returning seemingly random values, to crash (in debug implementation which checks bounds) – Revolver_Ocelot Dec 18 '15 at 16:13
  • @Revolver_Ocelot Got It.Something similar happened when I tried to access stack top just after initialization. – Pradeep Dec 18 '15 at 16:14
2

Spacing

I have a few issues with your spacing and brace usage. First, your logic in your loop is WAY too indented. A single indent is fine. Second, do not write logic on the same line as if unless it's a trivial condition and has no else - and never write logic on the same line as else. It's impossible to read. Strongly prefer writing braces throughout. Also add a space after if

Here's balanced rewritten with better spacing:

bool balanced(string exp)
{
    stack<char> st;
    for(int i=0; i<exp.length(); i++)
    {
        if (exp[i]== '{' || exp[i]=='[' || exp[i]== '(') {
            st.push(exp[i]);
        }
        else if (exp[i]=='}') {
            if (st.top() == '{' && !st.empty()) {
                st.pop();
            }
            else {
                return false;
            }
        else if (exp[i]==')') {
            if(st.top() == '(' && !st.empty()) {
                st.pop();
            }
            else {
                return false;
            }
        }
        else if(exp[i]==']') {
            if(st.top()=='['  && !st.empty()) {
                st.pop();
            }
            else {
                return false;
            }
        }
    }

    if (st.empty()) {
        return true;
    }
    else {
        return false;
    }
}

Now that I can read your code, we can get to the logic issues.

Dealing with bools

You end with if (expr) return true; else return false;. That's exactly equivalent to just:

return st.empty();

Similarly, you have:

bool balanced = balanced(exp);
if (balance == true) ...
else ...

Never write == true, and you don't even need the variable here:

if (balanced(exp)) {
    ...
}
else {
    ...
}

Which can even be a ternary:

cout << (balanced(exp) ? "Yes" : "No") << endl;

Repetition

Your logic is extremely repetitive. We have three types of opens and three types of closed - we treat the opens identically, and we treat the closes the same way - check if the stack is non-empty and the top element is the equivalent open. For any char other than those 6 - we don't care.

So we can collapse our logic to be more explicitly equivalent with the three closes. Also a switch helps a lot here:

switch (exp[i]) {
case '{':
case '[':
case '(':
    st.push(exp[i]);
    break;
case '}':
case ']':
case ')':
    if (!st.empty() && st.top() == open_brace(exp[i])) {
        st.pop();
    }
    else {
        return false;
    }
    break;
default:
    break;
}

Where you just have to implement open_brace to do the right thing. This saves a bunch of code, which in turn makes it less error prone. Also note the reordering of the conditions - you need to check for non-emptiness first.

Arguments

balanced doesn't modify it's argument, or really need to do anything with it other than iterate over it. So take it by reference-to-const:

bool balanced(std::string const& expression)

And lastly...

using namespace std;

Avoid it.

Community
  • 1
  • 1
Barry
  • 286,269
  • 29
  • 621
  • 977