I have set of lines which I read from a file that gets stored as an array stack of characters. A function called procssline gets called with the stored stack as a parameter. One of the lines reads as follows:

Nn<-<-<-<-No <-w iz<-sthe<-<-<- the time.

Where the top of the stack is the '.', and the bottom is the 'N' respectively.

The function processes the line by taking each "<-" as a 'backspace' and subsequently rewriting (pushing) the line into a result stack so that it would turn into this when I pop off the result stack and output the characters:

Now is the time.

I have access to the typical stack functions: pop, push, and peek. I'm trying to come up with an algorithm for it but I'm having difficulty coming up with a proper loop. This is my current version, which compiles, but doesn't run through properly and outputs the first character of the result of the first line as a '<'

void processLine(stack<char> &array, int linelength)
{
  char catchvar1;
  char catchvar2;
  int bscount = 0;
  stack<char> result;

  for (int i = 0; i < linelength; i++)
  {
 
  array.pop(catchvar1); //pops first character
  if (catchvar1 == '-')  //if its a '-', then pop off the next character too
  {
    array.pop(catchvar2);
    if (catchvar2 == '<')  //if the next character is a '<', add to backspace counter
    {
      bscount++;
    }
    else 
    {
      result.push(catchvar1);
      result.push(catchvar2); 
    } 
   } 
  else                    //if the popped character is not a '-'
    {
      if (bscount = 0)    //if bscount = 0, popped character gets pushed onto new stack
      {
      result.push(catchvar1); 
      }
      else               //if bscount is >0, bscount gets decremented and popped character 
      {                  //stays popped off
      bscount--;
      }
    
    }  
 } 
  char resultvar;
  result.pop(resultvar);
  cout << resultvar << endl; 
}

Also, here are my implementations for the pop and push functions, in case there is something awry in it:

template <class stackElem, int maxSize>
bool stack<stackElem, maxSize>::push(const stackElem &item)
{
  top++;         
  elements[top] = item; 
 }

template <class stackElem, int maxSize>
bool stack<stackElem, maxSize>::pop(stackElem &item)
{
 item = elements[top];
 top--;
 
 }

Okay let me help you with the algorithm, it will be a simple one.


This is you stack content: [N,n,<,-,<,-,<,-,<,-,N,o, ,<,-,w, ,i,z,<,-,s,t,h,e,<,-,<,-,<,-, ,t,h,e, ,t,i,m,e,.]

where as you said the top of the stack is '.' and bottom of the stack is 'N';

Now to make the algorithm easier first you should reverse the stack. Think about how to achieve this.

Now assume the stack is reversed, that is, it is now this:
[.,e,m,i,t, ,e,h,t, ,-,<,-,<,-,<,e,h,t,s,-,<,z,i, ,w,-,<, ,o,N,-,<,-,<,-,<,-,<,n,N]

so now 'N' is the top of the stack, and '.' is the bottom. So as you know, because of the property of stack, you can only access the top of it at a given time. So this should hint you that, the problem will be easier if you used more than one stack.

Hence we create a resultStack. This stack will store the result.

Now we have the preliminary out of the way take a look at the idea. The idea is to save the previous character and use the current character to determine if that sequence made a backspace character. That's really it. Here is the implementation,

stack<char> processLine(const stack<char> &stk){
  stack<char> src(reverseStack(stk));
  stack<char> resultStack;
  char prev = -1;  
  while(! src.empty()){
	  char top = src.top();
	  //if no sign of backspace just add it
	  if(top != '-' && top != '<' && prev != '<'){		
		  resultStack.push(top);
	  }
	  //else its either '-' or '<', so do proper checking
	  else{
		  //check if the 2 sequenced character created a backspace? 
		  if(prev == '<' && top == '-'){
			  //backspace detected, so pop top if any
			  if(!resultStack.empty()) resultStack.pop();
		  }
		  prev = top; //update previous		 
	  }
	  src.pop();
  }
  return reverseStack(resultStack);
}

the 'reverseStack' returns the given stack in reverse ordered. Try the idea out and see how it fits. Here is a live code

Edited 5 Years Ago by firstPerson: n/a

I got it now! Thanks so much firstPerson, I don't know why I didn't think of how easier it would be in reverse order haha! We actually had a choice between queues and stacks, and I realize now how much more I'd probably prefer the FIFO structure of queues!

Thanks again, I hope you didn't take too much time to write that example out for me (I know coming up with/writing out that code would have taken me more than an hour alone!). :)

If I understand you correctly, this thread offered no help at all and you decided to post another thread with the exact same question? This one's closed, continue with the original.

Plus, I gave you an (almost) perfect algorithm to do this task.

This article has been dead for over six months. Start a new discussion instead.