Java Reference
In-Depth Information
P
ROJECTS
Whenever you need a stack for any of the following projects, use the class
that Exercise 14 asks you to define.
OurStack
1.
Write a Java program that uses a stack to test whether an input string is a palindrome. Exercise 11 defines “palin-
drome” and asks you to describe a solution to this problem.
2.
Define a class
Postfix
that includes the static methods
convertToPostfix
and
evaluatePostfix
. These methods
should implement the algorithms given in Segments 5.16 and 5.18, respectively. Assume that the given algebraic
expressions are syntactically correct. The standard class
StringBuilder
, which is in the Java Class Library and is
described in Segment A.79 of Appendix A, will be helpful.
3.
Define and demonstrate a method that evaluates infix expressions using the algorithm given in Segment 5.21.
Assume that expressions are syntactically correct and use single-letter operands.
4.
Repeat the previous project, but remove the assumption that the expressions are syntactically correct.
5.
Consider the following algorithm to sort the entries in a stack S
1
. First create two empty stacks, S
2
and S
3
. At any
given time, stack S
2
will hold the entries in sorted order, with the smallest at the top of the stack. Move the top
entry of S
1
to S
2
. Pop and consider the top entry
t
of S
1
. Pop entries of stack S
2
and push them onto stack S
3
until
you reach the correct place to put
t
. Then push
t
onto S
2
. Next move all the entries from S
3
to S
2
.
a.
Write an iterative implementation of this algorithm.
b.
Consider the following revision of this algorithm. After moving the top entry of S
1
to S
2
, compare the new
top entry
t
of S
1
with the top entry of S
2
and the top entry of S
3
. Then either move entries from S
2
to S
3
or
from S
3
to S
2
until you locate the correct position for
t
. Push
t
onto S
2
. Continue until S
1
is empty. Finally,
move any entries remaining in S
3
to S
2
. Implement this revised algorithm.
6.
In the language Lisp, each of the four basic arithmetic operators appears before an arbitrary number of operands,
which are separated by spaces. The resulting expression is enclosed in parentheses. The operators behave as follows:
•
(+ a b c
...
)
returns the sum of all the operands, and
(+)
returns 0.
•
(- a b c
...
)
returns
a
-
b
-
c
-
..., and
(- a)
returns
-a
. The minus operator must have at least one
operand.
•
(* a b c
...
)
returns the product of all the operands, and
(*)
returns 1.
•
(/ a b c
...
)
returns
a
/
b
/
c
/
..., and
(/ a)
returns 1
/
a
. The divide operator must have at least
one operand.
You can form larger arithmetic expressions by combining these basic expressions using a fully parenthesized
prefix notation. For example, the following is a valid Lisp expression:
(+ (- 6) (* 2 3 4) (/ (+ 3) (*) (- 2 3 1)))
This expression is evaluated successively as follows:
(+ (- 6) (* 2 3 4) (/ 3 1 -2))
(+ -6 24 -1.5)
16.5
Design and implement an algorithm that uses a stack to evaluate a legal Lisp expression composed of the four
basic operators and integer values. Write a program that reads such expressions and demonstrates your algorithm.
