时间戳

首页 > 解决方案 > 我的代码在这里有错误吗？C、队列数据结构

c - 我的代码在这里有错误吗？C、队列数据结构

问题描述

我正在使用我学校的 LinkedList 解决一个涉及堆栈和队列数据结构的问题。

我已经使用 Queue 解决了这个问题，但它仍然无法工作，我希望从外部查看我的代码，看看哪里出了问题。

我已经写了我的问题，给出了下面的代码和我自己的尝试。

这是一个很长的问题，希望我已经做的足够让你们清楚地帮助我:)

让我知道是否有任何不确定性。

我怀疑这取决于在我搜索整个队列以找到合作伙伴后确定结果。

感谢您帮助一个菜鸟:) 我的判断可能在这一点上模糊不清

我的目标/问题 ：编写一个名为balanced()的函数

原型：int平衡（char *表达式）；

该函数处理括号并告诉我它是否平衡（返回 0）或不平衡（返回 -1）。

平衡表达式的示例是：

不平衡表达式的示例是：

预期成绩

输入一个以换行符结尾的表达式：

[({{{}}})[[]]{}({})]

表达是平衡的。

输入一个以换行符结尾的表达式：

{1+2+{5}*[6+x]+{4+5}(3+2)}

表达是平衡的。

输入一个以换行符结尾的表达式：

[5[3(3)4{()]}]

表达不平衡。

**下面是我为函数编写和尝试的代码：balanced()。

代码运行，没有错误提示**

int balanced(char *expression)
{

    Queue q1, q2;

    q1.ll.head = NULL;
    q1.ll.tail = NULL;
    q1.ll.size = 0;

    q2.ll.head = NULL;
    q2.ll.tail = NULL;
    q2.ll.size = 0;

    // transfer all them brackets into a queue called q1
    while ( *expression != '0' )
    {
        if ( *expression != '{' || *expression != '}' || *expression != '[' || *expression != ']' || *expression != '(' || *expression != ')' )
        {
            enqueue( &q1, *expression );
        }
        expression++;
    }
    // at this point, my queue is pure brackets

    char interested, partner, partnerSearch;
    int innerCount, outerCount, almighty;
    innerCount = 0;
    outerCount = 0;
    almighty = -1;

    while (  outerCount != q1.ll.size )
    {
        if( !isEmptyQueue( &q1 ) )
        {
            interested = dequeue( &q1 ); // pick a guy

            // i'll next try to find a match for the bracket by peekQueue
            if ( interested == '{' )
            {
                partner = '}';
            }
            else if ( interested == '[' )
            {
                partner = ']';
            }
            else if ( interested == '(' )
            {
                partner = ')';
            }
            // at this point, they know who their ideal partner is

            // I'll need to run it by a loop for the queue
            innerCount = 0;

            while ( innerCount <  (q1.ll.size - 1) )
            {
                partnerSearch = dequeue( &q1 );

                if( partner != partnerSearch )
                {
                    enqueue( &q1, partnerSearch );
                }
                // so if partner == partnerSearch, it will successfully get dequeue
                // if not they queue back
                innerCount++;
            }
        }
        else
            almighty = 0;
    }

    if ( almighty == 0 )
        return 0;
    else
        return -1;
}

标签： cdata-structuresqueue

解决方案

这段代码：

    if ( *expression != '{' || *expression != '}' || *expression != '[' || *expression != ']' || *expression != '(' || *expression != ')' )
    {
        enqueue( &q1, *expression );
    }

是错的。

假设这*expression是一个'a'. 那么表达式为真。

假设这*expression是一个'{'. 那么表达式为真。

假设这*expression是一个'}'. 那么表达式为真。

换句话说 - 它永远是真实的。

您可能想使用==而不是!=

正如@DavidRanieri 在评论中所写：

while ( *expression != '0' )

是错的。

应该是

while ( *expression != '\0' )

或者干脆

while ( *expression )

总的来说，在我看来，您的方法太复杂了。

我会使用堆栈来完成这项工作。所有左括号都被推入堆栈。当你有一个右括号时，从堆栈中弹出并检查两个括号是否具有相同的类型。

这是一些伪代码：

for ( each character C in expression )
{
   if (C is an opening bracket)
   {
       stack->push(C)
   }
   else if (C is a closing bracket)
   {
       if (stack is empty) return -1

       TMP = stack->pop;
       if (C == '}' and TMP != '{') return -1
       if (C == ']' and TMP != '[') return -1
       ... same for other bracket types ...
   }
}

if (stack is empty) return 0

return -1

在真正的 C 代码中，这可能是：

int check_brackets(char* expression)
{
    stack_t s = {NULL};
    char c = *expression++;
    while(c)
    {
        if (c == '{' || c == '[' || c == '(')
        {
            stack_push(&s, c);
        }
        else if (c == '}' || c == ']' || c == ')')
        {
            if (stack_empty(&s)) return -1;

            char tmp = stack_pop(&s);
            if (
                (c == '}' && tmp != '{') ||
                (c == ']' && tmp != '[') ||
                (c == ')' && tmp != '(')
               )
            {
                stack_free(&s);
                return -1;
            }
        }
        c = *expression++;
    }
    if (stack_empty(&s)) return 0;

    stack_free(&s);
    return -1;
}

（注意：stack_t 和相关函数的实现未显示）

推荐阅读