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 console. Furthermore, the calculator does its computation entirely with integers.

program6065
Program: Stack application--a single-digit, RPN calculator.

Notice that the stack variable of the Calculator method may be any object that implements the Stack interface. Consequently, the calculator does not depend on the stack implementation used! For example, if we wish to use a stack implemented using an array, we can simply replace line 6 with the following:

Stack stack = new StackAsArray(10);

The running time of the Calculator method depends upon the number of symbols, operators, and operands, in the expression being evaluated. If there are n symbols, the body of the while 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).