CS111 Programming Assignment 7
Stacks and Queues

Instructor: Trish Cornez


Program 1: Stack - Last In First Out
    Use a stack to reverse the words of sentences in a paragraph. Begin by reading an entire paragraph.
    Then, read each word until you have a word that ends in a period - Add each of these words to the stack.
    Once you have a word with a period, pop the words off the stack and print them.

    Process your reverse sentence so that it ends with a period and the first letter of the first word is capitalized.


    Sample Run:
      Input...

    Twinkle twinkle little star. How I wish I was where you are.
      Output...

    Star little twinkle Twinkle. Are you where was I wish I how.






Program 2: Stack with Backtracking
    Write a program that converts an infix expression into an equivalent postfix expression.
    For this assignment, do not worry about invalid expressions - only consider correct infix notation.


    Guidelines for converting infix to postfix:
    1. Define two string variables for holding both expressions:
        String infx;
        String postfx;

    2. Define a stack for holding operators and the open parentheses '('.
    3. Use a loop structure to examine each element, token, in the infx string:
      • If the token is an operand , 'A' - 'Z' then append the character to the postfx string.
      • If the token is an operator (-, +, *, /, %) then you need to do two things:
        • Pop and append all the operators from the stack to the postfx string variable that have precedence greater than or equal to the operator you are examining.
        • Push the token onto the stack.
    4. After processing the infx string, some operators might be left on the stack. Pop and append all remaining stack elements to the postfx string.

    5. Finally, test your program on the following input :

This program will read an infix expression and convert it to a postfix expression.

Enter an infix expression (do not use spaces): X+Y*Z
This expression converted to postfix is XYZ*+

Enter an infix expression (do not use spaces): X+Y*Z/X
This expression converted to postfix is XYZ*X/+

Enter an infix expression (do not use spaces): A+B*C*D+E
This expression converted to postfix is ABC*D*+E+






Program 3: Implementing and Testing a Queue Class

    Implement a Queue class as a linked list of nodes containing Strings. Design the Queue class to remove Nodes at the front of the linked list and add Nodes at the back. Use only singly linked Nodes.

    Implement Queue operations (member methods) for addLast() and removeFirst().
    Test your Queue class by implementing the childhood game of Hide and Seek. The diagram below shows seven players in the elimination process as simulated by a queue.
Queue Action
Bobo Ruth Ned Sam Ari Barb Lucy Remove Bobo and Ruth from the front and add them to the end.
Ned Sam Ari Barb Lucy Bobo Ruth Remove Ned
Sam Ari Barb Lucy Bobo Ruth Move Sam and Ari to the end of the list.
Barb Lucy Bobo Ruth Sam Ari Remove Barb
Lucy Bobo Ruth Sam Ari Move Lucy and Bobo to the end of the list.
Ruth Sam Ari Lucy Bobo Remove Ruth
Sam Ari Lucy Bobo Move Sam and Ari to the end of the list.
Lucy Bobo Sam Ari Remove Lucy
Bobo Sam Ari Move Bobo and Sam to the end of the list.
Ari Bobo Sam Remove Ari
Bobo Sam Move Bobo and Sam to the end of the list.
Bobo Sam Remove Bobo
Sam Sam is the only person left in line therefore she is IT.





Extra Credit

Modify the above application so that it reads parenthesis to dientify priorities. Example:
Enter an infix expression (do not use spaces): (X+Y)*Z
This expression converted to postfix is XY+Z*

Enter an infix expression (do not use spaces): (X+Y)/(X-Y)
This expression converted to postfix is XY+XY-/

Method: Use the same stack for holding operators and store an open parentheses '(' token when it occurs.
  1. if the token is an open parentheses, '(', then push it onto the stack
  2. If the token is a closed parentheses, ')', then pop and append all the symbols from the stack until the most recent left parentheses. Pop and discard the left parentheses.
  3. If the token is an operator (-, +, *, /, %) then you need to do two things: