| | |
Given the stack of integers $\{7, 5\}$ , what does the stack look like after a call to "push" 8? Assume the left-most element is the top element of the stack.
The stack of integers $\{2, 9, 5, 8, 1, 3\}$ is "popped" twice. What is the value returned by the second "pop" operation? Assume the left-most element is the top element of the stack.
The stack of integers $\{41, 8\}$ undergoes the following operations, in the following order: "pop", "push 2", "push 15", "pop". What does the stack look like after all of these operations have been performed? Assume the left-most element is the top element of the stack.
Suppose that an intermixed sequence of stack push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence could not occur?
Suppose an intermixed sequence of stack push and pop operations are performed. The pushes push into the stack the integers 0 through 9 in order; popped values are printed in the order they are popped. Which of the below sequences could occur as the printed output?
(a) and (c) are possible; (b) and (d) are not.
What does the following code fragment print when $n$ is 50? In general, what does it do when presented with a positive integer n?
Stacks = new Stack (); while (n > 0) { s.push(n % 2); n = n / 2; } while (!s.isEmpty()) System.out.print(s.pop());
$110010$. In general, the code prints the binary version of the value $n$
Use the java.util.Stack class to write a ReverseStrings class that when executed reverses a sequence of strings from standard input.
import java.util.Scanner;
public class ReverseStrings {
public static void main(String[] args) {
System.out.println("Enter words (separated by spaces) to reverse:");
Scanner scanner = new Scanner(System.in);
String userInput = scanner.nextLine();
scanner.close();
scanner = new Scanner(userInput);
Stack stack = new Stack();
// The "<String>" suffix to "Stack" above tells the
// compiler that this will be a stack of String
// objects only (no other types of objects will
// be allowed to be pushed onto the stack). This
// is called a "type parameter" -- more is coming
// on these later...
while(scanner.hasNext()) {
stack.push(scanner.next());
}
scanner.close();
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
}
One can convert a number $n$ to a base $b$ using the following process:
As an example, to convert $1073$ to base $5$:
1073 = 214 * 5 + 3 214 = 42 * 5 + 4 42 = 8 * 5 + 2 8 = 1 * 5 + 3 1 = 0 * 5 + 1Thus, $1073$ written in base $5$ is $13243_5$.
Complete the program BaseChanger.java using a stack to implement this algorithm. For simplicity, you may assume that the program will only be used on bases between 2 and 10, inclusive.
Suppose a celebrity crashes a local party. He or she doesn't know anyone at the party, but everyone knows the celebrity. Suppose we have a list of the people at the party (including the celebrity), and a means to determine if any person $A$ knows any person $B$, where both $A$ and $B$ are people at the party. How can we use a stack to efficiently determine if a celebrity is present and -- when one is -- identify who that celebrity is?
To this end, complete the program Party.java using a stack, so that it behaves as suggested by the below sample run:
$ java Party↵
Celebrity ID = 2
Suppose one looks at any two people, say $A$ and $B$. If $A$ knows $B$, then $A$ can't be the celebrity and can be discarded from consideration, but $B$ could still be the celebrity. If $A$ doesn't know $B$, then $B$ can't be the celebrity and can be discarded from consideration, but $A$ could still be the celebrity. Now suppose you kept a stack of all people "under consideration"...
Use a stack to evaluate the postfix expression 1 2 + 3 4 * - 9 /. Write the state of the stack after each token (i.e., an operator or operand) is processed.
4
2 3 3 12 9
1 1 3 3 3 3 -9 -9 -1
=== === === === === === === === ===
The expression evaluates to -1
Use a stack to evaluate the postfix expression 2 6 1 - * 8 4 / - 3 *. Write the state of the stack after each token is processed. To what value does the expression evaluate?
1 4
6 6 5 8 8 2 3
2 2 2 2 10 10 10 10 8 8 24
=== === === === ==== ==== ==== ==== === === ====
The expression evaluates to 24
Use a stack to evaluate the postfix expression 1 5 + 7 3 - * 6 /. Write the state of the stack after each operator is processed. To what value does the expression evaluate?
4
6 6 24 4
=== === ==== ===
The expression evaluates to 4
Use two stacks (one for operands and one for operators) to evaluate the fully parenthesized infix expression ( ( 9 - 6 ) + ( ( 2 + 3 ) / 5 ) ). Write the state of both the operand and operator stacks after each token (i.e., operator, operand, or a single parenthesis) which results in at least one of the stacks changing is processed. To what value does the expression evaluate?
operand stack:
3 5
6 2 2 2 5 5 5 1
9 9 9 3 3 3 3 3 3 3 3 3 4
=== === === === === === === === === === === === ===
operator stack:
+ + / /
- - + + + + + + + +
=== === === === === === === === === === === === ===
The expression evaluates to 4
Use two stacks (one for operands and one for operators) to evaluate the fully parenthesized infix expression ( ( 5 * ( 1 + ( 4 - 2 ) ) ) / ( 6 / 2 ) ). Write the state of both the operand and operator stacks after each token (i.e., operator, operand, or a single parenthesis) which results in at least one of the stacks changing is processed. To what value does the expression evaluate?
operand stack:
2
4 4 4 2 2
1 1 1 1 1 1 3 6 6 6 3
5 5 5 5 5 5 5 5 5 15 15 15 15 15 15 5
=== === === === === === === === === ==== ==== ==== ==== ==== ==== ===
operator stack:
- -
+ + + + + / /
* * * * * * * * / / / / /
=== === === === === === === === === ==== ==== ==== ==== ==== ==== ===
The expression evaluates to 5
Use stack(s) to evaluate the fully parenthesized infix expression: ( ( 33 - 1 ) / ( ( 5 + ( 2 - 3 ) ) * 4 ) ). Write the state of the stack(s) after each token is processed. To what value does the expression evaluate?
operand stack:
3
2 2 2 -1 4
1 5 5 5 5 5 5 4 4 4 16
33 33 33 32 32 32 32 32 32 32 32 32 32 32 2 2
=== === === === === === === === === === === === === === === ===
operator stack:
- -
+ + + + + * *
- - / / / / / / / / / / /
=== === === === === === === === === === === === === === === ===
The expression evaluates to 2
Use a single stack to check if the delimiters match in the expression ( x ) ( a { b ( c ] d } e ) (which they don't). Indicate when and how you know that the delimeters don't match in this process, and what type of error exists.
(
{ {
( ( ( (
=== === === === === at this point we encounter a "]"
but this fails to match the top element on the stack
(so we have found a "matching error")
In using a stack to check delimiter matching, three different kinds of errors can occur. Give example expressions that would create each kind of error, and indicate which could result in stack underflow if things are not properly checked first.
answers vary. As one possibility: "a + [b * (c - d])" has mis-matched delimiters; "[a + (b - c)" is missing a right delimiter; "a + (b - c)]" is missing a left delimiter. This last case (missing left delimiter) can create a stack underflow error when a stack is used for delimiter checking and we fail to check to see if the stack is empty before attempting to pop the stack.
Write a class PostFixEvaluator that prompts the user for a postfix expression whose elements are separated by spaces, and then evaluates that expression, as suggested by the sample run below. Ensure support for the "+", "-", "*", "/", and "^" operators with operands of type double.
$ java PostFixEvaluator↵ Enter a postfix expression: 1 4 3 2 ^ * + 14.6 7.3 / -↵ 35.0
Write a class FullyParenthesizedInfixEvaluator that prompts the user for a fully parenthesized infix expression whose elements are separated by spaces, and then evaluates that expression, as suggested by the sample run below. Ensure support for the "+", "-", "*", "/", and "^" operators with operands of type double.
$ java FullyParenthesizedInfixEvaluator↵ Enter a fully parenthesized infix expression: ( ( ( ( 5 + 1 ) * 2 ) ^ 3 ) - ( 5.8 / 2.9 ) )↵ 1726.0
Write a class DelimeterChecker that prompts the user for a mathematical expression, which it then checks for balanced and properly nested parentheses, brackets, and curly braces. If no errors in the expression are found, a message to that effect is printed. Otherwise, the location of the error is shown along with a message indicating what kind of error occurred, as suggested by the following sample runs.
$ java DelimeterChecker↵ Enter an expression to check... [(1+2)*(3-4}]↵ [(1+2)*(3-4}] ^ Paired delimeters do not match An error was found
$ java DelimeterChecker↵ Enter an expression to check... {[(1+2)*4-1]↵ {[(1+2)*4-1] ^ Missing right delimiter An error was found
$ java DelimeterChecker↵ Enter an expression to check... (3*4)]^{3^4}↵ (3*4)]^{3^4} ^ Missing left delimiter An error was found
$ java DelimeterChecker↵ Enter an expression to check... (6/2)*{3^[4/(1+7)]}↵ No errors were found
If we implement a stack using a resizing array, when and how is the array resized?
double the size when full, halve the size when quarter full