Thread: First Use of a Stack

Hey all,

I've been working on a project that converts infix arithmetic into postfix arithmetic and then determines the value. I understand how stacks work, but I've never created them in a program before. I'm currently using 3 c files. One with a main, one with the infix to postfix operations, and one that has the stack information (This was given to me).

I'm wanting to know how I can add something to the stack. I'm confused because it shows it should send a value of type stack.. How am I supposed to define that?

Thanks so much for any help!!

I bolded the specific areas I'm trying to solve to get started on it.

------------------------------------------------------
Here is the stack file:

Code:

/*
 * This is a linked list implementation of stack interface.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "stack.h"

/* function to initialize a new stack variable */
void stackInit(stack *stkPtr)
{
        stkPtr->top = NULL;
}

/* function to free the memory associated with the stack */
void stackDestroy(stack *stkPtr)
{
        stkNode *temp, *temp2;

        temp = stkPtr->top;
        while (temp != NULL) {
                temp2 = temp->next;
                free(temp);
                temp = temp2;
        }

        stkPtr->top = NULL;
}

/* function to add an element to the top of the stack */
void stackPush(stack *stkPtr, stkElement element)
{
        stkNode *newNode;

        /* allocate a new node to hold element pushed */
        newNode = malloc(sizeof(stkNode));

        if (newNode == NULL) {
                fprintf(stderr, "Insufficient memory to push element on stack.\n");
                exit(1);
        }

        /* put information in node */
        newNode->element = element;

        /* link new top node to old top node */
        newNode->next = stkPtr->top;

        /* make the new node the top node in stack */
        stkPtr->top = newNode;
}

/* function that removes the element from the top of the stack */
stkElement stackPop(stack *stkPtr)
{
        if (stackIsEmpty(stkPtr)) {
                fprintf(stderr, "Can't pop element from stack: stack is empty.\n");
                exit(1);

        }

        stkElement element = (stkPtr->top)->element;

        stkNode *temp = stkPtr->top;
        stkPtr->top = (stkPtr->top)->next;
        free(temp);

        return element;
}

/* function that returns a true value if the stack is empty */
bool stackIsEmpty(stack *stkPtr)
{
        return stkPtr->top == NULL;
}

/* function that returns the number of elements in the stack */
int stackLength(stack *stkPtr)
{
        int count = 0;

        stkNode *temp = stkPtr->top;

        while (temp != NULL) {
                count++;
                temp = temp->next;
        }

        return count;
}

/* function that returns the top element in the stack without removing it */
stkElement stackPeek(stack *stkPtr)
{
        if (stackIsEmpty(stkPtr)) {
                fprintf(stderr, "Stack is empty - can't peek.\n");
                exit(1);
        }

        return (stkPtr->top)->element;
}

Here is the file that calls to the stack to add an element (adding is what I'm wanting to be able to do):

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "postfix.h"
#include "stack.h"

/* function to convert an infix to postfix */
char *infixToPostfix(char *infixStr)
{
        char *postfixStr = calloc(strlen(infixStr), sizeof(char));

        if (postfixStr == NULL)
        {
                //Memory could not be allocated
                fprintf(stderr, "Couldn't allocate memory\n");
                exit(EXIT_FAILURE);
        }

        char *token;
        const char delim[] = " ";

        token = strtok(infixStr, delim);
        while( token != NULL)
        {
                if(isOperand(token))
                {
                        strcat(postfixStr, token);
                }
                else if(isLeftParen(token))
                {
                        stackPush(<WHAT HERE?>, token);
                }
                else if(isOperator(token))
                        printf(" %s \n", token);

                token = strtok(NULL, " ");
        }

        return token;
}

/* function that returns true if the string is an operator */
bool isOperator(char *str)
{
        if((strcmp(str, "+") == 0) ||
                (strcmp(str, "-") == 0) ||
                (strcmp(str, "*") == 0) ||
                (strcmp(str, "/") == 0) ||
                (strcmp(str, "%") == 0) ||
                (strcmp(str, "^") == 0))
                return true;
        else
                return false;
}

/* function that returns true if the string is an operand/integer */
bool isOperand(char *str)
{
        if((strcmp(str, "0") == 0) ||
                (strcmp(str, "1") == 0) ||
                (strcmp(str, "2") == 0) ||
                (strcmp(str, "3") == 0) ||
                (strcmp(str, "4") == 0) ||
                (strcmp(str, "5") == 0) ||
                (strcmp(str, "6") == 0) ||
                (strcmp(str, "7") == 0) ||
                (strcmp(str, "8") == 0) ||
                (strcmp(str, "9") == 0))
                return true;
        else
                return false;
}

/* function that returns true if the string is a left parenthesis */
bool isLeftParen(char *str)
{
        if((strcmp(str, "(") == 0))
                return true;
        else
                return false;
}

/* function that returns true if the string is a right parenthesis */
bool isRightParen(char *str)
{
        if((strcmp(str, ")") == 0))
                return true;
        else
                return false;
}

Thank you for your response! The definitions are in the stack.h file. However, I'm not sure what values should be sent to stackPush through the stack and stkElement parameters. What should I have for those values?

Thank you!

Ok. I'm not sure how the element is supposed to be used either. I would assume that there needs to be some way to get the actual value on the stack, but I'm not sure how you can assign it to element.

Anyway, here is the stack.h file:

Code:

/*
 * This is an interface for a stack of strings.
 *
 */

#ifndef _STACK_H
#define _STACK_H

#include <stdbool.h>

typedef char * stkElement;

struct stkNode {
  stkElement element;
  struct stkNode *next;
};

typedef struct stkNode stkNode;

typedef struct {
  stkNode *top;
} stack;

/* function to initialize a new stack variable */
void stackInit(stack *stkPtr);

/* function to free the memory associated with the stack */
void stackDestroy(stack *stkPtr);

/* function to add an element to the top of the stack */
void stackPush(stack *stkPtr, stkElement element);

/* function that removes the element from the top of the stack */
stkElement stackPop(stack *stkPtr);

/* function that returns a true value if the stack is empty */
bool stackIsEmpty(stack *stkPtr);

/* function that returns the number of elements in the stack */
int stackLength(stack *stkPtr);

/* function that returns the top element in the stack without removing it */
stkElement stackPeek(stack *stkPtr);

#endif  /* _STACK_H */

Thanks again for your help!

I just tried with the snippet you recommended, and this is the error I got:

postfix.c: In function infixToPostfix:
postfix.c:42: warning: passing argument 2 of stackPush from incompatible pointer type
stack.c:33: note: expected stkElement but argument is of type char **

The third error continues to pop up even though I have element defined as stkElement... For some reason it says it is a char**

Thanks so much for your help! That works with a slight modification. Here is the code for anyone else who is curious. The infixToPostfix logic doesn't quite work yet, but the stack works.

Code:

/* function to convert an infix to postfix */
char *infixToPostfix(char *infixStr)
{
        char *postfixStr = calloc(strlen(infixStr), sizeof(char));
        stack stk;
        stackInit(&stk);
        stkNode node;

        if (postfixStr == NULL)
        {
                //Memory could not be allocated
                fprintf(stderr, "Couldn't allocate memory\n");
                exit(EXIT_FAILURE);
        }

        char *token;
        const char delim[] = " ";

        token = strtok(infixStr, delim);
        while( token != NULL)
        {
                if(isOperand(token))
                {
                        strcat(postfixStr, token);
                        strcat(postfixStr, " ");
                }
                else if(isLeftParen(token))
                {
                        node.element = token;
                        stackPush(&stk, node.element);
                }
                else if(isOperator(token))
                {
                        while((!stackIsEmpty(&stk)) && (stackPeek(&stk) != "("))
                        {
                                if(stackPrecedence(stackPeek(&stk)) >= inputPrecedence(token))
                                {
                                        strcat(postfixStr, stackPeek(&stk));
                                        stackPop(&stk);
                                        strcat(postfixStr, " ");
                                }
                                else
                                        break;
                        }
                        node.element = token;
                        stackPush(&stk, node.element);
                }
                else if(isRightParen(token))
                {
                        while((!stackIsEmpty(&stk)) && (stackPeek(&stk) != "("))
                        {
                                strcat(postfixStr, stackPeek(&stk));
                                stackPop(&stk);
                                strcat(postfixStr, " ");
                        }
                        if(!stackIsEmpty(&stk))
                                stackPop(&stk);
                }

                token = strtok(NULL, " ");
        }

        while(!stackIsEmpty(&stk))
        {
                if(stackPeek(&stk) != "(")
                {
                        strcat(postfixStr, stackPeek(&stk));
                        strcat(postfixStr, " ");
                }
                stackPop(&stk);
        }

        return postfixStr;
}