Converting prefix expressions to infix

Question

Here is my new working code. Man, working with strings in C is tedious and annoying. I had built the algorithm in short time, took hours figuring how to implement it properly in C. Tell me if there are more bugs or if some improvement is possible.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{
  char data[100];
  struct node *next;
}SNode;

typedef struct{
 int count;
 SNode *top;
}stack;

int isEmpty(stack *s){
  return (s->count==0);
 }

void push(stack *s,char x[]){
  SNode *temp = (SNode *)malloc(sizeof(SNode));
  strcpy(temp->data,x);
  temp->next = s->top;
  s->top=temp;
  s->count++;
  }

char * pop(stack *s){
     if(isEmpty(s)){
      return "-1";

     }
    SNode *temp = s->top;
    s->top = temp->next;
    static char a[10];
    strcpy(a,temp->data);
    free(temp);
    s->count--;
    return a;
  }


 int main(){
    stack *s = (stack *)malloc(sizeof(stack));
    s->count = 0;
    char a[100];
    printf("Enter prefix expression: ");
    gets(a);
    int i;
    for(i=strlen(a)-1;i>=0;i--){
    if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'){
       char s1[10], s2[10];
       strcpy(s1,pop(s));
       strcpy(s2, pop(s));
       char b1[10] ="(",b2[10]=")";
       strcat(b1,s1);
       char t[2]="\0";
       t[0]=a[i];
       strcat(b1,t);
       strcat(b1,s2);
       strcat(b1,b2);
       push(s,b1);
      }
     else if(isalpha(a[i])){
         char t[2] = "\0";
          t[0] = a[i];
          push(s,t);
     }
    }
    char *infix = pop(s);
    printf("Infix expression: %s",infix);
    return 0; 
     } 

Answer 1

malloc()

In general, malloc may fail, and will return NULL when that happens, you should deal with that.

The result of malloc does not have to be cast to the target type, additionally it is usually safer to use the target variable in the sizeof expression.

stack *s = malloc(sizeof *s); 
if (s == NULL) { // deal with it}

gets()

You have a buffer that is 100 chars wide, the long-deprecated gets() will just write over the end of the buffer, you should try and use fgets() e.g fgets(buffer, 100, stdin) or alternatively gets_s() if your compiler supports C11's optional Annex K.

Editing the string in place

Meaning changing the characters in the string without extra memory allocation. You're changing the string in place, this probably makes things much more complicated than they need to be. Using an input and an output string would clear things up. Using the pointer into the string rather than the string index might make things a little bit more readable as well. I don't think I would choose to edit the string in place unless I was forced to do it. Not shifting the string also makes it easier to visualize what's going on as you only have to move the index forward.

Accessing the string via an index

With char* buffer, buffer[i] and *buffer are equivalent; I'd probably trend more towards using the string pointer rather than the index, that might be a matter of taste.

Naming consistency

You have the node struct typedefed as SNode and the stack just typedefed as stack. It's easy to spot when someone is inconsistent, no matter if I agree with the style or not. Here there are two ways of how you define the struct and two ways (one capitalized, and the other not) of writing the typedef; stick to one way.

pop()

Popping an empty stack is a bug in most cases, if not you probably should treat it like a bug and assert on the empty stack. Returning \0 hides the fact that you tried to call pop on the empty stack making it harder to track down the bug

Warnings

isalpha() is defined in <ctype.h> which is not included

Bug

*+ab+cd is parsed as a + b * c + d and given operator precedence that is incorrect - the result should be (a + b) * (c + d).

Answer 2

Since your code relies on a max length of 100 you can reduce many code for your stack by using a simple array. A test for stack overflow must be added.

typedef struct {
    char *data[20];
    char **top;
} Stack;

int main() {
  Stack stack;
  stack.top = stack.data;
  ......

  // if you like..
  for(i=0; i<sizeof(stack.data)/sizeof(*stack.data); i++)
    if(stack.data[i]!=null) free(stack.data[i])
}

void push(Stack *s, char *t) {
    if(*s->top==null)
        *s->top = malloc(100);
    strcpy(*s->top, t);
    s->top++;
}
char *pop(Stack *s) {
    if(s->top > s->data) {
        s->top--;
        return *s->top;
    }
    return null;
}