检查平衡分组字符时在线判断运行时错误

Question

这是我的代码，用于检查一串分组字符是否适当平衡。它在我的本地机器上工作正常，但在线判断给我一个运行-次错误。

#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;
}

Answer 1

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

你应该在取顶之前检查堆栈是否为空。

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

Answer 2

间距

我对您的间距和大括号的使用有一些疑问。首先，您在循环中的逻辑过于缩进。一个缩进就可以了。其次，不要在 if 的同一行写逻辑，除非它是一个微不足道的条件并且没有 else - 永远不要在 else 的同一行写逻辑。无法阅读。非常喜欢自始至终写大括号。在if

之后也加一个space

这里用更好的间距进行了平衡重写：

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

现在我可以阅读你的代码了，我们可以开始逻辑问题了。

处理布尔值

你以 if (expr) return true; else return false; 结束。这完全等同于：

return st.empty();

同样，您有：

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

永远不要写== true，你甚至不需要这里的变量：

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

甚至可以是三元的：

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

重复

你的逻辑非常重复。我们有三种类型的打开和三种类型的关闭 - 我们以相同的方式对待打开，我们以相同的方式对待关闭 - 检查堆栈是否为非空以及顶部元素是否为等效的打开。对于这 6 个以外的任何字符 - 我们不在乎。

所以我们可以折叠我们的逻辑，使其更明确地等同于三个关闭。开关在这里也有很大帮助：

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

您只需实施 open_brace 即可做正确的事。这节省了一堆代码，这反过来又使它更不容易出错。还要注意条件的重新排序 - 您需要先检查非空。

参数

balanced 不修改它的参数，或者除了迭代它之外真的需要用它做任何事情。所以通过 reference-to-const:

bool balanced(std::string const& expression)

最后...

using namespace std;

Avoid it.

检查平衡分组字符时在线判断运行时错误

Online judge runtime error when checking for balanced grouping characters

c++

stack

runtime-error