Algorithms and OOD (CSC 207 2013F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Java 7 API] [Java Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2013S (Walker)] [CSC 207 2011S (Weinman)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Summary: In this laboratory, you will have an opportunity to ground your understanding of stacks, particularly of the array-based implementation of stacks.
Required Code Files:https://github.com/Grinnell-CSC207/linear
a. Review the reading on linear structures.
b. Review the reading on stacks.
c. Fork and clone the repo at https://github.com/Grinnell-CSC207/linear
Read through LSExpt.java
and LinkedStackExpt
.
Summarize what the stack should look like at each step. (A piece of
paper might help.) Note that the info
method will print
information on the stack (is it empty? is it full? what elements are
in the stack) and the clear
method will repeatedly call
get
until the stack is empty.
Run LinkedStackExpt
and see if you get the output that
you expect.
Skim through ReportingLinearStructure.java
. Summarize
the main approach of the class. What ideas from the class might you
apply in other situations? (Pick at least one or two.)
The file ArrayBasedStack.java
has a significant bug.
Identify and correct that bug.
One useful application of stacks is matching things. For example, we can match the parens in a Scheme expression as follows:
Step through the characters in the expression
When you encounter an open paren or open square bracket, push it
on the stack
When you encounter a close paren or close square bracket, pop
the corresponding opening character off the stack. If the two
characters don't match, issue an error.
If you encounter a closing character with an empty stack, that
close paren or bracket is mismatched.
If the stack is not empty, there are unmatched open or closed parens.
Implement this algorithm. (You might also add support for braces and
angle brackets.) That is, write and experiment with a method,
checkMatching(String str)
, that checks whether the
parens, square brackets, and potentially other characters, match
correctly.
Revise your answer from the previous exercise to store the indices of matching symbols. That is, you will need to push both symbol and index. Use the indices to provide better error messages (e.g., you can say where the mismatch occurs in the string).
How can you store two kinds of values in stack? One option is to make it a stack of Objects, and alternately push Character and Integer objects. Another option is to create a simple class that groups a character and an integer.
Extend your answer from the previous extra problem to provide a nice picture of the matching parens. For example, for each pair of matching parens, you might draw a line underneath, as in the following.
(oh (boy) (I am having) ((so) much) fun matching (parens)) +---+ +-----------+ +--+ +---------+ +------+ +--------------------------------------------------------+
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Java 7 API] [Java Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2013S (Walker)] [CSC 207 2011S (Weinman)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Copyright (c) 2013 Samuel A. Rebelsky.
This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this
license, visit http://creativecommons.org/licenses/by/3.0/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.