Projects

1. Enhance the functionality of the RPN calculator given in Program  in the following ways:
   1. Use double-precision, floating-point arithmetic. I.e., use the Double class defined in Program .
   2. Provide the complete repertoire of basic operators: +, -, and .
   3. Add an exponentiation operator and a unary negation operator.
   4. Add a clear function that empties the operand stack and a print function that prints out the contents of the operand stack.
2. Modify Program  so that it accepts expressions written in prefix (Polish) notation. Hint: See Exercise .
3. Write a program to convert a postfix expression into an infix expression using a stack. One way to do this is to modify the RPN calculator program given in Program  to use a stack of infix expressions. The expressions can be represented as instances of the String class defined in Program . A binary operator should pop two strings from the stack and then push a string which is formed by concatenating the operator and its operands in the correct order. For example, suppose the operator is '*' and the two strings popped from the stack are "(b+c)" and "a". Then the result that gets pushed onto the stack is the string "a*(b+c)".
4.   Devise a scheme using a stack to convert an infix expression to a postfix expression. Hint: In a postfix expression operators appear after their operands whereas in an infix expression they appear between their operands. Process the symbols in the prefix expression one-by-one. Output operands immediately, but save the operators in a stack until they are needed. Pay special attention to the precedence of the operators.
5. Modify your solution to Project  so that it immediately evaluates the infix expression. I.e., create an InfixCalculator routine in the style of Program .
6. Consider a string of characters, S, comprised only of the characters (, ), [, ], and . We say that S is balanced if it has one of the following forms:
   • , i.e., S is the string of length zero,
   • ,
   • ,
   • ,
   • 
   where both T and U are balanced strings, In other words, for every left parenthesis, bracket or brace, there is a corresponding right parenthesis, bracket or brace. E.g., "{()[()]}" is balanced, but "([)]" is not. Write a program that uses a stack of characters to test whether a given string is balanced. (Use the Char class defined in Program ).
7. Design and implement a MultipleStack class which provides stacks in a single container. The declaration of the class should look something like this:

   class MultipleStack : public Container
   {
       // ...
   public:
       MultipleStack (unsigned int);
       void Push (Object&, unsigned int);
       Object& Pop (unsigned int);
       // ...
   };

   • The constructor takes a single integer argument that specifies the number of stacks in the container.
   • The Push function takes two arguments. The first gives the object to be pushed and the second specifies the stack on which to push it.
   • The Pop function takes a single integer argument which specifies the stack to pop.
   Choose one of the following implementation approaches:
   1. Keep all the stack elements in a single array.
   2. Use an array of Stack objects.
   3. Use a linked list of Stack objects.
8. Design and implement a class called DequeAsDoublyLinkedList that provides a deque implemented as a doubly-linked list. Select one of the approaches shown in Figure .
9. In Section , the Deque class is derived from the Queue class. This is the design paradigm known as generalization. The alternative paradigm is specialization in which the Queue class is derived from the Deque class. Redesign the Deque and Queue components of the class hierarchy using specialization.

     
   Figure: Expression Tree for
   

10. Devise an approach for evaluating an arithmetic expression using a queue (rather than a stack). Hint: Transform the expression into a tree as shown in Figure  and then do a breadth-first traversal of the tree in reverse (see Exercise ). E.g., the expression becomes . Evaluate the resulting sequence from left to right using a queue in the same way that a postfix expression is evaluated using a stack.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.