Trying to convert reverse polish notation to infix using an stack of strings, running into a small error and I don't know what's causing it

Question

I've got a string stack implemented and I'm trying to convert rpn to infix using it. This is how the stack should look as the infix function works, for example if I entered 2 3 + 5 - 8 * :

2             //push 2
2,3           //push 3
(2+3)         //reach operator, pop 2 and 3, format it, put result back on the stack
(2+3),5       //push 5
((2+3)-5)     //reach operator, pop (2+3) and 5, format it, put result back
((2+3)-5),8   //push 8
(((2+3)-5)*8) //reach operator, pop ((2+3)-5) and 8, format, put result back

Sadly, this is not how the program has been working for me, and I think its something technical, not my algorithm. When entering "2 5 A", it works, giving a result of "(2+5)". Trying "40 50 A", I get "(40+50)". However, when trying "50 100 A" I get "(+)". Longer expressions like "1 2 A 3 S" also gives me just "(-)". I just can't seem to figure out what's causing this. Please feel free to give a jab at it. Here is my code:

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <unistd.h>


/*options to later implement (-e for evaluate, -c for infix conversion, -g for mock assembly */
#define OP_EVAL "-e"
#define OP_INFX "-c"
#define OP_GENI "-g"

/* begin stack of strings implementation */
struct stack_entry {
  char *data;
  struct stack_entry *next;
};

struct stack_t
{
  struct stack_entry *head;
  size_t stackSize;  
};

struct stack_t *newStack(void)
{
  struct stack_t *stack = malloc(sizeof *stack);
  if (stack)
    {
      stack->head = NULL;
      stack->stackSize = 0;
    }
  return stack;
}

char *copyString(char *str)
{
  char *tmp = malloc(strlen(str) + 1);
  if (tmp)
    strcpy(tmp, str);
  return tmp;
}

void push(struct stack_t *theStack, char *value)
{
  struct stack_entry *entry = malloc(sizeof *entry); 
  if (entry)
    {
      entry->data = copyString(value);
      entry->next = theStack->head;
      theStack->head = entry;
      theStack->stackSize++;
    }
  else
    {
      printf("FAILURE\n");
    }
}

char *top(struct stack_t *theStack)
{
  if (theStack && theStack->head)
    return theStack->head->data;
  else
    return NULL;
}

void pop(struct stack_t *theStack)
{
  if (theStack->head != NULL)
    {
      struct stack_entry *tmp = theStack->head;
      theStack->head = theStack->head->next;
      free(tmp->data);
      free(tmp);
      theStack->stackSize--;
    }
}

/*end stack of strings implementation */


/*begin argument handling for -c, -e and -g */
enum method
{
  EVAL,
  INFX,
  GENI
};

int 
is_option(const char *str)
{
  return (strcmp(str, OP_EVAL) == 0) ||
         (strcmp(str, OP_INFX) == 0) ||
         (strcmp(str, OP_GENI) == 0);
}

enum method
manip_method(const char *arg)
{
  if (strcmp(arg, OP_EVAL) == 0)
    return EVAL;
  else if (strcmp(arg, OP_INFX) == 0)
    return INFX;
  else if (strcmp(arg, OP_GENI) == 0)
    return GENI;
  else
    return 0;
}
/* end of argument handling code (again, not even being used yet) */

/* gets operator, converts it, if not A, S, X, D, or M returns NULL */
char*
get_oper(char *op){
  if(strcmp(op, "A") == 0)
    return "+";
  if(strcmp(op, "S") == 0)
    return "-";
  if(strcmp(op, "X") == 0)
    return "*";
  if(strcmp(op, "D") == 0)
    return "\\";
  if(strcmp(op, "M") == 0)
    return "%";
  else
    return NULL;
}


/* formats an infix expression */
char* 
formats(char *s1, char *s2, char* op){

  int length = strlen(s1) + strlen(s2) + strlen(op) + 3;
  char *buf = malloc(length);
  strcpy(buf, "(");
  strcat(buf, s2);
  strcat(buf, op);
  strcat(buf, s1);
  strcat(buf, ")");
  return buf;

}

/* 1) reads tokens and puts them on stack 
   2) when operator is reached, pops two elements off
      the stack and formats it, then pushes the result onto the stack
   3) after the loop ends, there should only be one element left on the
      stack: the final infix expression */
char*
infix(int argc, char *argv[], int x){
  int i;
  char *format, *result, *s1, *s2, *op;
  struct stack_t *stack = newStack();
  for(i = x; i < argc; i++){
    if(!get_oper(argv[i])){
      push(stack, argv[i]);
    } else {
      s1 = top(stack);
      pop(stack);
      s2 = top(stack);
      pop(stack);
      op = get_oper(argv[i]);
      format = formats(s1, s2, op);
      push(stack, format);
    }
  }

  result = top(stack);
  pop(stack);
  return result;
}


int
main(int argc, char *argv[])
{
  char *result;
  enum method method;
  int x;
  if (argc >= 4){
    if (is_option(argv[1])){
      if (argc < 5){
    printf("not a valid calculatable expression, exiting now...\n");
    exit (EXIT_FAILURE);
      }
      x = 2;
      method = manip_method(argv[1]);
    }
    else {
      x = 1;
      method = EVAL;
    }
  } else {
    printf("need option and or a valid reverse polish notation expression, exiting now...\n");
    exit (EXIT_FAILURE);
  }

  result = infix(argc, argv, x);
  printf("result: %s\n", result);


  exit (EXIT_SUCCESS);

}

Edit: Here are some more examples of the programs behavior

mesquite$ rpcalc 1 5 A
result: (1+5)
mesquite$ rpcalc 1 100 S
result: (1-100)
mesquite$ rpcalc 1 2 A 3 D
result: (\)
mesquite$ rpcalc 10 100 M
result: (%)

Answer 1

Bluepixy has it: You free the data associated with the stack when you pop off elements, so this:

s1 = top(stack);    // return handle to topmost item
pop(stack);         // invalidate that handle

is a recipe for disaster, especially since you malloc in formats, which is likely to give you a handle to recetly freed memory. Your string concatenation might have the same source and destination buffers.

So remove the deallocation of the data, free(tmp->data), from pop and delegate it to the caller:

s1 = top(stack);
pop(stack);
if (s1 == NULL) exit(1);       //Stack underflow

s2 = top(stack);
pop(stack);
if (s2 == NULL) exit(1);       //Stack underflow

op = get_oper(argv[i]);
format = formats(s1, s2, op);
free(s1);
free(s2);
push(stack, format);

Of course, you must also free the final result:

result = infix(argc, argv, x);
printf("result: %s\n", result);
free(result);

Your current implementation doesn't guard against malformed expressions (e.g. "A 2 3", "1 2 A 3", "12 A 44"). These occur with stack underflow (which I've tried to repeir very crudely above) or when there is more than one item on the stack after procesing the RN expression.

You have mentioned a BST in a comment, although I think you mean an AST. It is probably a good idea to create a syntax tree from the RPN expression first. With that representation it is easy to generate infix notation, evaluate the expression and generate assembly.

That shouldn't be too difficult, because your formats function already creates a tree-like structure - left node, operator, right node - where the child nodes or strings max have further subexpressions.