Finding and replacing elements in a linked list-CodePudding

I'm trying to add a function (ReplaceItem()) that finds existing elements in a linked list and replaces them with a new element. I'm a novice programmer, and I'm not sure how to continue.

Currently, if the function finds the element it wants to replace, it gets rid of the first element and adds in the new one, but the problem is it can't check the following ones. It also never ends because the stack won't ever be empty.

The idea I had while programming this was to keep popping the stack until the end, and then push all the elements back in with the needed elements replaced. There's most definitely a better way, but that was what I came up with at the time. I was told I could use any member functions of StackType but not "assume any knowledge of the stack's implementation".

StackDr.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <cctype>
#include <cstring>

#include "StackType.h"
using namespace std;

void ReplaceItem(StackType& stack , ItemType oldItem , ItemType newItem);

int main()
{
  ifstream inFile;       // file containing operations
  ofstream outFile;      // file containing output
  string inFileName;     // input file external name
  string outFileName;    // output file external name
  string outputLabel;
  string command;        // operation to be executed

  char item;
  StackType stack;
  int numCommands;

  // Prompt for file names, read file names, and prepare files
  cout << "Enter name of input command file; press return." << endl;
  cin  >> inFileName;
  inFile.open(inFileName.c_str());

  cout << "Enter name of output file; press return." << endl;
  cin  >> outFileName;
  outFile.open(outFileName.c_str());

  cout << "Enter name of test run; press return." << endl;
  cin  >> outputLabel;
  outFile << outputLabel << endl;

  inFile >> command;

  numCommands = 0;
  while (command != "Quit")
  {
    try
    {
      if (command == "Push")
      {
        inFile >> item;
        stack.Push(item);
      }
      else if (command == "Pop")
        stack.Pop();
      else if (command == "Top")
      {
        item = stack.Top();
        outFile<< "Top element is " << item << endl;
      }
      else if (command == "IsEmpty")
        if (stack.IsEmpty())
          outFile << "Stack is empty." << endl;
        else
          outFile << "Stack is not empty." << endl;

      else if (command == "IsFull")
        if (stack.IsFull())
          outFile << "Stack is full." << endl;
        else outFile << "Stack is not full."  << endl;
      else
        outFile << command << " not found" << endl;
    }
    catch (FullStack)
    {
      outFile << "FullStack exception thrown." << endl;
    }

    catch (EmptyStack)
    {
      outFile << "EmptyStack exception thrown." << endl;
    }

    numCommands  ;
    cout <<  " Command number " << numCommands << " completed."
         << endl;
    inFile >> command;

  };

  cout << "Testing completed."  << endl;
  inFile.close();
  outFile.close();
  return 0;
}

void ReplaceItem(StackType& stack , ItemType oldItem , ItemType newItem)
{
    while(stack.IsEmpty() == false)
    {
        char item;
        item = stack.Top();
        if(oldItem == item)
        {
            stack.Pop();
            stack.Push(newItem);
        }
    }
}

StackType.cpp

// Implementation file for linked StackType
#include "StackType.h"
#include <new>

struct NodeType
{
  ItemType info;
  NodeType* next;
};

bool StackType::IsFull() const
// Returns true if there is no room for another ItemType
//  on the free store; false otherwise.
{
  NodeType* location;
  try
  {
    location = new NodeType;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

bool StackType::IsEmpty() const
{
  return (topPtr == NULL);
}

void StackType::Push(ItemType newItem)
// Adds newItem to the top of the stack.
// Stack is bounded by size of memory.
// Pre:  Stack has been initialized.
// Post: If stack is full, FullStack exception is thrown;
//       else newItem is at the top of the stack.
{
  if (IsFull())
    throw FullStack();
  else
  {
    NodeType* location;
    location = new NodeType;
    location->info = newItem;
    location->next = topPtr;
    topPtr = location;
  }
}

void StackType::Pop()
// Removes top item from Stack and returns it in item.
// Pre:  Stack has been initialized.
// Post: If stack is empty, EmptyStack exception is thrown;
//       else top element has been removed.
{
  if (IsEmpty())
    throw EmptyStack();
  else
  {  
    NodeType* tempPtr;
    tempPtr = topPtr;
    topPtr = topPtr->next;
    delete tempPtr;
  }
}

ItemType StackType::Top()
// Returns a copy of the top item in the stack.
// Pre:  Stack has been initialized.
// Post: If stack is empty, EmptyStack exception is thrown;
//       else a copy of the top element is returned.
{
  if (IsEmpty())
    throw EmptyStack();
  else
    return topPtr->info;  
}

StackType::StackType()  // Class constructor.
{
  topPtr = NULL;
}

StackType::~StackType()
// Post: stack is empty; all items have been deallocated.
{
  NodeType* tempPtr;

  while (topPtr != NULL)
  {
    tempPtr = topPtr;
    topPtr = topPtr->next;
    delete tempPtr;
  }
}

StackType.h

typedef char ItemType;
struct NodeType;

class FullStack
// Exception class thrown by Push when stack is full.
{};

class EmptyStack
// Exception class thrown by Pop and Top when stack is emtpy.
{};

class StackType {
public:
    StackType();
    ~StackType();
    void Push(ItemType);
    void Pop();
    ItemType Top();
    bool IsEmpty() const;
    bool IsFull() const;

private:
    NodeType* topPtr;
};

CodePudding user response：

Since ReplaceItem() doesn't have access to StackType's internals, all it can do is pop and push items. So you will have to create a whole new stack, and then assign it back to the original stack.

Also, if the 1st element of the original stack is not your old value, your function gets stuck in an endless loop. So you have to pop items from the original stack just to progress your loop correctly, so you will have to remember what you need to re-push anyway.

Try something like this:

void ReplaceItem(StackType& stack, ItemType oldItem, ItemType newItem)
{
    StackType newStack;

    while (!stack.IsEmpty())
    {
        char item = stack.Top();
        stack.Pop();

        if (oldItem == item)
            newStack.Push(newItem);
        else
            newStack.Push(oldItem);
    }

    // unfortunately, StackType does not implement copy or
    // move semantics, otherwise you could have simply used:
    //
    // stack = newStack;
    // or
    // stack = std::move(newStack);
    //
    // So, you will just have to Push manually instead...
    //
    while (!newStack.IsEmpty()) {
        char item = newStack.Top();
        newStack.Pop();
        stack.Push(item);
    }
}

However, if you are at liberty to alter StackType, then you should add a Replace() method to StackType, and then the logic becomes much more efficient since you can then access the node data directly, eg:

class StackType {
public:
    ...
    void Replace(ItemType oldItem, ItemType newItem);
    ...
};

void StackType::Replace(ItemType oldItem, ItemType newItem)
{
  NodeType* tempPtr = topPtr;
  while (tempPtr != NULL)
  {
    if (tempPtr->info == oldItem)
      tempPtr->info = newItem;
    tempPtr = tempPtr->next;
  }
}

void ReplaceItem(StackType& stack, ItemType oldItem, ItemType newItem)
{
    stack.Replace(oldItem, newItem);
}