Проблема со сбалансированными скобками, зачем проверять, пусто ли это?

Question

Я не понимаю, зачем нам проверять, пуст ли стек? Потому что тогда, что если, например, строка не имеет какого-либо типа или круглых скобок, то у нас всегда будет false, что будет означать, что строка не сбалансирована? Не можем, мы даже пренебрегаем if(s.empty()) и просто сразу возвращаем false, поскольку внутри стека ничего не помещается?

#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

Есть две проверки на пустой стек. Первый перед попыткой прочитать верхний элемент стека и гарантирует, что этот элемент существует. Вторым в конце кода является обеспечение того, чтобы при достижении конца строки в стеке не оставалось несбалансированных открывающих скобок.

Кстати, более короткая версия вашего кода (которая также работает для строк* содержит char с, кроме только скобок)

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