First Use of a Stack

This is a discussion on First Use of a Stack within the C Programming forums, part of the General Programming Boards category; Hey all, I've been working on a project that converts infix arithmetic into postfix arithmetic and then determines the value. ...

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    5

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

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,169
    You need to look in stack.h for the definition.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User
    Join Date
    Feb 2011
    Posts
    5
    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!

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,169
    It wants a pointer to a stack. So you probably have to do something like:
    Code:
    stack stk;
    stkInit(&stk);
    stkElement elem;  // No idea how to use this. What's stack.h look like?
    stkPush(&stk, &elem);
    If you understand what you're doing, you're not learning anything.

  5. #5
    Registered User
    Join Date
    Feb 2011
    Posts
    5
    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!

  6. #6
    Registered User
    Join Date
    Feb 2011
    Posts
    5
    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**

  7. #7
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,169
    Okay, so according to stack.h, stkElement is a char *. All you need to do is pass your string in then: stkPush(&stk, token);
    If you understand what you're doing, you're not learning anything.

  8. #8
    Registered User
    Join Date
    Feb 2011
    Posts
    5

    Solved

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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  2. infix evaluation using stack
    By lewissi in forum C++ Programming
    Replies: 0
    Last Post: 11-03-2005, 01:56 AM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 09:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 05:27 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21