Linked List Programming Assignment

Stacks

A stack is a special type of list with restricted access operations. Typically, a stack is viewed as a vertical list in which items can only be added to or removed from the list at the top. A typical stack class will offer a limited set of methods something like the following:

class stack
{
public:
  stack();
  ~stack();

  bool isEmpty() const;
  int top() const; // Return the int at the top of the stack
  
  void push(int x); // Push a new int on the stack
  void pop(); // Remove the item at the top of the stack
};

Because a stack is essentially a simplified list, we can implement a stack in much the same way that we implemented a linked list in chapter 3. Because the stack is actually simpler than the linked list in its behavior, we can make the implementation of the stack even simpler than the implementation of the singly linked list in chapter 3.

Here is an outline of how we could implement a stack class.

• The stack is implemented as a singly linked chain of nodes.
• Each node contains an int and a pointer.
• The stack class itself just contains one pointer, a pointer to the item at the top of the stack.

Implement the stack class following this outline.

Stack class application - evaluating arithmetic statements

As a second part of this programming exercise, we will also write a program that uses the integer stack class we just implemented to solve a problem. The problem is to evaluate arithmetic expressions written in postfix form. In postfix form, the operands of an arithmetic statement appear followed by the operator. Here are some examples of arithmetic expressions written in postfix form:

1 2 + // Equivalent to 1+2
2 3 4 + * // Equivalent to (2 * (3 + 4))
2 3 + 4 * // Equivalent to (2 + 3)*4

One of the virtues of postfix form is that expressions can be written without the need for parentheses. Here is an algorithm for evaluating an arithmetic expression written in postfix form with the aid of a stack of integers.

• Scan the expression from left to right
• When you encounter an integer, push it on the stack.
• When you encounter an arithmetic operator, pop the top two numbers off the stack and use them as operands for the indicated operation. Push the resulting number back on the stack.
• When you reach the end of the expression, the result of the calculation should be the sole item on the stack.

Your assignment is to write a C++ program that uses your integer stack class and the algorithm outlined above to evaluate postfix arithmetic expressions that the user enters. Your program should support the use of both positive and negative integers, and all five of the integer arithmetic operators, +, - , *, /, and %.

Here is a helpful hint. One problem you will have to solve is how to scan the input the user types and separate it into integers and operators. Something you will find useful to help you do this is the cin.peek() method. peek() returns a C++ char telling you what the next character in the input stream is without actually removing that character from the input stream. Another useful method is get(), which returns the next character in the input stream.

Here is some code to demonstrate how you can use peek() and get() to read the input line and do the right thing with the input.

do {
  char ch = cin.peek();
  if(ch >= '0' && ch <= '9')
    {
    // Read an integer
    int n;
    cin >> n;
    // Insert code here to do the right thing with n
    }
  else if(ch == ' ')
    ch = cin.get(); // skip the space
  else
    {
    ch = cin.get();
    // ch is an operator or the - at the start of a number
    // Insert code here to do the right thing.
    }
} while(cin.peek() != '\n');

The loop contains a test to make it stop correctly at the end of the input line.