# Converting prefix expressions to infix

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

• Not so fast ;-) I goes like that: You first write a title that states what your code does, instead of crying for help, then you write a nice description and explain what and how (perhaps even why) you did in your code. Mar 30, 2018 at 12:30
• You defintely have a bug in your conversion *+ab+cd should be (a+b)*(c+d) and not a + b * c + d Mar 30, 2018 at 13:11
• @HaraldScheirich no it is not a bug. you gave the input wrong. the correct input would be *(+ab)(+cd) Mar 30, 2018 at 13:18
• @Gameatro i disagree, look up a few references, *+ab+cd is equivalent to mult(add(a,b),add(c,d)) which comes out to (a + b) * (c + d). Prefix notation does not utilize parentheses en.wikipedia.org/wiki/Polish_notation Mar 30, 2018 at 13:27
• Whatever book you are reading for learning C, throw it away. It is too old. No sensible book recommends gets for anything. Mar 30, 2018 at 20:24

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

• i m working on the bug. for malloc, it wont fail unless ur ram is full. Mar 31, 2018 at 1:03
• well i worked out logic for the code to work the way you said. but i am having diff implementing it in c. how do i return an array in c. that is required for pop function. to return a string. Mar 31, 2018 at 5:36
• gets_s() is Visual Studio/Windows specific, a more common replacement is fgets() (from the POSIX standard). Mar 31, 2018 at 16:26
• @Gameatro You return a string by a pointer, to create a new string dynamically you will have to malloc it Mar 31, 2018 at 16:42
• @MartinR I amended the gets() section Mar 31, 2018 at 16:47

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