c++ - c++中if语句中的多个条件(通过链接列表实现堆栈)

我正在尝试创建一个程序，以评估一堆括号的正确实现方式(即，如果一个括号包含打开和关闭的组件，则该括号有效，因此返回“true”)。例如，[[]] {} {()()}为true，而[[{})为false。

目前，我将要完成程序，但是，用于堆栈评估的逻辑运算符无法正常运行。

我使用Xcode进行编程，该问题可能与IDE有关，但可能性不大。问题:线程1:EXC_BAD_ACCESS(代码= 1，地址= 0x0)

程序不完整。我将插入一串方括号作为输入，并使用递归来评估堆栈，以删除堆栈中的所有元素(如果方括号逻辑正确，在这种情况下(“[() ]{}{()()}“) 是正确的。所需的逻辑如下:

s.evaluate-> [] {[]}

s.evaluate-> {}

s.evaluate-> true

#include<iostream>

using namespace std;

struct node
{
    char bracket;
    node* next;
};

class stack
{
    node* top;

public:
    // constructure
    stack()
    {
        top = NULL;
    }

    void push(char bracket); // to insert an element
    void pop();  // to delete an element
    void evaluate(); // to evaluate the stack for brackets' logic
    void show(); // to show the stack

    bool isPair(node* n2, node* n1) {

        if ((n1->bracket == '(' && n2->bracket == ')') || (n1->bracket == '[' && n2->bracket == ']') || (n1->bracket == '{' && n2->bracket == '}')) {
            return true;
        } else {
            return false;
        }
    }
};

// insert an element
void stack::push(char bracket)
{
    char value = bracket;
    node* ptr;

    ptr = new node;
    ptr->bracket = value;
    ptr->next = NULL;

    if (top != NULL)
        ptr->next = top;

    top = ptr;

}

// delete an element
void stack::pop()
{
    node* temp;

    if (top == NULL)
    {
        cout << "\nThe stack is empty.";
    }

    temp = top;
    top = top->next;
    cout << "\nPOP Operation" << endl << "Poped value is " << temp->bracket;
    delete temp;
}

// evaluate a stack for bracket logic
void stack::evaluate()
{
    node* target = top;
    node* targetNext = target->next;
    node* temp;
    node* tempNext;

    if (target == NULL)
    {
        cout << "\nTrue" << endl;
    }

    while (target != NULL)
    {
        if (isPair(targetNext, target)) {
            temp = targetNext->next;
            tempNext = temp->next;

            cout << target->bracket << " and " << targetNext->bracket << " are deleted" << endl;

            delete target;
            delete targetNext;

            target = temp;
            targetNext = tempNext;

        } else {
            target = target->next;
            targetNext = target->next;
        }
    }

}


// Show stack
void stack::show()
{
    node* ptr1 = top;
    cout<<"\nThe stack is\n";
    while(ptr1 != NULL)
    {
        cout << ptr1->bracket << " -> ";
        ptr1 = ptr1->next;
    }
    cout << "NULL\n";
}

// Main function
int main()
{
    stack s1;

    string brackets = "[()]{}{[()()]()}";

    for(char& c : brackets) {
        s1.push(c);
    }

    s1.show();

    s1.evaluate();

    s1.show();

    return 0;
}

现在，我专注于if逻辑部分。我将表示法从:

bool isPair(node* n2, node* n1) {

    if ((n1->bracket == '(' && n2->bracket == ')') || (n1->bracket == '[' && n2->bracket == ']') || (n1->bracket == '{' && n2->bracket == '}')) {
        return true;
    } else {
        return false;
    }
}

至:

bool isPair(node* n2, node* n1) {

    if (n1->bracket == '(' && n2->bracket == ')')
    {
        return true;
    }

    else if (n1->bracket == '[' && n2->bracket == ']')
    {
        return true;
    }

    else if (n1->bracket == '{' && n2->bracket == '}')
    {
        return true;
    }

    else
    {
        return false;
    }
}

但这并没有改变任何东西(如预期的那样)。为什么Xcode不想完全执行我的代码？

当前输出为:

The stack is
} -> ) -> ( -> ] -> ) -> ( -> ) -> ( -> [ -> { -> } -> { -> ] -> ) -> ( -> [ -> NULL
( and ) are deleted
{ and } are deleted
(lldb)

我知道，代码非常实用，我是C++和数据结构的新手，尽管您的帮助得到了大家的赞赏! 😄

最佳答案

我在您的代码中看到的问题:

问题1

删除target和targetNext时，将留下悬空的指针。

假设您有:

          target     targetNext
           |          |
           v          v
+----+     +----+     +----+
|    | --> |    | --> |    |
+----+     +----+     +----+

删除target和targetNext后，剩下的是:

node with dangling pointer
|
v
+----+     +----+     +----+
|    | --> | x  | --> | x  |
+----+     +----+     +----+

您要跟踪target之前的节点，并确保将其next设置为targetNext->next。

执行此操作时，必须小心处理top和target是同一节点的情况。

您需要使用:

// Special case the top node.
if ( top == target )
{
   top = prev = targetNext->next;
}
else
{
   prev->next = targetNext->next;
}

问题2

删除一对匹配的括号时，您需要从顶部开始检查。否则，您将永远无法匹配外括号。

假设您以“[[()]””开头。
您删除内部匹配对“()”。现在，您剩下的是“[]”。
如果您没有从头开始，则其余的一对将匹配。

删除target和targetNext后，您需要使用以下逻辑。

// Start checking from the top.
target = top;
if (target == NULL)
{
   cout << "\nTrue" << endl;
   return;
}

targetNext = target->next;
if ( targetNext == NULL )
{
   cout << "\nFalse" << endl;
   return;
}

问题3

使用防御性编程。在设置target之前，请始终检查targetNext是否有效，即是否为NULL。将函数顶部更改为:

node* target = top;
node* targetNext = NULL;
if ( target != NULL )
{
   targetNext = target->next;
}

在循环中也添加类似的检查。

if (isPair(targetNext, target)) {
   ...
} else {
   target = target->next;
   if ( target != NULL )
   {
      targetNext = target->next;
   }
   else
   {
      targetNext = NULL;
   }
}

问题4
isPair中的预期节点已切换。

当输入字符串为“[()]”时，堆栈对象为:

] -> ) -> ( -> [ -> NULL

当target指向')'时，targetNext指向'(`。

您检查target和targetNext是否指向匹配对的调用是:

if (isPair(targetNext, target)) {

在isPair中，您具有:

bool isPair(node* n2, node* n1) {
    if ((n1->bracket == '(' && n2->bracket == ')') ...

如您所见，n1和n2被翻转。您应该将其更改为:

bool isPair(node* n1, node* n2) {
    if ((n1->bracket == '(' && n2->bracket == ')') ...

或在调用函数时切换参数。

问题5

括号不匹配时，您将无法输出False。

清理了isPair和evaluate的版本:

bool isPair(node* n1, node* n2)
{
   return ( (n1->bracket == '(' && n2->bracket == ')') ||
            (n1->bracket == '[' && n2->bracket == ']') ||
            (n1->bracket == '{' && n2->bracket == '}'));
}

void stack::evaluate()
{
   node* target = top;
   node* prev = top;

   while ( target )
   {
      node* targetNext = target->next;
      if ( targetNext == NULL )
      {
         cout << "\nFalse" << endl;
         return;
      }

      if (isPair(targetNext, target)) {

         cout << target->bracket << " and " << targetNext->bracket << " are deleted" << endl;

         // Special case the top node.
         if ( top == target )
         {
            top = prev = targetNext->next;
         }
         else
         {
            prev->next = targetNext->next;
         }

         delete target;
         delete targetNext;

         // Intermediate output for troubleshooting.
         // this->show();

         // Start checking from the top.
         target = top;
      }
      else
      {
         prev = target;
         target = target->next;
      }
   }

   cout << "\nTrue" << endl;
   return;
}

关于c++ - c++中if语句中的多个条件(通过链接列表实现堆栈)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47304784/