Chapter 11 - Introduction to Abstract Data Types (ADTs)



Chapter 11 - Introduction to Abstract Data Types (ADTs)

11.1 An Example ADT

Arithmetic Operations on Complex Numbers

Designing an ADT for Complex Numbers

11.2 Lists

Array Implementation

Linked List Implementation

11.3 Stacks

Array Implementation

Linked List Implementation

11.4 Queues

Array Implementation

Linked List Implementation

11.5 Applications

The Mandelbrot Set Generator

RPN Expression Evaluator

Infix to Postfix Expression Converter

Drawing the Centipede

Chapter 11 - Introduction to Abstract Data Types (ADTs)

In this chapter we formalize the concept of an abstract data type (ADT), as a data structure and the functions and procedures that give the programmer access to it. We will build ADTs for a number of common structured data types including the list, stack and queue.

11.1 An Example ADT

We are familiar with literal data types such as float, integer, character and string. We have also studied arrays of these literal types. Abstract data types (ADTs) are sets of mathematical and logical operations on entities (of any literal type) in which the underlying data structure and the specific implementation of the operations is unknown to the user.

As a first example we will build an ADT for complex numbers. Before designing the adt_complex package, we need to review the properties of complex numbers.

Let p = a+bi represent a complex number, where [pic] . The number a is called the real part of p and b is called the imaginary part of p. Graphically a complex number is represented as a point in the complex plane.

Arithmetic Operations on Complex Numbers

The basic arithmetic operations of addition, subtraction, multiplication and division on complex numbers are given by,

where p and q are complex numbers. Notice that for each operation there is a real part and an imaginary part that remain separated. The + sign between the real and imaginary parts is not a mathematical operation but rather a notational separator.

Designing an ADT for Complex Numbers

The ADT for complex numbers should permit the user (application programmer) to create, read and display complex numbers as well as compute the results of +, -, * and /. The user also needs to extract the real and imaginary components as separate entities (real values). However, the user should not be given direct access to the components of a complex number. All these functions should be provided as part of the ADT interface.

Choosing a Data Representation

We first need to establish an internal representation for complex number types for our ADT.

private

type complex is record

real : float;

imag : float;

end record;

We will make this type private so that the user of the ADT package will not be able to manipulate the real and imaginary components directly.

Next we need to list the operations we plan to include in our ADT.

Reading and Writing Complex Numbers

As part of the interface we include get( ) and put( ) procedures for reading and writing complex numbers. These procedures can be implemented in a number of ways. In our ADT we will ask the user to enter the real and imaginary components (separated by a space) and we will display a complex number using the real_part + i imaginary_part format. The specification for the get( ) and put( ) procedures do not use these components. Instead we simply pass a complex value.

procedure get(c:out complex);

procedure put(c:in complex);

Math Operations

The basic math operations are written as infix function in order to simplify expressions using complex values.

function "+"(a,b: complex) return complex;

function "-"(a,b: complex) return complex;

function "*"(a,b: complex) return complex;

function "/"(a,b: complex) return complex;

For example the following expression could be written using the adt_complex package,

r := ((p+q)*(p-q))/(q*q);

where p, q and r are complex. The use of the same arithmetic operator symbols for complex math that are used for floating point and integer values is a powerful feature of Ada, called overloading.

Creating New Complex Numbers

The application programmer may want to create new complex numbers within the program. This can be implemented by adding a make_complex( ) function to our set of operations.

function make_complex(r,i : float) return complex;

Using make_complex(real,imag) the programmer can create a complex number by passing the real and imaginary parts into the function as floating point (real) values.

Extracting the Real and Imaginary Components

The interface should also permit the programmer to extract the real or imaginary parts from a complex number.

function get_real(c: complex) return float;

function get_imag(c: complex) return float;

These functions return the components of a complex number as floating point values.

Computing the Magnitude

Another common operation performed on complex number is the computation of the magnitude. The magnitude of a complex number is a real value representing the distance of the complex number from the origin in the complex plane.

function magnitude(c:complex) return float;

The adt_complex Package Specification

The complete listing of the adt_complex specification is shown below.

with ada.float_text_io;

use ada.float_text_io;

package adt_complex is

type complex is private;

procedure get(c:out complex);

procedure put(c:in complex);

function "+"(a,b: complex) return complex;

function "-"(a,b: complex) return complex;

function "*"(a,b: complex) return complex;

function "/"(a,b: complex) return complex;

function make_complex(r,i : float) return complex;

function get_real(c: complex) return float;

function get_imag(c: complex) return float;

function magnitude(c:complex) return float;

private

type complex is record

real : float;

imag : float;

end record;

end adt_complex;

The specification should provide the application programmer with all the information needed to use the adt_complex package. A comment block containing additional details and/or examples of the use of the interface would be helpful. In particular, we might want to describe the use of the get( ) procedure.

The adt_complex Package Body

We include in the partial listing below some of the arithmetic operations for the adt_complex interface. Note that the square root used in the magnitude( ) function forces us to include a mathematics package.

with ada.text_io, ada.float_text_io,

ada.numerics.elementary_functions;

use ada.text_io, ada.float_text_io,

ada.numerics.elementary_functions;

package body adt_complex is

-- this is not a complete listing

function "+"(a,b: complex) return complex is

c : complex;

begin

c.real:=a.real+b.real;

c.imag:=a.imag+b.imag;

return c;

end "+";

function "*"(a,b: complex) return complex is

c : complex;

begin

c.real:=a.real*b.real-a.imag*b.imag;

c.imag:=a.real*b.imag+b.real*a.imag;

return c;

end "*";

function "/"(a,b: complex) return complex is

c : complex;

begin

c.real:=(a.real*b.real+a.imag*b.imag)/

(b.real*b.real+b.imag*b.imag);

c.imag:=(a.imag*b.real-a.real*b.imag)/

(b.real*b.real+b.imag*b.imag);

return c;

end "/";

function magnitude(c:complex) return float is

begin

return sqrt(c.real*c.real+c.imag*c.imag);

end magnitude;

end adt_complex;

Inside the body of the package we can use dot-notation to access and manipulate the real and imaginary components of the complex values. Making the complex type private prevents the application programmer from using dot-notation to access the real or imag fields of the record.

We can write a simple program to test the adt_complex package. The listing below asks the user to enter two complex numbers p and q. Then these numbers are added together, subtracted, multiplied and divided with the results displayed. Also the real and imaginary components of p are extracted and the magnitude of p is computed and displayed.

with ada.text_io, adt_complex, ada.float_text_io;

use ada.text_io, adt_complex, ada.float_text_io;

procedure test_complex is

p,q : complex;

begin

put("Enter p..... ");

get(p);

put("Enter q..... ");

get(q);

new_line;

put("p+q = "); put(p+q); new_line;

put("p-q = "); put(p-q); new_line;

put("p*q = "); put(p*q); new_line;

put("p/q = "); put(p/q); new_line;

put("magnitude(p) = "); put(magnitude(p)); new_line;

put("real part of p = "); put(get_real(p)); new_line;

put("imag part of p = "); put(get_imag(p)); new_line;

end test_complex;

The adt_complex package specification, body and the test program above are included in the source code list associated with this chapter.

11.2 Lists

A list is an ordered sequence of items of any type we choose with one of the items designated as the current item. For example the values below

previous next

4 17 9 42 3 6 12

first current last

represent a list with the value 42 tagged as the current item. We may also designate other special values such as first, last, previous and next. Note that previous and next are defined with respect to the current item. For now we will limit our tags to designating the current item.

An ADT provides for a set of operations on the data type such as adding items, removing them, counting the number of items or checking for the presence of a particular item (or value). The set of operations that give the programmer access and control of the data type is called the ADT interface. Typical operations of the interface are shown below:

create_list(list)

add_before(list,position,value)

add_after(list,position,value)

delete(list,position)

find_item(list,value)

display(list,current)

destroy_list(list)

advance(list,current)

decriment(list,current)

get_current(list)

Before we can build an ADT for the list, we need to decide on the underlying data structure to be used. In our first version of the list ADT we will use an array to represent the list.

Array Implementation

We can implement a list as a contiguous array using the predefined type array in Ada.

n_max : constant integer := 1000;

the_list : is array(1..n_max) of any_literal_type;

Our operations on the ADT must be compatible with this data structure. Using a linear contiguous array (as opposed to a linked list) will simplify the implementation of some of the operations on the ADT such as display( ) and find( ). Unfortunately the array implementation will cause us some trouble with other operations such as add_before( ) and delete( ).

In order to insert a value x at the ith position in the list we would have to move all values ai+1, . . , an forward one position to make room for x. Similarly when we delete a value from the ith position we need to move all successors of ai backward one position to fill the hole left by the deleted value.

Using the contiguous array also creates the problem of forcing us to limit the size of the list to some maximum number of values n_max. In the idealized list ADT there should be no limit to the size of the list. Actually there will always be a finite maximum list size due to finite memory capacity, but the array implementation creates an immediate problem that must be solved.

We would like to set the array size to be a large as the largest list we will need for any application, but we cannot anticipate this value. Alternatively we will need to modify and recompile the list ADT for each application. This greatly diminishes the usefulness of the list ADT since it defeats the primary purpose of building the list ADT as a separate package that can be used in multiple applications without further modification.

Linked List Implementation

The problem of wasting memory by having to establish a large array that may not be used can be avoided with linked lists. Consider a singly-linked list implementation for the list ADT. The current item can be designated with a pointer to the appropriate list element. Creation and insertion of new values can be accomplished in the manner demonstrated in the previous chapter.

Unfortunately a singly-linked list does not give us direct access to the node that is previous to the current node. This makes is difficult to implement some of the interface functions for the list ADT.

We can build a doubly-linked list implementation that gives us access to nodes on either side of the current node using a dynamic data structure similar to the following:

type node;

type pointer is access node;

type node is record

data : any_data_type;

next : pointer;

prev : pointer;

end record;

This record provides a pointer to the next node and to the previous node in the list. The interface function add_after( ) in which an element is inserted before the current node is implemented by the following code segment. Assume that current and newnode are pointers to pointer records as defined above.

newnode := new node;

newnode.data := val;

newnode.next := current;

newnode.prev := current.prev;

current.prev := newnode;

newnode.prev.next := newnode;

In this code segment the data value, val is placed into a newly created record and inserted into the list just before the record pointed by current.

11.3 Stacks

The stack is an abstract data type (ADT) that can be used to save data elements in a last-in first-out (LIFO) order. The only item in a stack that can be accessed is the last item placed on the stack. This data structure is analogous to a stack of trays in a cafeteria. As you put trays onto the stack the rest of the stack is pushed down onto a spring loaded platform. As you take trays off the top of the stack the platform pops up to give access to the next tray on the stack.

Array Implementation

We will look at various ways to implement a stack ADT but for now we will build a stack for integers using an ordinary (i.e. one-dimensional, linear and contiguous) list data structure.

maxindex : constant integer := 1000;

type stacktype is array(1..maxindex) of integer;

S : stacktype;

itop : integer;

In this declaration we have specified that the maximum number of items in the stack will be 1000, that itop will be the index pointing to the item on the top of the stack and that the stack itself will be called S.  We will create a number of functions and procedures that provide access and control of the stack data type.  These will include a mechanism for adding items to the stack called push(S,x), taking items off the stack pop(S,x), checking the value on the top of the stack top(S) and testing to see if the stack is empty is_empty(S), or full is_full(S).

procedure push(S: in out stacktype; x : in integer);

procedure pop(S: in out stacktype; x: out integer);

function top(S) return integer;

function is_empty(S) return boolean;

function is_full(S) return boolean;

These functions and procedures provide all the interactivity we need to use the stack. We never want to have to worry about the details of its implementation but sometimes this is not possible. 

The function is_full(S) is necessary since we are dealing with a fixed-size list for our implementation of the stack.  In the ideal case we would never have to check to see if the stack was full since the abstract concept of a stack does not place a limit on its size. 

The procedure push(S,x) pushes the value contained in x onto the stack S.  The procedure pop(S,x) loads the value of the item on the top of the stack into the variable space labeled x and removes this value from the top of the stack S.  Actually all we need to do is decrement the index itop so that it points to the next lower position in the stack. The function top(S) returns the value at the top of the stack S without removing it.

You may question why is it OK for top(S) to be a function while we must implement the pop operation as a procedure.  Remember that the sole purpose of a function is to compute and return a value. Functions never perform any other operation or affect the values of any variables beyond the scope of the function itself.  If we were to implement pop as a function such as y:=pop(S) then this function would have to decrement the index itop pointing to the top of the stack in addition to returning the value S(itop). While Ada allows side-effects, they are discouraged, and are not considered acceptable in good program design.

Lets take a closer look at how the stack data structure is managed as a list.  The list S is declared to hold 1000 integers S(1), S(2), . . . , S(1000).  The index itop points to the item currently at the top of the stack.

We can let itop=0 when the stack is empty, so our boolean function is_empty(S) only needs to check the value of the index itop.

function is_empty(S : stacktype) return boolean is

begin

  return (itop=0);

end is_empty;

Remember that the equal sign is an operator that compares two values of the same type and returns true if they are equal.  It is a good practice to imagine a question mark over the operators to remind ourselves of their purpose.  So this function returns true if itop=0 otherwise it returns false.  The boolean function is_full(S) has an equivalent form.

function is_full(S : stacktype) return boolean is

begin

  return (itop=maxindex);

end is_full;

Recall that maxindex is a constant set to 1000 in this example.  The procedure push(S,x) must check to see if the stack is full and if not, it places the value of the parameter x into the next available position in the list S.  What should we do if the list is full and someone is trying to push another value onto the stack?  When we study exceptions we will see how to trap on such errors and report the problem to the user.  For now we can let the push procedure ignore attempts to push values onto a full stack We are providing a mechanism for checking to see if the stack is full, so if someone pushes a value onto a full stack it their own fault when the program fails to operate correctly.

procedure push(S : in out stacktype; x : in integer) is

begin

  if not(is_full(S)) then

    itop:=itop+1;

    S(itop):=x;

  else

put("Error:  Stack Full");

  end if;

end push;

Actually, these types of decisions are central to issues of code correctness and software risk.  As programmers we cannot predict how our source code may be used (or abused) in some future application. Therefore it is important that we build our code as carefully as we can, making sure that we provide protection against those run-time and application errors that we can predict.  There will still be plenty of "unknown unknowns" to cause problems.

The pop procedure has a similar form. In this procedure we need to check to make sure that the stack is not empty.

procedure pop(S : in out stacktype; x : out integer) is

begin

  if not(is_empty(S)) then

    x:=S(itop);

    itop:=itop-1;

  else

    put("Error:  Stack Empty");

  end if;

end pop;

Finally, the function top(S) returns the value on the top of the stack.  If the stack is empty we can return 0 or we can create an exception.  Since top(S) is a function we choose to simply return a zero when the stack is empty and include comments in the package specification instructing the programmer to check for an empty stack before using this function.

function top(S : stacktype) return integer is

begin

  if not(is_empty(S)) then

    return S(itop);

  else

    return 0;

  end if;

end top;

11.4 Queues

A queue is another type of list data structure to which the user has restricted access. New items are placed at the back of a queue and the next available item is at the front of the queue. This is called first-in first-out (FIFO) order. An idealized queue is an infinite capacity list with special tags for the entries front and back.

We will define the following interface for a queue abstract data type.

enqueue(Q,x) - appends the value in x to the back of the queue Q

dequeue(Q,x) - loads the value at the front of the queue Q into the parameter x

front(Q) - returns the value at the front of the queue Q without changing the queue

is_empty(Q) - a boolean function that returns true if the queue is empty

is_full(Q) - a boolean function that returns true if the queue is full

Array Implementation

The is_full(Q) Boolean function will only be needed if we use a fixed-size array as our underlying list data structure. Let's build a package for the queue ADT. First we need a specification for the package. In the spec we declare the data structure and list the first lines of the functions and procedures that will be the ADT interface.

maxindex : constant integer := 1000;

type listype is array(1..maxindex)of float;

type queue is record

list : listype;

front : integer;

back : integer;

end record;

We declare the queue type in the specification but we do not declare an identifier Q of type queue. This is because we are not executing the package specification. Also there are no other packages withed or used in this specification. Remember that we create a package specification to permit the user to see the functions and procedures that are available without having to show their implementations. Our specification will be saved as adt_queue.ads and has the following form.

package adt_queue is

:

[data structure goes here]

:

[function and procedure specifications go here]

:

end adt_queue;

Next, we need to build the adt_queue package body. The specification and body of the package are compiled only. We don't try to build them since there is no main executable. The shown below is not complete.

package body adt_queue is

function is_empty(Q:queue)return boolean is

begin

return Q.front=0;

end is_empty;

function is_full(Q:queue)return boolean is

begin

return Q.back=Q.front;

end is_full;

function front(Q:queue)return float is

begin

if not(is_empty(Q)) then

return Q.list(Q.front);

else

return 0.0;

end if;

end front;

procedure enqueue(Q: in out queue; x : in float) is

begin

if not(is_full(Q)) then

Q.list(Q.back):=x;

Q.back:=Q.back+1;

if Q.back>maxindex then

Q.back:=1;

end if;

else

put("ERROR: Queue full");

end if;

end enqueue;

procedure dequeue(Q: in out queue; x : out float) is

begin

if not(is_empty(Q)) then

x:=Q.list(Q.front);

Q.front:=Q.front+1;

if Q.front>maxindex then

Q.front:=1;

end if;

else

put("ERROR: Queue Empty");

end if;

end dequeue;

end adt_queue;

The package body includes the word body in its descriptor line and is saved as adt_queue.adb. If we set the index called Q.front to zero (i.e. outside the range of valid indices of the list) we can simply return the boolean value of Q.front=0 to indicate whether the queue is empty. Since Q.back is the index of the next available position in the Q list, we know the queue is full when Q.back = Q.front.

Implementing the queue as a fixed-size list creates a few complications for us. We need to maintain the index values for front and back as items are enqueued (added to the list) and dequeued (removed from the list). As we reach the maxindex we need to wrap-around to the first index while checking to make sure that the list is not full or empty. Consider the following example case.

Initially a queue list is empty with back=1 (corresponding to the first available position in the list). As values are enqueued (in order 7, 2, 4, 8) the index back is incremented to the next available position in the list. As values are dequeued the index front is incremented to the next item in the queue list. When front=back then we know that the queue is empty.

Eventually these indices will reach the maximum index of the queue list (called maxindex). If either back or front are increased to a value>maxindex then they are set back to 1.

enqueue(Q,8)

enqueue(Q,4)

enqueue(Q,2)

enqueue(Q,7)

:

dequeue(Q,X)

dequeue(Q,Y)

:

enqueue(Q,2)

enqueue(Q,8)

enqueue(Q,5)

euqueue(Q,9)

These complications can be eliminated by choosing a different representation for the list data structure.

Linked List Implementation

Using a linked-list to represent the list data structure of our queue simplifies our interface functions and procedures. While we are rebuilding the adt_queue we will also make it generic. That is we will leave the data_type being managed by the queue unspecified until we are building an application. The sample code below is a generic version of the adt_queue package that uses dynamic memory allocation rather than a static array. We no longer need to concern

ourselves with the issue of a full queue.

generic

type data_type is private;

package adt_queue is

type qpointer is private;

type qnode is private;

type qtype is private;

function is_empty(Q : qtype) return boolean;

procedure enqueue(Q: in out qtype; x : in data_type);

procedure dequeue(Q: in out qtype; x : out data_type);

private

type qpointer is access qnode;

type qnode is record

data : data_type;

next : qpointer;

end record;

type qtype is record

front : qpointer := null;

back : qpointer := null;

end record;

end adt_queue;

The package body includes an instantiation of the unchecked_deallocation procedure which we have named remove_qnode. The type called data_type is generic in the adt_queue specification which permits the use of this package for any data type. In order to use adt_queue this generic package must be instantiated. More than one instantiation of adt_queue can be declared in a single program.

with ada.text_io, ada.unchecked_deallocation;

use ada.text_io;

package body adt_queue is

procedure remove_qnode

is new ada.unchecked_deallocation(qnode,qpointer);

function is_empty(Q : qtype) return boolean is

begin

return Q.front=null;

end is_empty;

procedure enqueue(Q: in out qtype; x : in data_type) is

newQ : qpointer;

begin

newQ := new qnode;

newQ.data := x;

newQ.next := null;

if Q.front=null then

Q.front:=newQ;

Q.back:=newQ;

else

Q.back.next:=newQ;

Q.back:=newQ;

end if;

end enqueue;

procedure dequeue(Q: in out qtype; x : out data_type) is

dumpme : qpointer;

begin

if Q.front=null then

put("EMPTY QUEUE ERROR");

else

x:=Q.front.data;

dumpme:=Q.front;

Q.front:=Q.front.next;

remove_qnode(dumpme);

end if;

end dequeue;

end adt_queue;

Designating the private types in the adt_queue limits access to the underlying linked-list data structure so that only the enqueue() procedure can allocate new memory from the available heap. The dequeue( ) procedure includes a call to the remove_qnode( ) procedure we instantiated above, which releases (deallocates) memory when we are finished with it. If remove_qnode( ) was not called in dequeue( ) , the discarded pointer records would not be available for later use. Not releasing memory back to the heap (i.e. available memory) creates what is called a memory leak. Our ADT prevents sloppy coding from wasting memory.

11.5 Applications

The Mandelbrot Set Generator

11.1: Write an Ada program that determines if a particular complex value is a member of the Mandelbrot Set.

The Mandelbrot Set is defined on the complex plane. Every complex number has a corresponding point in the complex plane. By convention the real component specifies the position on the horizontal axis and the imaginary component specifies the position on the imaginary axis.

The magnitude of a complex number p is the length (a real value) of line connecting the origin and the point representing p in the complex plane.  The Mandelbrot set is the set of all complex points C for which the magnitude of Z in

Z := Z*Z + C

converges to a fixed value when iterated. The parameter Z is a complex number initially set to zero (Z=0+i0).  To iterate this expression we set Z=0+i0 and C to the chosen number in the complex plane.  We compute a new value for Z and check its magnitude.  We then use the current value of Z to compute the next Z value.  Eventually we find that the magnitude of Z either converges to a fixed value or it diverges (continually grows to a larger and larger value). 

If we color the points C that converge to zero in the complex plane and color the points that diverge white, we obtain an image similar to the one shown below, in which the black region represents points in the Mandelbrot Set.

Mandelbrot Set

Our task in this exercise is to create a boolean function that returns true if its complex argument is in the Mandelbrot Set and false otherwise.

All the points in the Mandelbrot Set are within a radius of magnitude 2.0 from the origin of the complex plane. This means that we can terminate the iteration when the magnitude of the iterated value of Z exceeds 2.0 We can also terminate the iteration when we have reached a fixed value for Z. This may not be so easy to determine, as we will see. We can attempt to detect when the iterated value of Z has reached a fixed point (constant value) using a method similar to the following

put("Enter a complex number C = ");

get(C);

Z:=make_complex(0.0,0.0);

Zmag_old:=float'last;

loop

Z:=Z*Z + C;

Zmag:=magnitude(Z);

exit when Zmag>=2.0 or Zmag-Zmag_old;

Zmag_old:=Zmag;

end loop;

put("The value C ");

if magnitude(Z)>2.0 then

put("is not a member of the Mandelbrot Set");

else

put("is a member of the Mandelbrot Set");

end if;

Note: This code segment uses the interface provided in the ADT_complex package for creating, displaying and performing arithmetic operations on complex values.

The problem with this method is that we are testing to see if two floating point values, namely Zmag and Zmag_old are equal. As we have seen this can create problems due to the way floating point values are internally represented in the computer. We need a better way to test for convergence. We could try to test for the difference between the magnitudes of two successive iterations of Z being less than some small amount, say 1x10-6.

exit when magnitude(z)>=2.0 or abs(magnitude(z)-zmag_old)= input_token precedence loop

operator_token=pop(OPERATOR)

if operator_token /= '(' then

output(ANSWER,operator_token)

end if

end loop

push(OPERATOR,input_token)

elsif input_token = '(' then

push(OPERATOR,input_token)

else -- input token must be ')'

while top(OPERATOR) /= '(' loop

operator_token=pop(OPERATOR)

output(ANSWER,operator_token)

end loop

operator_token=pop(OPERATOR) -- this token must be a '('

end if

end loop

while OPERATOR stack not empty loop --flush the OPERATOR stack

output(ANSWER,pop(OPERATOR))

end loop

This algorithm relies on the establishment of an order of precedence for each operator. This precedence follows our notion of operator precedence from basic arithmetic. That is, multiplication and division have higher precedence than addition and subtraction. We can test our algorithm on the same example infix expression we used in the previous exercise.

|Infix Expression |OPERATOR stack ANSWER postfix expression |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | ( |

| |__(___ |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | ( |

| |__(___ X |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | + |

| |( |

| |__(___ XY |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | __(___ XY+ |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | |

| |* |

| |__(___ XY+ |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | ( |

| |* |

| |__(___ XY+ |

| | |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) |______ XY+X |

| | - |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) |( |

| |* |

| |__(___ XY+XZ |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | * |

| |__(___ XY+XZ- |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | __ ___ XY+XZ-* |

| | ( |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) |( |

| |__/___ XY+XZ-*X |

| | + |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) |( |

| |( |

| |__/___ XY+XZ-*XZ |

| | ( |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) |* |

| |( |

| |__/___ XY+XZ-*XZ+X |

| | - |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) |( |

| |* |

| |( |

| |__/___ XY+XZ-*XZ+XY |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | __/___ XY+XZ-*XZ+XY-* |

|((X+Y)*(X-Z))/((X+Z)*(X-Y)) | __ ___ XY+XZ-*XZ+XY-*/ |

The implementation of this algorithm is challenging for the beginning programmer. It requires a substantial program design effort before sitting down at the keyboard. An effective design approach is to use a top-down problem decomposition. As we scan the pseudo code we find a list of operations that should be written as separate functions or procedures.

is_empty(input_string) - a boolean function to tell us when we have read all the tokens from the input string.

get_next_token(input_token) - a procedure to get the next input_token (for our example we can assume that all tokens are single ASCII characters)

is_operand(input_token) - a boolean function to recognize if an input_token is an operand

is_operator(input_token) - a boolean function to recognize if an input_token is an operator

precedence(input_token) - a function to return the precedence of an operator (we will need to establish a number precedence for +, -, * and / operators (e.g. +=1, -=1, *=2, /=2).

output(ANSWER,token) - a procedure to append the next token to the ANSWER string

When testing for '(' and ')' we can simply compare the token to these ASCII characters directly Finally we can use the interface provided in the adt_stack for the pop( ) and push( ) operations in our algorithm implementation.

This application gives you a rough sketch of the effort required to implement the infix to postfix expression converter. This program is a component of the Spreadsheet Class Project in Appendix B.

Drawing the Centipede

11.4: Build a graphical program to display a centipede (segmented worm) moving across the screen. The user should be able to specify the number and size of the segments and the flexibility of the centipede (i.e. how quickly the centipede can change directions).

The segments can be drawn as circles of radius r (specified by the user). They need to be separated by an amount equal to their diameters, so we can compute the position of the next segment by converting the segment center position from Polar to Cartesian coordinates.

The maximum change in direction between segments del_ang (specified by the user) can be used to generate a random angle ang for the coordinate conversions. Choosing 2*r for the magnitude of the change in position ensures that the segments will be contiguous.

ang:=ang+(ranu-0.5)*del_ang;

px:=integer(float(px_old)+float(size)*cos(ang));

py:=integer(float(py_old)+float(size)*sin(ang));

As usual we need to be careful about type casting. In this case we convert our position px_old and py_old to floating point so that we can multiply by the cosine and sine of the angle ang.

The problem statement does not mention what we should do when our centipede moves off the edge of the display window. As the centipede leaves one side of the window we will begin displaying it on the opposite side. This window wrapping operation can be implemented with a set of if...then statements.

if px>=xm-size then

px:=size;

elsif px=ym-size then

py:=size;

elsif py ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download