reversing a paragraph using stack in c

arsenal_729
arsenal_729 used Ask the Experts™
on
hi, i'd like to  reverse each line in stdin and reverse the order of lines in each ``paragraph''. Each paragraph must be reversed by pushing structs containing line numbers and stacks of characters onto a stack and later popping them off and printing them
Input Output
line 1. 2:.2 enil
line 2. 1:.1 enil
   
para 2. 4:.2 arap
   
para 3 7:2l3p
p313    6:313p

that's the interface
Stack:
the C type which will be used to represent stacks.
extern Stack stack_init(size_t el_size); given the size of the elements, an empty stack is returned.
extern Stack stack_push(Stack s, void *el_ptr);given a stack and a pointer to a new element, a new stack is returned with the new element pushed on.
extern Stack stack_pop(Stack s);given a stack, the top element is removed and the resulting stack is returned.
extern void stack_top(Stack s, void *el_ptr);given a stack and the address of an element, the top of the stack is copied to the element.
extern int stack_is_empty(Stack s);given a stack, returns 1 if the stack is empty and 0 otherwise
extern void stack_free(Stack s);given a stack, reclaims the memory used by the stack

i 'm really stuck how to write that ..can anyone guide me how to write that from beginning (code is not necessary)

i create a struct of stack ..but i think it's not gonna work

typedef struct head_Node
{
  int  elemsize;
  struct paranode *Next;
}Stack;

struct paranode
{
   int parasize;
   struct paranode *next;
}
sorry, i just have no idea....thanks in advance..
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Top Expert 2006

Commented:
1. home work question so no code

as far as hints go

1. to reverse a line

push each character on the stack
when you encounter a '.' , that means you have encountered end of line ...
so pop and print the contents of the stack and your line is reversed

2. to reverse a paragrpah ( reverse the ordering of lines )
push beginning of each line ( it will be location of '.' + 1 ) on to the stack
as soon as you get a '\n' (newline character) it is the end of the paragraph
pop the pointers to lines from the stack and display them .... ordering of line is reversed

what you need to do now is figure out how to use them together

you may need different stack for reversing a line and reversing paragraphs

ideal way to approach this problem would be to figure out how you want to organize your data ....
i.e. decide upon your data structures

next break down your problem into smaller parts ( like above ) and then join them together ...
have a clear picture of the solution that you are trying for

Author

Commented:
thanks for your advice...
but i still can't work it figure out how to reverse a paragraph, that's my code, and the main problem is i must use the interface that i mentioned...and i need to make the sake has no limit...

#include <stdio.h>
#include <stdlib.h>
#include "string.h"

#define MAX_STACK_SIZE 100

typedef enum {FALSE = 0, TRUE = 1,} BOOL;

struct Node
{
int  Data;
struct Node *Next;
};

struct Node *StackTop = 0;

void StackPush(int item);
int StackPop(void);
BOOL StackEmpty(void);

int main(void)
{
   char c,sentence[80];
   int i=0;
   gets(sentence);
   for ( i = 0; i < strlen(sentence); i++ )
{
 StackPush ( sentence[i] );
}

while( StackEmpty() == FALSE)
{
 printf("%c",StackPop());
}
               printf("\n\n");
return 0;
}

void StackPush(int item)
{
struct Node *p;

p = (struct Node *)malloc(sizeof (struct Node));

if ( p == 0 )
{
 printf("Stack Full \n");
 return;
}

p->Next  = StackTop;
p->Data  = item;
StackTop = p;
}



int StackPop(void)
{
struct Node *p;
int Value;

if ( StackEmpty() == TRUE )
{
 printf("Stack is Empty\n");
 return 0;
}

Value  = StackTop->Data;
p   = StackTop;
StackTop = StackTop ->Next;

free(p);
return Value;
}

BOOL StackEmpty(void)
{
if( StackTop == 0 )
 return TRUE;

return FALSE;
}
Top Expert 2006

Commented:
>>and i need to make the sake has no limit...

you can do it in two ways ...
1. implement stack as link list ... you can keep on allocating memory and adding nodes as and when required
2. create stack using malloc and increase its size at run time using realloc

>>i still can't work it figure out how to reverse a paragraph,

suppose you have following paragraph:

"this is a pragraph. it has more than one lines. all lines end with a full stop. full stop is a punctuation mark. punctuation marks are an important part of grammar."

if in your stack, you store address of first character of each line, your stack would look like

address of 'p' of punctuation                           -------------------------- top of stack
address of 'f' of full                          
address of 'a' of all
address of 'i' of it
address of 't' of this

all you need to do is pop the address from the stack and display the contents until next full stop in reverse fashion

Author

Commented:
thanks
but i' m not familier with pointers and malloc,
typedef struct Node{
   char  Data;
   struct Node *Next;
}StackNode;

typedef StackNode stake;
typedef StackNode *Stack;

main()
{
 Stack s;

...

...
}
also i don;t know how to use realloc...thanks for your patient..
Top Expert 2006

Commented:
If you are not familiar with pointers or malloc, then it wont be possible to provide an expanding stack ... your best bet will be to allocate a big enough stack and hope that it never overflows

If pointers have not yet been covered in your class then its fine but if they have been then I would suggest you to seriously take up a book and read them ... they are one of the most useful things in C

just noticed, you are using pointers in your data structures >>struct Node *Next;

and you say that you are not familiar !!!!

Author

Commented:
>> implement stack as link list ... you can keep on allocating memory and adding nodes as and when required

i don;t know how to implement it, so i look up the book, there's a similar example to reverse a set of interger using stack, so i copied it...but i'm not sure...how to..allocating memory in my program...

Author

Commented:
i'm not sure whether i'm doing the right thing in this program , cosi i 'm totally lost
Top Expert 2006

Commented:
1. for allocating memoy, use malloc ... refer to the man page ( on linux ) or help page ( on win ) for more info on this function ... its pretty simple ....

2. copying wont help :-)


============================
 void *malloc(size_t size);

 malloc() allocates size bytes and returns a pointer to the allocated memory.  The memory is not cleared.

Author

Commented:
but i have already use
p = (struct Node *)malloc(sizeof (struct Node)); in the push
Top Expert 2006

Commented:
ok then tell me where are you stuck ???

what is the overall design which you have in mind ?

Author

Commented:
typedef struct Node{
   char  Data;
   struct Node *Next;
}StackNode;

typedef StackNode *Stack;
is that right?
the thing is i really don't know how to implement the interface...like ..void stack_top(Stack s, void *el_ptr);
why use a pointer to element,i don't know what should i pass to the function.

the overall design is somethin like..
1.intialise the stack
2.read the characters from the beginners until encounter '.'
3. pop them into the stack...
4.keep reading from the '.' to another '.' repeating step 3.
5 if encounting a '\n'  pop the top from the stack until it is empty,
6.repeating the step 1-5 after the empty line...

thanks very much, could u tell me step by step....i'm lost

Author

Commented:
step 2 .3..read the characters from the beginning and PUSH them into stack, until encounter an empty line
Hi arsenal_729,

All of the help that you're received so far has been good advice, but there is a simpler solution.  Save the incoming lines of text and let C manage the stack through recursion.  Once you've mastered this it will be a lot easier to make the jump to managing your own recursive stack.  Also, used the C managed stack to reverse the current line.


main ()
{
  GetLines();
}

GetLines()
{
  char *Line;

//  Read a line from stdin into a temporary buffer.
//  if data was input,  malloc() enough memory to *Line to hold the string.  Copy the string to *Line.  Call GetLines();.
//  if no data was input, return;

//  Reverse the current line:

  ReverseLine (Line);
  fprintf (stdout, "\r\n");  /* DOS/Windows newline  */
}

ReverseLine (char *Line)
{
  if (*Line)
    ReverseLine (Line+1)
  fputc (*Line, stdout);
}


This is an easy program to implement.  Once you have it working you can replace the recursion with your own management.

Kent
Top Expert 2006

Commented:
void stack_top(Stack s, void *el_ptr);
given a stack and the address of an element, the top of the stack is copied to the element.

>>i don't know what should i pass to the function.

read the purpose of the function carefully, you will get the topmost element placed in the address which you pass.

according to your data structures you have a stack of chars ...

so in your calling function you would like to pass address of a char to this function and get the topmost value in that char ...

so, you can place a call like

char top_value;
...
stack_top ( s, (void *)&top_value );
...
the funciton stack_top will place the topmost element in top_value which you can then display or use

I must say that you have come up with a very good design ... step 4 seems redundant ... just take care not to print last '.' ( first chatacter on reversing ) and must print a trailing '.' after reversing entire paragraph
Top Expert 2006

Commented:
I agree Kent that it is easier using recursion, but this is a homework assignment ... he has an interface to implement and use :-)
Hi sunnycoder,

I recognized the smell of homework  :)  so instead of "giving up the answer" I suggested that he first write the program to let the language take care of the recursion, then move on to utilizing his own stack.

Recursion can be such a tough concept to grasp that if he's not 100% comfortable with it, then building and manipulating his own stack will yield LOTS of crashes, dumps, and endless loops that can be tough to debug.


Kent
Top Expert 2006

Commented:
well said ... things do seem trivial once you know them ;)

I feel a comment about marriage coming on....

Nahh.... I value my teeth.   ;)

Hi arsenal_729,

A word (or 438) about stacks.

If you're always going to be putting the same sized item on the stack you have unlimited flexibility in defining how you handle allocating and freeing space on the stack.  Basically, you always allocate or free a fixed length block so the only concerns that you'll have is stack overflow (allocating more space than the stack has free) and underflow (freeing space that was never allocated).

If there's even the slightest possibility that you could put items of different size on the stack then you need to "set it up right".

As far as stack management is concerned, the stack will contain two types of data.  User data (the objects that the stack is saving for the program) and stack control information (basically, how big is this block).  Here's the basic steps:

1)  Assume that you allocate space on the stack from low address to high (most common).

2)  The stack has a finite amount of space.  Each item on the stack is limited in length by the amount of space available on the stack, not the stack length.  Decide how big you're going to allow each item to be.  16-bit systems limited the size of any single item to 65535 (2^16-1) because they used a 16-bit value to store the length of the object.  16 bits should suffice for this project.  If you're not comfortable with this, use 32 bits.  If you're on a 32-bit system, use an *int*.

Some stack implementations allow you to relocate the stack.  Be warned that this can be very dangerous and tough to implement.  It also adds overhead.

3)  Allocate your stack.  1MB should be more than enough for this project.

4)  When you place items on the stack, you reserve space on the stack for the items, then save the length of the object on the stack.  Note that the length is ALWAYS the last thing you save.  This way the only position within the stack that you need to keep is the current position.  When you pop the stack, the pointer gets regressed to the previous length pointer.  Here's what the stack will look like

<0000><Data 1><Length 1><Data 2><Length 2>....<Data N><Length N>

Each Length value is the length of the data object PLUS the length of the length indicator.  Put simply, if you reserve 8 bytes on the stack and are using a 32-bit integer for the length field, the value in the length field with be 12 (8+4).  This allows you to pop the stack by subtracting the current length from the stack pointer.

Note that stack started with a Length indicator of 0.  This allows you to test for underflow (popping more than you've pushed) by testing for a length of zero whenever you pop().

There are a lot more details that you'll discover.  But you actually do need to discover some of them.  In the meantime, this should be a good start.

Kent


Author

Commented:
sorry kdo...
how can i do that, my course hasn;t covered fgets....
i guess it's something  like.
struct Node
{
  int  buff[80];
  struct Node *Next;
};
int count = 0;

struct node *start = (struct node *)malloc(sizeof(struct node));
struct node *end = start;

while(1){
     end->next = (struct node *) malloc(sizeof(struct node));
     end=end ->next ;
     Line = end->buffer;
     fgets(Line,80,stdin);
     count +=strlen(Line);
     if (LINE[strlen(LINE)-1] == '\n') break;
}
end->next = NULL;

my friend told me that, but he wasn;t sure...
i don;t know how it works..
could u direct me....
and what else should i do in order to write that program,...it 's a puzzing interface for me...thanks

Author

Commented:
sorry guys....i'm stuck, i'd would like to do it from scratch...'cos i don't really understand the basic stuff behind that...( i forgot most of all) to be honest, i just modify the code from the textbook....
.i'll try to understand all the basic stuff tonight, i still wanna do it , i still wanna learn..hope u guys can guide me through. and treat me like a new programmer...i must say thanks to u guys...

You're being asked to emulate a stack and haven't even covered basic I/O?  Who's teaching your class -- Captain Kangaroo?


Reading with fgets() is pretty simple.  The code that you've posted does it quite nicely.  However, you do need to test that you've reached the end of the data.

Using normal C practices, this function will recursively read lines from stdin until EOF is encountered.

ReadLines ()
{
  char Buffer[80];

  fgets (Buffer, 80, stdin);
  if (feof (stdin))
    return;
  ReadLines ();
}


Using your own stack management, it would look something like this:

ReadLines ()
{
  char Buffer[80];

  while (1)
  {
    fgets (Buffer, 80, stdin);
    if (feof (stdin))
      break;
    PushStringOntoStack (Buffer);
  }
}



Kent

Author

Commented:
thanks for your post, i'll check it tomorrow..
that's the spec..

You are to write a main() function in reverse.c which uses your stack implementation (see below) to reverse each line in stdin and reverse the order of lines in each ``paragraph''. A paragraph is a consecutive sequence of non-empty lines terminated by an empty line (a line with no characters except the newline) or end of file. Each non-empty line of the output should also contain the original number of the line. The table below gives an example:

Input Output
line 1. 2:.2 enil
line 2. 1:.1 enil
   
para 2. 4:.2 arap
   
para 3 7:2l3p
p3l2 6:3 arap

Each line must be reversed by pushing the characters onto a stack as they are read and later popping them off and writing them. Each paragraph must be reversed by pushing structs containing line numbers and stacks of characters onto a stack and later popping them off and printing them. You should attempt to make your code simple and elegant, avoiding data structures and operations other than those associated with the stacks as much as possible. A sample stack implementation will be provided. Your reverse program should work with this implementation and your stack implementation.

The stack interface
The interface is designed so as to allow multiple stacks to be defined and manipulated in a flexible way. The stack interface, defined in file stack.h, consists of the following type and set of functions:
Stack:
the C type which will be used to represent stacks.
stack_init:
given the size of the elements, an empty stack is returned.
stack_push:
given a stack and a pointer to a new element, a new stack is returned with the new element pushed on.
stack_pop:
given a stack, the top element is removed and the resulting stack is returned.
stack_top:
given a stack and the address of an element, the top of the stack is copied to the element.
stack_is_empty:
given a stack, returns 1 if the stack is empty and 0 otherwise.
stack_free:
given a stack, reclaims the memory used by the stack.

Except for stack_is_empty and stack_top, stacks passed to these functions should not be re-used (the stacks returned should be used instead). Your code must not impose any limit on the number of stacks, the number of elements in a stack or the size of elements. Your code should include a well documented version of the interface.

typedef void Stack(I need to create this)
Stack stack_init(size_t el_size);
Stack stack_push(Stack s, void *el_ptr);
Stack stack_pop(Stack s);
void stack_top(Stack s, void *el_ptr);
int stack_is_empty(Stack s);
extern void stack_free(Stack s);

This is pretty easy to do if you take it one step at a time.  It's not really that much code, either.

According to the rules that you've posted, you won't have A stack, you'll likely have several.  It is probably practical to have a stack for each autonomous function.  In this application you must read the last character in the last line of a paragraph before you begin reversing the data.  This suggests that you might have a stack to hold all the lines in a paragraph, and another to hold the characters in a line as you reverse it.

So you'll need a basic structure that allows you to manage the stack.  Here's a prototype that will get you started.  This structure will allow you to manage a stack where objects can be any length.  You might want to restrict the stack so that each entry is the same size.  (You'll decide how best to manage this as you get more code written.)

typedef struct Stack
{
  int Length;   /*  number of bytes in this stack  */
  int Position; /*  current position in the stack  */
  void *Data;
};


Here's the steps that I would take:

1)  Write the first function -- stack_init().  It's pretty simple.  :)
2)  Write stack_is_empty().  Also pretty simple.
3)  Write stack_free ().  (Two steps here, not one!)
4)  Write available_stack_space().  It's not on your list, but you'll need the functionality.  Also pretty easy.
5)  Write stack_push ().
6)  Write stack_top ().
7)  Write stack_pop ().

None of these functions are more than just a few lines of code and are pretty easy.

You're now ready to test your stack!  And just because we need a pun here, be careful or you'll blow your stack!  [apologizes....]


Kent

Author

Commented:
sorry, kdo, i still don't know what to do with this:
typedef struct Stack
{
 int Length;  
 int Position;
 void *Data;
};
what about :
typedef struct STACKnode* link;
struct STACKnode { Item item; link next; };
static link head;
link NEW(Item item, link next)      
  { link x = malloc(sizeof *x);
    x->item = item; x->next = next;    
    return x;                        
  }                                  
void STACKinit(int el_size)
  { head = NULL; }
main(){
 char buff[80];
 Stackinit(buff);
....

Author

Commented:
what about, is that right, and if not, whrong's wrong, could u tell me the basic...
#define size_t char

struct Stack
{
 int Length;
 int Position;
 void *Data; //why this is void not char???sorry....again..i'm a fool
};
typedef struct Stack *link;
static link head;

Stack stack_init(size_t el_size)
{
  head == NULL;
}

int main(){
   char buff[80];
   stack_init(buff);
   ..}
Hi arsenal_719,

Holiday weekend.  I'm not around my PC much.

The "void" in struct Stack could just as easily be a "char" in this case.  Void is a more generic form that you'd use if the data type could vary.  Since you're only putting strings on your stack, "char" is fine.

You're really lost, huh?

stack_init () is supposed to initialize the stack.  Hint:  Setting "head" to NULL isn't initializing the stack -- it's destroying  it.

Kent

Author

Commented:
so what should i do with the init, why not setting the top to NULL, or oi should malloc the size of the element ?
sorry i'll submit it in 12 hrs, i still get no idea..

stack_init() should set up the stack so that the other functions can use it.  It should create and EMPTY stack, not a NULL stack.  Basically, it must leave the stack in a state that the other functions can operate on the stack.

/* If your stack is going to be a linked list, do something like this.  Note that it has forward and backward pointers so that you can move up and down stack with ease.  When looking at any node in the stack, (previous == NULL) indicates the top of the stack.  When (next == NULL) you are at the bottom of the stack which is also usually the only node that is currently being operated upon  */

STACK *stack_init ()
{
  STACK *ptr;

  ptr = (STACK *) malloc (sizeof STACK);
  ptr->previous = NULL;
  ptr->next = NULL;
  ptr->length = 0;
  ptr->position = 0;

  return ptr;
}

/*  If you're going to use block memory and place items directly on the stack, you'll want something like this  */

STACK *stack_init ()
{
  STACK  *ptr;

  ptr = (STACK *) malloc (sizeof (stack));
  ptr->Data = (void *) malloc (INITIAL_STACK_SIZE);
  ptr->Position = 0;
  ptr->Length =  INITIAL_STACK_SIZE;
  *((int)ptr->data) = (int)0;   // Put a zero on the top of the stack.
  return (ptr);
}


It sounds like you're in an advanced class and haven't completed all of the pre-reqs.  Good Luck.

Kent

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial