Balanced parenthesis problem why check if its empty?

Question

I am confused about why do we need to check if the stack is empty? Because then what if for example, the string doesn't have any type or parenthesis, then we will always have false which will mean string is unbalanced? Cant, we even neglect the if(s.empty()) and just return false immediately since there wont be anything pushed inside the stack?

#include<bits/stdc++.h> 
using namespace std; 

// function to check if paranthesis are balanced 
bool areParanthesisBalanced(string expr) 
{ 
    stack<char> s; 
    char x; 

    // Traversing the Expression 
    for (int i=0; i<expr.length(); i++) 
    { 
        if (expr[i]=='('||expr[i]=='['||expr[i]=='{') 
        { 
            // Push the element in the stack 
            s.push(expr[i]); 
            continue; 
        } 
    /*if (expr[i]=='}'||expr[i]=='}'||expr[i]=='}') 
return false; 

    what about this alternative? */


        // IF current current character is not opening 
        // bracket, then it must be closing. So stack 
        // cannot be empty at this point. 
        if (s.empty()) 
        return false; 

        switch (expr[i]) 
        { 
        case ')': 

            // Store the top element in a 
            x = s.top(); 
            s.pop(); 
            if (x=='{' || x=='[') 
                return false; 
            break; 

        case '}': 

            // Store the top element in b 
            x = s.top(); 
            s.pop(); 
            if (x=='(' || x=='[') 
                return false; 
            break; 

        case ']': 

            // Store the top element in c 
            x = s.top(); 
            s.pop(); 
            if (x =='(' || x == '{') 
                return false; 
            break; 
        } 
    } 

    // Check Empty Stack 
    return (s.empty()); 
} 

// Driver program to test above function 
int main() 
{ 
    string expr = "{()}[]"; 

    if (areParanthesisBalanced(expr)) 
        cout << "Balanced"; 
    else
        cout << "Not Balanced"; 
    return 0; 
} 

Answer 1

There two checks for an empty stack. The first is before an attempt to read the top element of the stack and ensures that this element exists. The second at the end of the code is to ensure that no unbalanced opening brackets are left on the stack when the end of the string is reached.

Btw, a shorter version of your code (which also works for strings containing chars other than only brackets) is

bool areParanthesisBalanced(std::string const&expr) 
{ 
    std::stack<char> s;
    for(auto x : expr)
        switch(x) {
        case '[':
        case '(':
        case '{':
            s.push(x);
            break;
        case ']':
            if(s.empty() || s.top() != '[')
                return false;
            s.pop()
            break;
        case ')':
            if(s.empty() || s.top() != '(')
                return false;
            s.pop()
            break;
        case '}':
            if(s.empty() || s.top() != '{')
                return false;
            s.pop()
            break;
        }
    return s.empty();
}