时间戳

首页 > 解决方案 > 平衡括号问题为什么要检查它是否为空？

c++ - 平衡括号问题为什么要检查它是否为空？

问题描述

我很困惑为什么我们需要检查堆栈是否为空？因为如果例如，字符串没有任何类型或括号，那么我们将总是有 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; 
}

标签： c++algorithmstack

解决方案

有两个空堆栈检查。第一个是在尝试读取堆栈的顶部元素并确保该元素存在之前。代码末尾的第二个是确保到达字符串末尾时不会在堆栈上留下不平衡的左括号。

顺便说一句，您的代码的较短版本（也适用于包含chars 而不仅仅是括号的字符串）是

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

推荐阅读