Stack Linked List
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: Stack Linked List

  1. #1
    Join Date
    Nov 2000
    Location
    IL, U.S.A.
    Posts
    218

    Stack Linked List

    This is my current assignment
    1. Make a complete implementation in C++ of the class Stack ( a generic stack) using a forwardly linked
    ordered-list. Do NOT use arrays.
    2. Use this stack to convert an arithmetic expression in INFIX form with only single character identifiers
    of variables, left and right parentheses, operators (+, -, *, / ) to POSTFIX form. Input is an expression
    followed by a colon and a sequence of value assignments, terminated by a period.
    3. Use this example:
    X + ( Y + Z ) * A / B ? C * X : A=2, B=10, C=5, X=8, Y=6, Z=4.

    4. Completed project is due on Sept 5, 2001.
    5. First, create a generic stack using template and linked list. Test your stack using an array of integers.
    Then, test the algorithm of infix/postfix process using simple strings such as:
    a + ( b ? c * e + f / y )#
    a * b + ( c ? d / e )#
    When your algorithm is working properly, then use the provided string to test your program .

    6. Processing hints:
    a. Read an input character until # or :.
    1) If the current input symbol is an alphabet, write it to output.
    2) Else if the current input symbol is a left parenthesis ( ?(? ), push the current input symbol onto
    the stack.
    3) Else if the current input symbol is a right parenthesis ( ?)? ), then pop each symbol from the stack
    top and write it to output until a left parenthesis is popped. Then discard the matching left/right
    parentheses.
    4) Else If the current input symbol is an operator;
    i. If the stack is empty, then push the current symbol on the stack.
    ii. If the stack is not empty and the current symbol has higher precedence over the stacktop symbol,
    then push the current symbol on the stack.
    iii. If (stack is not empty and the current symbol has higher precedence over the stacktop symbol)
    a. While the stack top symbol has precedence greater or equal to the current symbol, pop it from the
    stack and write it to output.
    b. Upon exiting the while loop, then push the current symbol onto stack.
    5) At the end of input (input symbol is # or : ), pop and output all operators remained on stack.
    6) Remember (*, /) have higher precedence over (+, -).
    Part II. Read the assignment symbol = value and create a symbol table ( arrays of pairs of symbol and
    value). Print your symbol table. The symbol table consists of two columns.: the first column lists terms
    and the second column lists the matching values (parallel array).

    Part III. Apply the values from the table to your POSTFIX and print the output.
    Processing: Read a symbol. If it is an identifier, look up its value in the symbol table and push
    the value onto a stack of numbers.

    I have a stack program that changes Infix to postfix. My question is, What is the Linked list supose
    to do in this problem? I can't see what it is supose to do in this programming problem? What is a stack
    linked list used for? Can anyone give me some insight on how the design should work or could work? Not
    code just can you tell me what would do what?



  2. #2
    Join Date
    Feb 2001
    Location
    Virginia, USA
    Posts
    170

    Re: Stack Linked List

    You are supposed to implement the STACK data structure using what you've been taught about a linked list. You must first understand how a stack works, and then understand how a linked list works, and then use the linked list methodology to implement a stack.

    That means that you create a struct which contains all the data you need for one element. It should also contain a pointer to a struct of the same type as itself. You start out with one instance of this struct. As you add elements to this linked list, you dynamically allocate memory for new elements. As you do this, you assign the NEXT pointer to the newly allocated memory. This is how the linked list grows when you PUSH new elements onto the stack.

    Now, because it is a stack, there are only two operations you can perform: push and pop. I already explained push. Pop is even easier. All you need to do is go to the penultimate element, delete the memory pointed to by NEXT, and then set NEXT equal to NULL.

    The hard part comes when you have to figure out how to make the darned thing do infix or postfix arithmetic.


  3. #3
    Join Date
    Feb 2001
    Location
    Virginia, USA
    Posts
    167

    Re: Stack Linked List

    You are supposed to implement the STACK data structure using what you've been taught about a linked list. You must first understand how a stack works, and then understand how a linked list works, and then use the linked list methodology to implement a stack.

    That means that you create a struct which contains all the data you need for one element. It should also contain a pointer to a struct of the same type as itself. You start out with one instance of this struct. As you add elements to this linked list, you dynamically allocate memory for new elements. As you do this, you assign the NEXT pointer to the newly allocated memory. This is how the linked list grows when you PUSH new elements onto the stack.

    Now, because it is a stack, there are only two operations you can perform: push and pop. I already explained push. Pop is even easier. All you need to do is go to the penultimate element, delete the memory pointed to by NEXT, and then set NEXT equal to NULL.

    The hard part comes when you have to figure out how to make the darned thing do infix or postfix arithmetic.


  4. #4
    Join Date
    Nov 2000
    Location
    IL, U.S.A.
    Posts
    218

    Re: Stack Linked List

    So I have this for my Linked List but I guess I only need pop and push. I thought the question is asking me to change infix to postfix with the stack, not the linked list.

    //Forward Incomplete Declaration
    struct NodeType;

    //Definition that NodePtr points to a type of NodeType
    typedef NodeType* NodePtr;

    //Complete Declaration
    struct NodeType {
    char data; // Pointer to person's name
    NodePtr link; // Link Member
    };




    class List
    {
    public:
    List(); //Constructor
    ~List(); //Destructor
    bool Isempty() const; //Checks to see if node is empty
    void InsertAfter(char data1);//Inserts the correct node value
    void Delete(char data1);//Deletes the correct node value
    void Print(ostream& Outfile) const;//Outputs the correct output
    coid Print1(ostream& Outfile) const; //Outputs the correct output

    //Private members of the class
    private:

    NodePtr head;
    NodePtr tail;
    NodePtr currptr;
    NodePtr newNodeptr;
    NodePtr searcher;
    NodePtr trailer;

    };




  5. #5
    Join Date
    Feb 2001
    Location
    Virginia, USA
    Posts
    170

    Re: Stack Linked List

    Once you have the linked list working properly, then you can use the linked-list class in a separate class called "Stack". You will have a private member of type "LinkedList" in your "Stack" class. The stack class has four essential public member functions: constructor, destructor, push, and pop. Once you have the stack class working properly, you can use it somewhere else where you only use push and pop to carry out infix and postfix arithmetic. So, yes, you should be using the stack to change infix to postfix.


  6. #6
    Join Date
    Feb 2001
    Location
    Virginia, USA
    Posts
    167

    Re: Stack Linked List

    Once you have the linked list working properly, then you can use the linked-list class in a separate class called "Stack". You will have a private member of type "LinkedList" in your "Stack" class. The stack class has four essential public member functions: constructor, destructor, push, and pop. Once you have the stack class working properly, you can use it somewhere else where you only use push and pop to carry out infix and postfix arithmetic. So, yes, you should be using the stack to change infix to postfix.


  7. #7
    Join Date
    Nov 2000
    Location
    IL, U.S.A.
    Posts
    218

    Re: Stack Linked List

    That goes back to my question if the stack is changing infix to postfix then what do I use the Linked List for?


  8. #8
    Join Date
    Feb 2001
    Location
    Virginia, USA
    Posts
    170

    Re: Stack Linked List

    The linked list is the foundation of your stack class. The stack class is the tool you use for conducting infix->postfix conversion.


  9. #9
    Join Date
    Feb 2001
    Location
    Virginia, USA
    Posts
    167

    Re: Stack Linked List

    The linked list is the foundation of your stack class. The stack class is the tool you use for conducting infix->postfix conversion.


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center