Explain what modifications would be needed to make the parenthesis
matching algorithm check expressions with more kinds of
parentheses such as <>.
Complete the body of this method. You do not need to check the
precondition. You may use the CharStack class.
public static boolean balanced(String p)
// Precondition: Each character of p is '(', ')', '{' or '}'.
// Postcondition: The method returns true if the characters form a
// sequence of correctly balanced parentheses with each '(' matching
// a ')' and each '{' matching a '}'. Note that a sequence such as
// ( { ) } is NOT balanced because when we draw lines to match the
// parentheses to their partners, the lines cross each other. On the
// other hand, ( { } ) and { ( ) } are both balanced.
Short Answers
Section 6.3
Implementations of
the Stack ADT
|
I am going to execute this code with THREE pushes and ONE pop:
IntStack s = new IntStack( );
s.push(1);
s.push(2);
s.push(3);
System.out.println(s.pop( ));
Suppose that s is represented by a partially filled array. Draw the
state of the private instance variables of s after the above code:
_______ __________________________________
manyItems| | data| | | | | |
|_______| |______|______|______|______|______|...
[0] [1] [2] [3] [4]
I am going to execute this code with THREE pushes and ONE pop:
IntStack s = new IntStack( );
s.push(1);
s.push(2);
s.push(3);
System.out.println(s.pop( ));
Suppose that s is represented by a linked list. Draw the
state of the private member variables of s after the above code:
_______
head| |
|_______|
Short Answers
Section 6.4
More Complex
Stack Applications
|
Implement the following method. You may use the IntStack class and
the Stack operations of push, pop, peek, isEmpty, and size.
The parameter, in, is an EasyReader from Appendix B of the text and
it is already attached to some kind of input. You may use the methods:
in.isEOLN() -- returns true when the end of line is reached.
in.peek() -- returns the next input character without actually reading it.
in.ignore() -- reads and throws away the next input character.
in.intInput() -- reads and returns an integer value from the EasyReader. This should be used only if you know that the next input characters form
a valid integer value.
The method specification is:
public static int evaluatePostfix(EasyReader in)
// Precondition (Which is not checked): The next input line of in is a
// properly formed postfix expression consisting of integers,
// the binary operations + and -, and spaces.
// Postcondition: The method has read the next input line (including
// the newline) and returned the value of the postfix expression.
Consider the usual algorithm to convert an infix expression to a postfix
expression. Suppose that you have read 10 input characters during
a conversion and that the stack now contains these symbols:
| |
| + |
| ( |
bottom |___*___|
Now, suppose that you read and process the 11th symbol of the input.
Draw the stack for the case where the 11th symbol is:
A. A number:
B. A left parenthesis:
C. A right parenthesis:
D. A minus sign:
E. A division sign:
