简单的Stack和Map程序卡住了

Question

这个简单的程序有什么问题以及为什么它在 cpp.sh

上处于挂起状态

#include <stack>
#include <map>
#include <set>
#include <iostream>

using namespace std;

int main()
{    
    string expression {")"};    
    stack<char> mystack;
    map<char, char> mymap{ {'(', ')'}, {'[', ']'}, {'{', '}'} };
    set<char> myset{ ')', ']', '}'};

    for(auto &i: expression)
    {
        if(mymap.count(i) == 1)
        {
            mystack.push(i);
        }
        
        else if(myset.count(i) == 1)
        {
            cout << "Received :: " << i << endl;
            
            if(mymap.at(mystack.top()) == i)
            {
                cout << " Popped: " << mystack.top() << endl;
                mystack.pop();
            }
            else
            {
                cout << "Non Balanced" << endl;
                break;
            }
        }
    }
    if(mystack.size() != 0)
    {
        cout << "Non Balanced" << endl;
    }
    return 0;
}

Answer 1

您遇到的问题是由于您尝试访问空堆栈的顶部，这会导致未定义的行为。具体来说，当输入表达式以右括号开头（例如，

expression = ")"

）时，程序会进入连续尝试从空堆栈中弹出的状态。

要解决此问题，您应该在使用

mystack.top()

之前添加检查以确保堆栈不为空。

for(auto &i: expression)
{
    if(mymap.count(i) == 1)
    {
        mystack.push(i);
    }
    
    else if(myset.count(i) == 1)
    {
        cout << "Received :: " << i << endl;
        
        if(!mystack.empty() && mymap.at(mystack.top()) == i)
        {
            cout << " Popped: " << mystack.top() << endl;
            mystack.pop();
        }
        else
        {
            cout << "Non Balanced" << endl;
        }
    }
}

通过此修改，您的程序应该可以正确处理平衡和不平衡括号的各种情况。

请记住使用各种输入表达式来测试您的程序，以确保它正确处理所有情况。