1

完全披露：这是一个任务。我不是在寻找明确的答案，而是在寻找一些指导。

我很难用 C 初始化我的堆栈。具体来说，我似乎无法让它正确地将新元素推送到堆栈上。我知道我的 push/pop/etc 功能是正确的（它们是提供的），但我担心我没有正确看待这个。

这是读取字符串并确定它是否“平衡”的基本尝试（所有括号、大括号和方括号都有伙伴并以正确的顺序出现。）据我所知，这不是我的问题逻辑，我相信语法是正确的，所以我有点不知所措......

这是我的实施尝试：

int isBalanced(char* s) {

struct DynArr *string;
string = newDynArr(50);

while (nextChar(s) != '\0') {
    if ((nextChar(s) == '(') || (nextChar(s) == '{') || (nextChar(s) == '[')) {
        pushDynArr(string, nextChar(s));
    }
    if (nextChar(s) == ')') {
        if (topDynArr(string) != '(') {
            return 0;
        } else popDynArr(string);
    }
    if (nextChar(s) == '}') {
        if (topDynArr(string) != '{') {
            return 0;
        } else popDynArr(string);
    }
    if (nextChar(s) == ']') {
        if (topDynArr(string) != '[') {
            return 0;
        } else popDynArr(string);
    }
}

if (isEmptyDynArr(string)) {
    printf("The stack is empty\n");
    return 1;
} else return 0;
}

输出总是打印“堆栈为空”并返回 true，尽管我给了它不平衡的字符串。我可能已经看这个太久了，无法识别明显的东西。我将不胜感激您可以提供的任何帮助。我不需要明确的答案，但朝着正确的方向推动就足够了。

编辑：这是已请求的功能...

int isEmptyDynArr(DynArr *v) 
{
    if(v->size == 0) {
        return 1;
    }
    else return 0;
}

DynArr* newDynArr(int cap)
{
    assert(cap > 0);
    DynArr *r = (DynArr *)malloc(sizeof( DynArr));
    assert(r != 0);
    initDynArr(r,cap);
    return r;
}

void pushDynArr(DynArr *v, TYPE val)
{
    assert(v != 0);
    addDynArr(v, val);
}

void popDynArr(DynArr *v)
{
    assert(v != 0);
    assert(isEmptyDynArr(v) == 0);
    v->size--;
}

TYPE topDynArr(DynArr *v)
{
    assert(v != 0);
    assert(isEmptyDynArr(v) == 0);
    return v->data[v->size - 1];
}

char nextChar(char* s)
{
    static int i = -1;
    char c;
    ++i;
    c = *(s+i);
    if ( c == '\0' )
        return '\0';
    else
        return c;
}
4

2 回答 2

2

此行可能会从输入行中跳过 1 个或 2 个或 3 个字符：

nextChar(s) == '(') || (nextChar(s) == '{') || (nextChar(s) == '['

你绝对应该使用：

char ch = nextChar(s);
if( ch == '(' || ch == '{' || c == '[' )
于 2012-11-27T09:13:45.307 回答
1

你似乎没有在s任何地方增加。你的nextChar功能是做什么的？我只能猜测，但它似乎只会返回*s。如果是这种情况，您需要++s在每次迭代后递增 s ( )。如果它确实神奇（因为在纯 C 中确实没有一种明智的方法来做到这一点）无论如何都会增加 s，那么您应该每次迭代只调用一次并保存结果。我猜是前者，在这种情况下，例如对于这个字符串：“(())”，您将读取第一个 '(' 两次并返回 0。

更新：是的，显然您的 nextChar 函数确实使用了全局计数器。建议二适用，每次迭代只调用一次。或者更好的是，摆脱那个东西。该功能的设计方式，您可以在程序的整个生命周期中有效地使用它一次，并且该功能的整个功能都可以替换为 (*s ? *(s++) : *s)。或者只是 *(s++) （自己检查 0 ）。

于 2012-11-27T09:14:23.217 回答