Implementation

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Implementation

Program gives the implementation of a simple RPN calculator. The purpose of this example is to illustrate the use of the Stack class. The program shown accepts very simplified RPN expressions: The expression may contain only single-digit integers, the addition operator, +, and the multiplication operator, *. In addition, the operator = pops the top value off the stack and prints it on the standard output stream, cout. Furthermore, the calculator does its computation entirely with integers.

program6591
Program: Stack Application--A Single-Digit, RPN Calculator

Notice that the RPNCalculator function is passed a reference to a Stack object. Consequently, the function manipulates the stack entirely through the abstract interface. The calculator does not depend on the stack implementation used! For example, if we wish to use a stack implemented using an array, we would declare a StackAsArray variable and invoke the calculator as follows:

StackAsArray s (10);
RPNCalculator (s);

On the other hand, if we decided to use the pointer-based stack implementation, we would write:

StackAsLinkedList s;
RPNCalculator (s);

The running time of the RPNCalculator function depends upon the number of symbols, operators and operands, in the expression being evaluated. If there are n symbols, the body of the for loop is executed n times. It should be fairly obvious that the amount of work done per symbol is constant, regardless of the type of symbol encountered. This is the case for both the StackAsArray and the StackAsLinkedList stack implementations. Therefore, the total running time needed to evaluate an expression comprised of n symbols is O(n).