3. Simulate the action of the algorithm for checking delimiters for each of the
ID: 3666521 • Letter: 3
Question
3. Simulate the action of the algorithm for checking delimiters for each of the following
strings by showing the contents of the stack at each point. Do not write code.
a. {[A+B]-[(C-D)] b. ((H) * {([J+K])})
4. Write code to determine whether an input character string is of the form
xCy
where x is a string consisting of the letters ‘A’ and ‘B’ and y is the reverse of the x (i.e. if x=”ABABBA” then y must equal “ABBABA”, eg. ABABBACABBABA). At each point you may read only the next character in the string.
5. Write code to determine whether an input character string is of the form
A D bD cD ... Dz
Where each string a, b, ...z is of the form of the string define in Exercise 4. (Thus a string is in the proper form if it consists of any number of such strings separated by the character ‘D’, e.g. ABBCBBADACADBABCBABDAABACABAA.) At each point you may read only the next character in the string, i.e. you must process the string on a left to right basis. You may not use string functions.
6. Design and implement a stack in Java in which each item on the stack is a varying number of integers. Choose a Java data structure to implement your stack and design push and pop methods for it. You may not use library functions.
7. Consider a language that does not have arrays but does have stacks as a data type. That is, one can declare
stack s;
The push, pop, empty, and peek operations are defined. Write code to show how a one- dimensional array can be implemented by using these operations on two stacks. You need to start by thinking in terms of the operations we do on arrays.
8. Design a method for keeping two stacks within a single linear array s[SPACESIZE] so that neither stack overflows until all of memory is used and an entire stack is never shifted to a different location within the array. Write Java methods push1, push2, pop1, and pop2 to manipulate the two stacks. (Hint: the two stacks grow toward each other.)
9. Transform each of the following expressions to prefix and postfix. Do not write code.
a. (A+B)*(C$(D-E)+F)-G
b. A+(((B-C)*(D-E)+F)/G)$(H-J)
10. Transform each of the following expressions to infix. Do not write code.
a. ++A-*$BCD/+EF*GHI b. +-$ABC*D**EFG
c. AB-C+DEF-+$
d. ABCDE-+$*EF*-
11. Apply the evaluation algorithm in the text to evaluate the following postfix expressions. Do not write code. Assume A=1, B=2, and C=3.
a. AB+C-BA+C$-
b. ABC+*CBA-+*
12. Write a prefix method to accept an infix string and create the prefix form of that string, assuming that the string is read from right to left and that the prefix string is created from right to left.
Explanation / Answer
6.)
instruction to use and run the code :
1) copy the codes here as separate .java files (the ===== lines mark the boundaries of the codes). To test use the QueueTest and StackTest . They further have comments about what is happening in each steps.
================== STACK CODE ============
import java.util.Arrays;
public class StackUC<T> {
private int maxSize;
private T[] stack;
private int top;
public StackUC(int size) {
maxSize = size;
stack = (T[])new Object[maxSize];
top = -1;
}
public void push(T element) {
if(top==maxSize-1) {
throw new IllegalStateException("Stack is full, cant push anymore elements");
}else{
stack[++top] = element;
}
}
public T pop() {
if(isEmpty()) {
throw new IllegalStateException("Stack is empty, cant pop anymore elements");
}else{
T value = stack[top];
top--;
return value;
}
}
public T peek() {
return stack[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
@Override
public String toString() {
return "Stack: "+ Arrays.toString(stack);
}
}
==
============================= STACK TEST ======
public class StackTest {
public static void main(String args[]){
//String test
StackUC<String> ss = new StackUC<String>(2);
ss.push("a");
ss.push("b");
System.out.println(ss.toString()); //print the stack elements
ss.pop(); // should pop out "b" from stack
System.out.println(ss.pop()); //should print a as stack follows LIFO - last in first out
//Integer test
StackUC<Integer> stack = new StackUC<Integer>(5);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
System.out.println(stack.toString());
stack.pop(); // will pop out 8
System.out.println(stack.pop()); // will pop out 7
System.out.println(stack.pop()); // will pop out 6
// negative test keeping it commented
//stack.push(6); // will throw an stack full error as the max limit is crossed - which is valid
}
}
===========
9
POSTFIX
a) A B + C$ D E - F + * G -
b) A B C - D E - * F + G / $ H J - +
10.
c) AB-C+DEF-+$
d) (A * (B $ (C + (D - E)))) - (E*F)
11
a)
AB+C-BA+C$-
1 2 + 3 - 2 1 + 3 $ -
+
2
1
--------
-
3
1+2
-------
+
1
2
3-3
-------
-
$
3
2+1
-----------
3 - 3
------------
= 0
b)
ABC+*CBA-+*
1 2 3 + * 1 2 3 - + *
= 0
===================
12)
import java.util.Stack;
public class Converter {
public static void main(String args[]){
String infix = "((a+b)*(z+x))";
System.out.println("Prefix : " + printPreFix(infix));
}
public static String printPreFix(String str){
Stack stack = new Stack();
String prefix = "";
for(int i=str.length()-1;i>=0;i--){
char c = str.charAt(i);
if(Character.isLetter(c)){
prefix = ((Character)c).toString() + prefix;
}
else if(c == '('){
prefix = ((Character)stack.pop()).toString() + prefix;
}
else if(c == ')'){
continue;
}
else{
stack.push(c);
}
}
return prefix;
}
}
=======
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.