Function that reads "<-" as a backspace in a array stack!

[fsefsef23]

Sorry for the confusing title. Basically I have a line which I read from a file that gets stored as an array stack of characters that 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.

I need to write a function that processes the line by taking each "<-" as a 'backspace' and subsequently rewriting the line so that it would turn into this

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 something that works with any number of consecutive backspaces! As you can see one backspace is simple enough, but any more than one and I'm in trouble!

void processLine(stack<char> &array, int linelength)
{
  char discardvar;
  char catchvar; 
  
  for (int i = 0; i < linelength; i++)
  {
  array.pop(catchvar);
  if (catchvar == '-') //if there is a '-', pop off the '<' and the letter its erasing
  {
    array.pop(discardvar);  
    array.pop(discardvar);
  }
  else if (catchvar == '<')
  {

  }
  else 
   array.push(catchvar); //placeholder, didn't think of way to reconstruct line yet 
}
}

If any additional information is needed that I haven't provided, please let me know! Thanks in advance!

[WaltP]

Sorry for the confusing title.

At least you tried... :icon_mrgreen:

Thing #1:

if (catchvar == '-') //if there is a '-', pop off the '<' and the letter its erasing
  {
    array.pop(discardvar);  
    array.pop(discardvar);
  }

What if the sentence is supposed to be "Now- the time is now!" when done?

Thing #2:
Pop the 'good characters' into a string and delete from there. When done, push them back. You don't want to edit the stack directly, which is what you're trying to do.

[fsefsef23]

I'm trying to get an algorithm that gets rid of the "<-" but also understands how many letters to erase when they appear consecutively and pops them off too! I don't think if i put it into a string it would make any difference, since I'll still need to sort through the line. I wouldn't worry about if the sentence has a lone "-" in it for now either.

[WaltP]

As you reach a <-, count it in delcount. When you pop a regular character, if delcount > 0 throw the character away and decrement delcount.

As for the lone -, given the above sentence "this is a trial- new and improved" results in "this is a tri new and improved". You can't just blindly pop the <.

[fsefsef23]

So far here is what I have:

void processLine(stack<char> &array, int linelength)
{
  char discardvar;
  char catchvar;
  int bscount;
  //stack<char> result;  ignore until loop is sorted out
  
  for (int i = 0; i < linelength; i++)
  {
    bscount = 0;
    array.peek(catchvar);
    while(catchvar == '-')
    {
    array.pop(discardvar);
    array.pop(discardvar); 
    bscount +=1;
    }
    for (int i = 0; i < bscount; i++)
    {
      array.pop(discardvar);
    }
  }  
}

The intention of this loop is that when it finds a '-', it pops the '-' and its subsequent '<' attached to it (again, not concerned with a lone '-' right now), and then adds 1 bscount. It then peeks again and sees if the next value after the "<-" is another backspace. If so, it will do the same until it reaches a character. It then pops off the number of characters based on bscount. I'm terrible with loops so please let me know if the code works the way I explained it haha!

[WaltP]

Just pop a character
If '-' then
{
   pop a character
   if '<' then 
   {
      increment bscount
      discard both characters
   }
   else
   {
      don't discard the characters
   }
}
else
{
    if bscount = 0
    {
       don't discard the character
    }
    else
    {
       discard the character
       decrement bscount
    }
}

That's what you need in a nutshell. What you are doing on a sequence of <-<-<- is popping the -, then blindly discarding the < and -. Next pop gets you <.

There's a little more logic to be added, but that will get you to 2nd base.

[mrnutty]

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!).

As a reply to your other post, since that thread was closed, NP. Took about 15-20 minutes. Just a tip, when you try to solve a problem, think about the simplest solution first, and take it step by step.

[WaltP]

The problem with FirstPerson's solution to reverse the stack is ... it's a stack. Stacks should not be manipulated in weird ways.

All you need to do is pop the values and you get the data in the proper order to perform the task. A pop gets the last value -- the '.'. The next pop gets '-', then '<'. This is simple. No overhead by reversing, no manipulating the stack in ways that stacks are not meant to be handled. No second or third stacks.

What part of my algorithm didn't make sense?

[mrnutty]

The problem with FirstPerson's solution to reverse the stack is ... it's a stack. Stacks should not be manipulated in weird ways.

All you need to do is pop the values and you get the data in the proper order to perform the task. A pop gets the last value -- the '.'. The next pop gets '-', then '<'. This is simple. No overhead by reversing, no manipulating the stack in ways that stacks are not meant to be handled. No second or third stacks.

What part of my algorithm didn't make sense?

The problem with that way is that one would need a counter since there could be multiple backspaces, thus when adding new elements, one would use counter to check if it should be added or not. If you reverse the stack, then the emphasis is not on adding, but on popping, that is instead of having to worry about whether to push the next value depending on how many backspaces were encountered, one would simply pop value if there was any.

Anyways, if you are allowed to queue, then thats essentially better than reversing the stack, since reversing the stack essentially transforms the stack into a queue.

[WaltP]

The problem with that way is that one would need a counter since there could be multiple backspaces,

Of course. If you have multiple BS's, you need to know how many.

thus when adding new elements, one would use counter to check if it should be added or not. If you reverse the stack, then the emphasis is not on adding, but on popping, that is instead of having to worry about whether to push the next value depending on how many backspaces were encountered, one would simply pop value if there was any.

Not following you. Original post states "array stack of characters that reads as follows:
Nn<-<-<-<-No <-w iz<-sthe<-<-<- the time." Therefore you have a stack that contains the information. You mention adding. Adding what? To where? The only thing you can do with the stack given is pop. There is no adding. Please explain what is lacking in my algo as a way to answer the original post. All popping. As a stack with data is supposed to do.

[mrnutty]

Of course. If you have multiple BS's, you need to know how many.

Yes but if you reverse the stack, then a counter is not needed as shown by the algorithm I posted in the other thread.

Not following you. Original post states "array stack of characters that reads as follows:
Nn<-<-<-<-No <-w iz<-sthe<-<-<- the time." Therefore you have a stack that contains the information. You mention adding. Adding what? To where? The only thing you can do with the stack given is pop. There is no adding. Please explain what is lacking in my algo as a way to answer the original post. All popping. As a stack with data is supposed to do.

In you algorithm, you have something that says in psuedocode, "don't discard the characters". Well then he's gonna have to store it somewhere else, presumably in another stack, assuming he's not allowed to store it in vectors or strings.
So with your algorithm, every time you find a valid character to add to that another stack, you have to check to see if the backspace counter is greater than 0, if so then don't add it to the stack and decrements counter, hence the emphasis is on adding. But if you reverse the stack then every time you encounter a backspace, you can simply just remove the last element added in the result stack, or wherever he stores the "don't discard the characters'" part. You get it?

[WaltP]

I just looked at your code. It is identical to mine. You are counting the number of BS's and not pushing, whereas I count the number of BS's and "don't discard". What does "don't discard" mean? In your code it means "push onto another stack". I left the definition open to include an array or string.

The problem with your code is you require linelength. But it's a stack. You have no idea what linelength is, and don't need to. Just pop the characters and when the stack is empty, you're done.

[mrnutty]

I just looked at your code. It is identical to mine. You are counting the number of BS's and not pushing, whereas I count the number of BS's and "don't discard". What does "don't discard" mean? In your code it means "push onto another stack". I left the definition open to include an array or string.

The problem with your code is you require linelength. But it's a stack. You have no idea what linelength is, and don't need to. Just pop the characters and when the stack is empty, you're done.

What are you talking about? This code,

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

requires no length parameter, and requires no counter for backspace. It just checks if the sequence produced a backspace and if so, then pops the latest result added. In fact here is a live code.

[WaltP]

Sorry, I was looking at the wrong code. My bad.