Understanding pointers and the stack in C

Question

I am writing a program that converts reverse polish notation input from the command line into infix notation using stacks. It does not solve the rpn notation it just prints out the output in infix notation. I have been having problems with the behavior of the stack. This program does no contain all the code functions (for simplicity). I omitted functions that print data and do input error checking, but they do not change the stack. So assuming that the correct data is entered for example 2 5 + then we can proceed to how this program should behave. The program works with three files the client, interface and implementation files. When input is entered from the command line the program loops the argv[] array and checks to see if the data is numeric and if it is then it pushes the numeric data on the created stack. If some of the data is not numeric then this implies we have an arithmetic operator character. When this happens then two values are popped off the stack and are merged together along with the arithmetic operator function. Then the merged result is pushed on the stack.Input of the form 4 5 + works just fine with correct output 4 + 5, as well as input of the form 9 8 + 6 - with output 9 + 8 - 6 works.

The problem occurs when this form 3 4 + 5 8 + + is typed in, I get as output 5 + 8 + 5 + 8, but the correct output should be 3 + 4 + 5 + 8. This might be due to the arguments that I pass into the push_stack function, which is a string that is merged before it is passed in. I am new to learning about pointers so perhaps someone can clarify for me what is going on in the stack. I included the three files with the functions and calls that modify the stack. Any help is appreciated

//stackfunctions.c file
#include "stackfunctions.h"

struct stackelements{
   SType items[STORAGE];
   int top;
};

pointer_stack stack_new(){
    pointer_stack stack = malloc(sizeof(struct stackelements));
    stack->top = -1; // empty initially
    return stack;
}

int stack_push(pointer_stack stack, Stype stack_value){
    if(stack->top == STORAGE - 1){
       return 0;
     }

     stack->top++;
     stack->items[stack->top] = stack_value;
     return 1;
}

Stype stack_pop(pointer_stack stack){
     if(stack->top == -1)
         abort();//
     stack->top--;
     return stack->items[stack->top+1];
}

void stack_print(pointer_stack stack){
    int i;
    printf("\n--------Top------------\n");

    for(i = stack->top; i >= 0; i--) {
        printf("   %s\n", stack->items[i]);
     }
     printf("---------Bottom----------\n");
}

The stackfunctions.h file

//stackfunctions.h file
#include<stdio.h>
#include<stdlib.h>

#define STORAGE 128

typedef struct stackelements *pointer_stack;

typedef char *Stype;

extern pointer_stack stack_new();

extern int stack_push(pointer_stack stack, Stype stack_value);

extern Stype stack_pop(pointer_stack stack);

extern void stack_print(pointer_stack stack);

Main program file

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

int main(int argc, char *argv[]){

    int i,j;
    float x = 0;
    char *operator[1], *point_b[1], *point_a[1];
    char result[100], a[30], b[30], op[3];

    pointer_stack stackP;

    stackP = stack_new(); // Create new stack

    // Loop through command line argument input

    for(i=1; i < argc; i++){     
        // Check to see if input is numeric.
        if(sscanf(argv[i], " %f ", &x)){
            stack_push(stackP, argv[i]); // If input is numeric push them into stack.

        else{ // Input is an operator, then we must

            operator[0] = argv[i];

            //Pop two items off stack

            point_b[0] = stack_pop(stackP);

            // create strings from pointer returned by atack_pop function

            memcpy(b, point_b[0] , strlen(point_b[0])+1);

            point_a[0] = stack_pop(stackP);

            memcpy(a, point_a[0] , strlen(point_a[0])+1);

            memcpy(op, operator[0] , strlen(operator[0])+1);

            // The we have to merge the popped off values and push the new 
            // result back on stack.

            sprintf(result, "%s %s %s", a, op, b);

            stack_push(stackP, result);

            stack_print(stackP); // Function that prints the stack, function
                                 // not included in other files, but it only
                                 // prints out the stackP pointer values. I use this
                                 // to check the output.

     }// close else

  }// close for loop

  free(stackP);

  return 0;
}

Answer 1

You never initialize the operator array. So, what did you expect to copy from operator[0] by your memcpy calls is completely unclear. How did you expect this to work, if the operator[0] value you use contains uninitialized garbage? The fact that your code produces the result you describe actually indicates that the code you posted is not real. In your real code you probably remembered to give operator[0] a meaningful value.

You push a pointer to the local result array into the stack. And then you reuse the result array. This will obviously "change" what you previously pushed into the stack. This is the actual reason for the incorrect result you described.

Also, function sscanf can return a non-zero EOF value in case of early matching failure. This will not work properly with your if (sscanf(... condition. It will assume that a number was read, while in reality it wasn't.

There are many other "weird" things in the code that are not necessarily errors, but are worth mentioning anyway.

Why does sscanf format contain extra spaces at the beginning and at the end? Why are operator, point_b, point_a declared as arrays (of 1 element each)? What is the point of "manually" implementing strcpy functionality through a strlen-and-memcpy combination?

Answer 2

It looks like you're clobbering your storage (result).

You're storing results into result and from there you push it onto your stack. Fine. But you're only saving a pointer to result. After the first argument with 3 4 +, result should have 3 + 4. However, when you unwrap the next argument, you turn 5 8 + into result. But, because you only have one result array, you end overwriting the 3 + 4 result you already had.

Instead, you're might want to allocate space each time you push onto the stack and free that memory when you pop.