K&R练习1-24

Question

练习1-24。编写一个程序来检查C程序中的基本语法错误，如不匹配的括号、方括号和大括号。不要忘记引号，包括单引号和双引号，转义序列和注释。（如果以完全的一般性来做这个程序会很难。）

这是我为这个程序编写的代码（还没有完成，稍后我会继续完善）：

#include <stdio.h>

#define YES 1
#define NO 0

int a = 0;

void push(int stack[], int c);
void pull(int stack[]);
int check(int stack[], int c);

int main()
{
    int stack[1000], c, keep = 1;

    extern int a;

    while ((c = getchar()) != EOF && keep == YES)
    {
        if (c == '[' || c == '(' || c == '{')
            push(stack, c);

        else if (c == ']' || c == ')' || c == '}')
            keep = check(stack, c);

    }

    return 0;
}

void push(int stack[], int c)
{
    int i;

    for (i = a; i; --i)
        stack[i+1] = stack[i];

    ++a;

    stack[0] = c;
}

void pull(int stack[])
{
    int i;

    --a;

    for (i = 0; i < a; ++i)
        stack[i] = stack[i+1];

    stack[a] = '\0';
}

int check(int stack[], int c)
{
    if ((c == ']' && stack[0] == '[') || (c == ')' && stack[0] == '(') || (c == '}' && stack[0] == '{'))
    {
        pull(stack);
        return YES;
    }

    else
    {
        printf("Mismatched character: '%c'\n", c);
        return NO;
    }
}

当我给它一个输出像{}或( ) () {} []这样的时候，它可以工作，但是对于像(())这样的输入，它给我返回了这个输出：

- hansoko

---

为什么你不继续“推”到最后呢？这样看起来会大量改变顺序，违背了使用栈的初衷。 - tadman

为什么不按照C语言的本意使用，用0表示假，非零（默认为1）表示真，而是要自己创造一个带有“YES”和“NO”的C方言呢？ - tadman

我建议编写一个堆栈库，包括测试以确保您的堆栈库正常工作。然后在这个括号匹配代码中使用经过测试和验证的库。目前很难确定错误是在您的堆栈实现还是匹配实现中。如果您正在完成K&R练习，那么您肯定会重复使用该库。 - JohnFilleau

值得注意的是，你将开头字符推入堆栈，但接下来却需要一个非常烦人的检查函数来进行反转。为什么不推入你期望的结束字符呢？这样可以大大简化操作，在推入方面几乎没有额外的成本。在这里使用switch可能是个好主意。 - tadman

您的错误报告可以更好。不仅仅是“字符不匹配”，还要考虑报告不匹配的位置。 - JohnFilleau

Answer 1

你的push程序有问题。当i为零时，循环for (i = a; i; --i)从不执行循环体，因此它从不执行stack[1] = stack[0]。你需要将测试条件改为i >= 0。（然而，有一种更好的方法来实现一个栈，而不是每次push或pop时都移动所有元素。另外，我们称从栈顶移除一个项目为“pop”，而不是“pull”。）

- Eric Postpischil