Multiple conditions in if statement in c++ (Stack implementation via Linked List)

Question

I am trying to create a program which evaluates a stack of brackets for their correct implementation (i.e. if a bracket has opening and closing components, the bracket is valid, therefore it returns "true"). For example [()]{}{()()} is true while [({}) is false.

Currently, I am about to finish the program, although, the logical operator for stack evaluation does not work quite right.

I program in Xcode, and the problem can be related specifically for the IDE, but it is unlikely. The issue: Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)

The program is not complete. I am about to insert a string of brackets as an input, and use a recursion for the evaluation of stack, in order to delete all the elements in a stack, if the bracket logic is correct, which in this case ("[()]{}{()()}") is correct. The desired logic is below:

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

For now, I concentrate on the if logic part. I have changed the notation from:

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

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

to:

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

But it did not change anything (as expected). Why Xcode do not want to proceed my code fully?

Current output is:

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

I know, the code is very noobie, I am new to C++ and data structures, although, your help is utterly appreciated!

Answer 1

Problems I see in your code:

Problem 1

You are leaving dangling pointers when you delete target and targetNext.

Let's say you have:

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

After you delete target and targetNext, you are left with:

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

You have keep track of the node previous to target and make sure that its next is set to targetNext->next.

When you do that, you have to be careful to deal with the case where top and target are the same node.

You'll need to use:

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

Problem 2

When you delete a pair of matching brackets, you'll need to start the check from the top. Otherwise, you will never be able to match outer brackets.

Let's say you start with "[()]".
You delete the inner matching pair, "()". Now you are left with "[]".
If you don't start from the top, the remaining pair will lever be matched.

You'll need to use the following logic after you delete target and 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;
}

Problem 3

Use defensive programming. Always check whether target is valid, i.e. it is not NULL, before setting targetNext. Change the top of the function to:

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

Add similiar checks inside the loop too.

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

Problem 4

The expected nodes in isPair is switched.

When the input string is "[()]", the stack object is:

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

When target points to ')' , targetNext points to '(`.

Your call to check whether target and targetNext point to a matching pair is:

if (isPair(targetNext, target)) {

In isPair, you have:

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

As you can see, n1 and n2 are flipped. You should change it to:

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

or switch the arguments when calling the function.

Problem 5

You are missing to output False when there are mismatching brackets.

---

Cleaned up versions of isPair and 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;
}