Sunday, 23 October 2011
4.14 - END
4_14. Compile class ArithmeticExpression. Create an instance using the exception example given in the table above "(a+B)". Run method isValid(). The method should return false.
4.14. Worked, done.
4_15. Edit method isValid(), to take care of the other 9 rules given in the table above. For each implementation check the method by using the exception example given in the table above.
4.15. I added some methods to help with the changes. This was quite a complicated task, but I believe I came up with good solutions to it.
public boolean isValid()
{
int numoperands = 0;
int numoperators = 0;
int numopen = 0;
HashSet Caseoperandset = new HashSet();
boolean tempIsValid=true;
if(!expression.substring(0,1).equals("(") || !expression.substring(0,1).equals(")"))
tempIsValid = false;
for (int i =0; i<expression.length();i++)
{
Character tempCharacter=new Character(expression.charAt(i));
boolean canTemp2 = i+1<expression.length();
if(canTemp2) { Character temp2 = new Character(expression.charAt(i+1));
if(!operatorSet.contains(tempCharacter) && !operandSet.contains(tempCharacter) && !bracketSet.contains(tempCharacter))
tempIsValid= false;
if(checkIfClosedParentheses(tempCharacter)) {
if(operandSet.contains(temp2) && canTemp2)
tempIsValid = false;
}
if(operatorSet.contains(tempCharacter)) {
numoperators++;
if(checkIfClosedParentheses(temp2) && canTemp2)
tempIsValid = false; }
if(operandSet.contains(tempCharacter)) {
numoperands++;
Caseoperandset.add(tempCharacter); }
if(checkIfOpenParentheses(temp2) && canTemp2)
{tempIsValid = false;}
if(checkIfOpenParentheses(tempCharacter))
numopen++; }
else
{
if(!operatorSet.contains(tempCharacter) && !operandSet.contains(tempCharacter) && !bracketSet.contains(tempCharacter))
tempIsValid= false;
if(operatorSet.contains(tempCharacter))
numoperators++;
if(operandSet.contains(tempCharacter)) {
numoperands++;
Caseoperandset.add(tempCharacter); }
if(checkIfOpenParentheses(tempCharacter))
numopen++;
}
}
if(checkParentheses(expression) || numoperands != numoperators+1 || numopen != numoperators || !checkIfConsecutiveOperands(Caseoperandset) || checkIfOperandsDouble(Caseoperandset))
tempIsValid = false;
return tempIsValid;
}
public boolean checkIfConsecutiveOperands(HashSet characters)
{
boolean Consecutive = true;
for(char c='a';c<=characters.size();c++)
{
if(!operandSet.contains(c))
Consecutive = false;
}//for
return Consecutive;
}
public boolean checkIfOperandsDouble(HashSet characters)
{
for(char c='a'; c<characters.size(); c++) {
for(char z='a'; c<characters.size(); z++)
{
if(c == z)
return true;
}
}
return false;
}
public static boolean checkIfOpenParentheses(Character c)
{
if(c.toString().equals("("))
return true;
else return false;
}
public static boolean checkIfClosedParentheses(Character c)
{
if(c.toString().equals(")"))
return true;
else return false;
}
public static boolean checkParentheses(String s) { //Mark Byers method to find whether parenthesis are equal by checking the nesting level.
int nesting = 0;
for (int i = 0; i < s.length(); ++i)
{
char c = s.charAt(i);
switch (c) {
case '(':
nesting++;
break;
case ')':
nesting--;
if (nesting < 0) {
return false;
}
break;
}
}
return nesting == 0;
}
4_16. What changes have to be made to modify class ArithmeticExpression to use double values rather than int values.
4.16. You would have to change all your int values into doubles (but not in your loops, i believe). This seems unnecessary for now; however, because everything seems to be working fine with ints.
4_17. When the user attempts to divide by zero, an "ArithmeticException (divide by zero)" error is thrown. The ArithmeticException class is part of the APCS Java Subset.
http://www.cs.duke.edu/csed/AP/subset/doc/index.html
Place a check in method evaluate() that catches this runtime error.
4.17. case '+': result=operand1+operand2; break;
case '*': result=operand1*operand2; break;
case '/': {if(operand1 == 0) {System.out.println("Cannot divide by zero."); return 0;} result=operand2/operand1; break;}
case '-': result=operand2-operand1; break;
Simply checked if it's zero. If it was a gave an error and set the case to 0.
4_18. Edit class ArithmeticExpression to include a method that converts the infix expression represented by the String expression to a postfix expression..
Public String infixToPostfix()
The algorithm for this method requires two stacks, one to build the postfix expression, and an auxiliary stack for temporarily holding operators.
Moving through the expression from the left.
Ignore open parentheses
Push operands on the "build" stack.
Push operators on the auxiliary stack.
On closed parentheses, pop the operator from the auxiliary stack and push it onto the "build" stack.
After processing all the characters in the expression String the "build" stack will contain the characters making up the postfix string in order from bottom to top of the stack.
Construct the postfix String (you can use the empty auxiliary to help) and return the postfix String.
4.18. Took a while... with a bit of help from Gershon's blog to find some of my compiling errors i finally got it:
public String infixToPostfix()
{
ArrayListStack operatorStack = new ArrayListStack();
String postfix = "";
for(int i=0;i<expression.length();i++)
{
char c = expression.charAt(i);
if(operandSet.contains(c))
postfix=postfix+Character.toString(c);
if(operatorSet.contains(c))
operatorStack.push(c);
if(Character.toString(c).equals(")"))
postfix = postfix + Character.toString((Character)operatorStack.pop()); //thanks to Gershon I found the casting issue that was bothering me for ages...
}
return postfix;
}
Sunday, 9 October 2011
4.10-4.13
4_10. The minimum number of moves for a one disk game is one, and for a two disk game three. Try to find a formula, in terms of the number of disks (n), which correctly expresses the minimum number of moves required to complete the game for any given (n).
4.10
f(n) = 2n-1 where n is the number of disks being played with.
4_11. Modify method play() so that the player is unable to place a larger disk on a smaller dsk.. Modify play() so that the game will only accept correct input from the user ('b,'g' or 'y').
4.11
public void play()
{
setUpPegs();
ArrayStack blue=new ArrayStack(maxPegs);
ArrayStack green=new ArrayStack(maxPegs);
ArrayStack yellow=new ArrayStack(maxPegs);
int difficulty;
SimpleInput inputDifficulty = new SimpleInput();
difficulty=inputDifficulty.getInt("How many disks would you like?");
for (int i=0;i<difficulty;i++)
{
disk temp=new disk(20,100-(i*10),0+(i*5),180-(i*20),"red",true);
blue.push(temp);
temp.makeVisible();
}//for
reDraw(blue,green,yellow);
while(!(blue.isEmpty() && green.isEmpty()))
{
char from, to;
SimpleInput moveCharacter = new SimpleInput();
from = moveCharacter.getChar("from: b=blue, g=green, y=yellow");
to = moveCharacter.getChar("to: b=blue, g=green, y=yellow");
disk carry=null;
switch (from)
{
case 'b': carry=(disk)blue.pop(); break;
case 'g': carry=(disk)green.pop();break;
case 'y': carry=(disk)yellow.pop();break;
default : System.out.println("error");
}//switch
switch (to)
{
case 'b': if(blue.peekTop() != null && ((disk)blue.peekTop()).getWidth()<carry.getWidth()){
System.out.println("Please put a smaller disk on a larger disk only."); }
else{
carry.changePosition(carry.getXPosition()%100,180-(stackHeight(blue)*20));
blue.push(carry); break; }
case 'g': if(green.peekTop() != null && ((disk)green.peekTop()).getWidth()<carry.getWidth()){
System.out.println("Please put a smaller disk on a larger disk only."); }
else{
carry.changePosition((carry.getXPosition()%100)+100,180-(stackHeight(green)*20));
green.push(carry); break; }
case 'y': if(yellow.peekTop() != null && ((disk)yellow.peekTop()).getWidth()<carry.getWidth()){
System.out.println("Please put a smaller disk on a larger disk only."); }
else{
carry.changePosition((carry.getXPosition()%100)+200,180-(stackHeight(yellow)*20));
yellow.push(carry); break; }
default : System.out.println("error");
}//switch
reDraw(blue,green,yellow);
}//while(main loop)
System.out.println("Well Done");
}//play
}//class TowersOfHanoi
4_12. Create a new class named TowersDemonstration which will prompt the user for the number of disks, as in TowersOfHanoi, but which will demonstrate the game by playing automatically. As you develop the algorithm for this class you should consider both iterative and recursive approaches.
There is a classic recursive solution to Towers of Hanoi. Try to find this solution for yourself, and then try to code the solution. If you have difficulty working out the solution for yourself, search for a solution on the web.
4.12
I tried integrating this step for a long time. I don't understand how to put the algorithm I found into the method... and I also can't understand where the method switch() came from (I looked through all the other classes and was unable to find it).
4_13. Compile class ArithmeticExpression. Create an instance of the class on the BlueJ workbench with a valid arithmetic expression String parameter. Execute the evaluate() method with the following expressions. Do you get the predicted results?
4.13
Yes, except for the last one. The expression was "(a/b)" where a = 1 and b = 0. I expected to get either "null" or a string message saying "undefined" (although Mr. Reid would argue "infinity" would be a more accurate message). Instead however, the program could not process the arithmetic expression and broke the method giving me an error. This could easily be coded into giving me either "null" or "undefined".
Sunday, 2 October 2011
4.6-4.9
4.6
public static String getReverse(String word)
{
String str = "";
for (int i = 0; i<word.length(); i++)
{
str += word.substring(word.length()-i-1, word.length()-i);
}
return str;
}//getReverse
//uses recursion to reverse word
public static String getReverseRecursive(String word)
{
if (word.length()==1)
{
return word;
}
else
{
String str = word.substring(word.length()-1) + getReverseRecursive(word.substring(0, word.length()-1));
return str;
}
}//getReverseRecursive
4.7
The advantage of using an iterative approach for me is the logic, it makes much more sense for me to go through something in a linear fashion, or rather simply not backwards as you do in recursion. On the other hand, using a recursive approach is much more efficient as it doesn't use any loops, and simple uses some commands and calls. Essentially, if you can think of the solution recursively it's much more effective, but it's very hard to do so for me, in respect with an iterative approach.
4.8
public static boolean isPalindrome(String word)
{
if(word.length()%2 == 0)
return(word.substring(0,word.length()/2) == getReverse(word.substring(word.length()/2, word.length())));
else return(word.substring(0,word.length()/2) == getReverse(word.substring(word.length()/2+1, word.length())));
}
}//class StringReverseDemo
4.9
I actually forgot the meaning of static and non-static, I'll ask about it in class.
4.1-4.5
4.1 Modified methods:
public Object pop()
{
if(stack[stackTop] == null)
System.out.println("Stack underflow, operation can not be completed");
Object temp = stack[stackTop];
stackTop--;
return temp;
}//pop
public Object peekTop()
{
if(stack[stackTop] == null)
System.out.println("Stack underflow, operation can not be completed");
return stack[stackTop];
}//peekTop
4.2
private boolean isFull()
{
int count = 0;
for(int i = 0; i<stack.length; i++)
{
if(stack[i] != null)
count++;
}
if(count == max)
return true;
else return false;
} // returns true if full, otherwise returns false.
4.3 Modified push() method:
public void push(Object x)
{
if(isFull()) {
System.out.println("Stack overflow, operation can not be completed");
return; }
stackTop++;
stack[stackTop]=x;
}//push
4.4 To be honest, I have no idea how to populate the ArrayStack in order to test it, and I'm coding out of pure logic, which so far seems to be working for me. I'll talk to you later about how to put in values for the Array in order to test it.
4.5
import java.util.ArrayList;
public class ArrayListStack implements Stack
{
private ArrayList stack;
private int stackTop;
public ArrayListStack()
{
stack = new ArrayList();
stackTop = -1;
}
public boolean isEmpty()
{
return (stackTop==-1);
}//isEmpty
public void push(Object x)
{
if(isFull()) {
System.out.println("Stack overflow, operation can not be completed");
return; }
stackTop++;
stack.get(stackTop) = x;
}//push
public Object pop()
{
if(stack.get(stackTop) == null)
System.out.println("Stack underflow, operation can not be completed");
Object temp = stack.get(stackTop);
stackTop--;
return temp;
}//pop
public Object peekTop()
{
if(stack.get(stackTop) == null)
System.out.println("Stack underflow, operation can not be completed");
return stack.get(stackTop);
}//peekTop
private boolean isFull()
{
int count = 0;
for(int i = 0; i<stack.length; i++)
{
if(stack.get(i) != null)
count++;
}
if(count == max)
return true;
else return false;
} // returns true if full, otherwise returns false.
}//ArrayStack
Subscribe to:
Posts (Atom)