CSSE 2: Data Structures and Algorithms III

Stacks Worksheet

  1. Implement stacks using the following structure

    2. typedef struct node

    {

    int x;

    struct node * next;

    }IntNode;

    Using this implementation read a list of integer values and print them in reverse order

  2. Using the implementation in 1 read a list of integer values, store them on the stack and then remove all occurrences of 2 from the stack.

  3. An expression in postfix notation can be evaluated at run time by means of a stack. For simplicity, assume that the postfix expression consists of integer values and operators only. For example, we might have the following postfix expression:

8 5 4 + * 7 –

The evaluation proceeds as follows: when a value is encountered, it is pushed onto the stack. When an operator is encountered, the first and second items on the stack are retrieved and popped, the operator is applied (the second item is the left operand, the first item is the right operand) and the result is pushed onto the stack. When the postfix expression has been processed, the value of that expression is the top item on the stack.

Given the functions isdigit and calc below, write a program that reads in an arithmetic expression in postfix notation and evaluates it.

int isdigit (char s)

//checks to see if a character is a digit or not

{ return(s>='0'&& s <='9');

}

int calc(int op, int op1, int op2)

//calculates op1 op op2 e.g. 3 + 4

{

switch(op)

{

case '+': return (op1 + op2);

case '-': return (op1 - op2);

case '*': return (op1 * op2);

case '/': return (op1 / op2);

default: cout <<"Illegal Operation" <<endl;

exit(1);

}

}

Using the given algorithm evaluate the following postfix strings:

  1. 7 3 + 4 *

  2. 6 5 – 3 4 * +

 

Some tutorial exercises:

Convert the following infix expressions into postfix notation:

  1. A + B + CA/B*C*D

  2. A*B+C

  3. A+B*C

  4. A/B+C*D

  5. (A+B)*C

  6. A+(B+C*D)

  7. A*(B-2*C)*(D+E)

  8. A-(B+C*D)+E*F