CODEWITHSUNDEEP
cstack
AhmeDSeddiK
AhmeDSeddiK

Reputation: 13

Reversing a string using stack is not working for me

So i was writting a code to reverse a string using stack but the output always

seem wrong,anyone can tell whats the problem?!

when i write a string like hello the output should be "olleh" but its "ollo" any idea why that happening

the code is:

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

#define MAX_SIZE 101

void push(char );
void pop();
char Top();
void print();



char A[MAX_SIZE];
int top=-1;

void rev(int n)
{
    int i;
    for(i=0; i<n; i++){
        push(A[i]);
    }
    for(i=0; i<n; i++){
        A[i]=Top();
        pop();
    }

}

void main()
{

    printf("enter a string: ");
    gets(A);
    rev(strlen(A));
    printf("output= %s",A);
}

void push(char a)
{
    if (top == MAX_SIZE -1){
        printf("Error: stack overflow\n");
        return;
    }
    A[++top] = a;
}

void pop()
{
    if(top==-1){
      printf("Error: stack is empty\n");
        return;
    }
    top--;
}

char Top()
{
    return A[top];
}

void print()
{
    int i;
    printf("Stack: ");
    for(i=0;i<=top;i++){
        printf("%d ",A[i]);
    }
    printf("\n");
}

this is the output in screenshoot

the output

Upvotes: 1

Views: 75

Answers (3)

AndersK
AndersK

Reputation: 36082

The problem lies in that your pop function accesses the stack directly, the same one you are reading from so you are overwriting prematurely the contents

Example

ABC

push A, push B, push C, top is now 2

C  A[2]
B  A[1]
A  A[0]

so then you loop from 0 to 2

A[0] = Top() ;

now you overwrite A[0] 'A' with A[2] 'C' but you fail to store the previous value 'A'

the stack contents look like

A[2] C
A[1] B
A[0] C

Simplest is just to have a second array

char B[MAX_SIZE]

To traverse your stack do something like this

for (i = top, j = 0; i >= 0; --i)
{
  B[j++] = A[i];
}

(alt do a Pop function that returns the top value)

If you need to use only one array (for whatever academic reason) swap the values

for (i = top, j = 0; i >= 0; --i)
{
  if (i != j)
  {
    tmp = A[j];
    A[j] = A[i];
    A[i] = tmp;
  }
}

Upvotes: 0

D&#233;j&#224; vu
D&#233;j&#224; vu

Reputation: 28830

You're almost there!

First of all, don't use the dangerous gets(), use fgets instead

    fgets(A,MAX_SIZE,stdin);

then the reverse function is almost fine, but you are overwriting the same string, re-using (from half the string) chars you just copied from the tail (of stack / string).

Make the stack another array

char A[MAX_SIZE]; // input string
char S[MAX_SIZE]; // stack

in push / pop / top use only the stack, replace the A[...] with S[...]

Note: would be more elegant to use pop() without Top(), having pop return the char from the 'top' of the stack

char pop();

in rev()

for(i=0; i<n; i++){
    A[i] = pop();
}

pop() being

char pop() {
    if(top==-1){
       printf("Error: stack is empty\n");
       return 0;
    }
    return S[top--];
}

Upvotes: 1

zombie
zombie

Reputation: 5259

Because the push function is added to the same variable that the has the user input

Please add another variable then ‘char A[]’ for the stack

Further explanations: if you started reversing “hello” the push function would replace “h” with “o” and that’s what you see

Upvotes: 0

Related Questions