JAVA

Lab #4 Stacks

Problem: Complete Exercises 5, 6, and 7 on pages 176 and 177..

Exercise 5: Describe SPECIFICALLY a. What value is displayed when the code executes? b. what mathematical function odes it evaluate?

Exercise 6: What value is displayed when the code executes?

Exercise 7: Convert the expressions from infix format to postfix format. Requirements:

You will submit the lab in written format ONLY, no coding is required.

:

FILES GIVEN FOR ASSIGNMENT:

:

**************************BalancedDelimiters************************

--------------------------------------------------------------------------------------------------------------------------

BalanceChecker.java

--------------------------------------------------------------------------------------------------------------------------

// Segment 5.10 /**  A class that checks whether the parentheses, brackets, and braces  in a string occur in left/right pairs.   @author Frank M. Carrano  @author Timothy M. Henry  @version 4.0 */ public class BalanceChecker { /** Decides whether the parentheses, brackets, and braces  in a string occur in left/right pairs.  @param expression A string to be checked.  @return True if the delimiters are paired correctly. */  public static boolean checkBalance(String expression) { StackInterface openDelimiterStack = new ArrayStack<>(); int characterCount = expression.length(); boolean isBalanced = true; int index = 0; char nextCharacter = ' '; while (isBalanced && (index < characterCount)) { nextCharacter = expression.charAt(index); switch (nextCharacter) { case '(': case '[': case '{': openDelimiterStack.push(nextCharacter); break; case ')': case ']': case '}': if (openDelimiterStack.isEmpty()) isBalanced = false; else { char openDelimiter = openDelimiterStack.pop(); isBalanced = isPaired(openDelimiter, nextCharacter); } // end if break; default: break; // Ignore unexpected characters } // end switch index++; } // end while if (!openDelimiterStack.isEmpty()) isBalanced = false; return isBalanced; } // end checkBalance // Returns true if the given characters, open and close, form a pair // of parentheses, brackets, or braces. private static boolean isPaired(char open, char close) { return (open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}'); } // end isPaired } // end BalanceChecker 

--------------------------------------------------------------------------------------------------------------------------

Driver.java

--------------------------------------------------------------------------------------------------------------------------

/**  A driver that demonstrates the class BalanceChecker.   @author Frank M. Carrano  @author Timothy M. Henry  @version 4.1 */ public class Driver { public static void main(String[] args) { testBalance("a {b [c (d + e)/2 - f] + 1}"); // Seg. 5.10 testBalance("[a {b / (c - d) + e/(f + g)} - h]"); // Question 3a (Chapter 5) testBalance("{a [b + (c + 2)/d ] + e) + f }"); // Question 3b testBalance("[a {b + [c (d+e) - f ] + g}"); // Question 3c System.out.println(" Done."); } // end main public static void testBalance(String expression) { boolean isBalanced = BalanceChecker.checkBalance(expression); if (isBalanced) System.out.println(expression + " is balanced"); else System.out.println(expression + " is not balanced"); } // end testBalance } // end Driver /* a {b [c (d + e)/2 - f] + 1} is balanced [a {b / (c - d) + e/(f + g)} - h] is balanced {a [b + (c + 2)/d ] + e) + f } is not balanced [a {b + [c (d+e) - f ] + g} is not balanced Done. */ 

************************InfixExpressions************************

--------------------------------------------------------------------------------------------------------------------------

Infix.java

--------------------------------------------------------------------------------------------------------------------------

/**  A class that evaluates an infix expression.  Based on pseudocode in Segment 5.21.  @author Frank M. Carrano  @author Timothy M. Henry  @version 4.0 */ public class Infix { public static double evaluateInfix(String infix) { Double operandOne, operandTwo, result; Character top; char topOperator; StackInterface operatorStack = new ArrayStack<> (); StackInterface valueStack = new ArrayStack<>(); int characterCount = infix.length(); for (int index = 0; index < characterCount; index++) { char nextCharacter = infix.charAt(index); switch(nextCharacter) { case 'a': case 'b': case 'c': case 'd': case 'e': valueStack.push(valueOf(nextCharacter)); break; case '(': case '^': operatorStack.push(nextCharacter); break; case ')': // Stack is not empty if infix expression is valid top = operatorStack.pop(); topOperator = top.charValue(); while (topOperator != '(') { operandTwo = valueStack.pop(); operandOne = valueStack.pop(); result = compute(operandOne, operandTwo, topOperator); valueStack.push(result); top = operatorStack.pop(); topOperator = top.charValue(); } // end while break; case '+': case '-': case '*': case '/': boolean done = false; while (!operatorStack.isEmpty() && !done) { top = operatorStack.peek(); topOperator = top.charValue(); if (precedence(nextCharacter) <= precedence(topOperator) ) { operatorStack.pop(); operandTwo = valueStack.pop(); operandOne = valueStack.pop(); result = compute(operandOne, operandTwo, topOperator); valueStack.push(result); } else done = true; } // end while operatorStack.push(nextCharacter); break; default: break; // Ignore unexpected characters } // end switch } // end for while (!operatorStack.isEmpty()) { top = operatorStack.pop(); topOperator = top.charValue(); operandTwo = valueStack.pop(); operandOne = valueStack.pop(); result = compute(operandOne, operandTwo, topOperator); valueStack.push(result); } // end while result = valueStack.peek(); return result.doubleValue(); } // end evaluateInfix private static int precedence(char operator) { switch (operator) { case '(': case ')': return 0; case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; } // end switch return -1; } // end precedence private static double valueOf(char variable) { switch (variable) { case 'a': return 2.0; case 'b': return 3.0; case 'c': return 4.0; case 'd': return 5.0; case 'e': return 6.0; } // end switch return 0; } // end valueOf private static Double compute(Double operandOne, Double operandTwo, char operator) { double result; switch (operator) { case '+': result = operandOne.doubleValue() + operandTwo.doubleValue(); break; case '-': result = operandOne.doubleValue() - operandTwo.doubleValue(); break; case '*': result = operandOne.doubleValue() * operandTwo.doubleValue(); break; case '/': result = operandOne.doubleValue() / operandTwo.doubleValue(); break; case '^': result = Math.pow(operandOne.doubleValue(), operandTwo.doubleValue()); break; default: // Unexpected character result = 0; break; } // end switch return result; } // end compute } // end Infix 

--------------------------------------------------------------------------------------------------------------------------

Driver.java

--------------------------------------------------------------------------------------------------------------------------

/**  A driver that demonstrates the class Infix.   @author Frank M. Carrano  @author Timothy M. Henry  @version 4.1 */ public class Driver { public static void main(String[] args) { System.out.println("Testing infix expressions with " + "a = 2, b = 3, c = 4, d = 5 "); testInfix("a+b"); testInfix("(a + b) * c"); testInfix("a * b / (c - d)"); testInfix("a / b + (c - d)"); testInfix("a / b + c - d"); testInfix("a^b^c"); testInfix("(a^b)^c"); testInfix("a*(b/c+d)"); System.out.println(" Done."); } // end main public static void testInfix(String infixExpression) { System.out.println("Infix: " + infixExpression); System.out.println("Value: " + Infix.evaluateInfix(infixExpression)); System.out.println(" "); } // end testInfix } // end Driver /* Testing infix expressions with a = 2, b = 3, c = 4, d = 5 Infix: a+b Value: 5.0 Infix: (a + b) * c Value: 20.0 Infix: a * b / (c - d) Value: -6.0 Infix: a / b + (c - d) Value: -0.33333333333333337 Infix: a / b + c - d Value: -0.33333333333333304 Infix: a^b^c Value: 2.4178516392292583E24 Infix: (a^b)^c Value: 4096.0 Infix: a*(b/c+d) Value: 11.5 Done. */ 

*******************PostfixExpressions**********************

--------------------------------------------------------------------------------------------------------------------------

Postfix.java

--------------------------------------------------------------------------------------------------------------------------

/**  A class that represents a postfix expression.  Based on pseudocode in Segments 5.16 and 5.18.   @author Frank M. Carrano  @author Timothy M. Henry  @version 4.0 */ public class Postfix { /** Creates a postfix expression that represents a given infix expression.  Segment 5.16.  @param infix A string that is a valid infix expression.  @return A string that is the postfix expression equivalent to infix. */  public static String convertToPostfix(String infix) { StackInterface operatorStack = new LinkedStack<>(); StringBuilder postfix = new StringBuilder(); int characterCount = infix.length(); char topOperator; for (int index = 0; index < characterCount; index++) { boolean done = false; char nextCharacter = infix.charAt(index); if (isVariable(nextCharacter)) postfix = postfix.append(nextCharacter); else { switch (nextCharacter) { case '^': operatorStack.push(nextCharacter); break; case '+': case '-': case '*': case '/': while (!done && !operatorStack.isEmpty()) { topOperator = operatorStack.peek(); if (getPrecedence(nextCharacter) <= getPrecedence(topOperator)) { postfix = postfix.append(topOperator); operatorStack.pop(); } else done = true; } // end while operatorStack.push(nextCharacter); break; case '(': operatorStack.push(nextCharacter); break; case ')': // Stack is not empty if infix expression is valid topOperator = operatorStack.pop(); while (topOperator != '(') { postfix = postfix.append(topOperator); topOperator = operatorStack.pop(); } // end while break; default: break; // Ignore unexpected characters } // end switch } // end if } // end for while (!operatorStack.isEmpty()) { topOperator = operatorStack.pop(); postfix = postfix.append(topOperator); } // end while return postfix.toString(); } // end convertToPostfix // Indicates the precedence of a given operator. // Precondition: operator is a character that is (, ), +, -, *, /, or ^. // Returns an integer that indicates the precedence of operator: // 0 if ( or ), 1 if + or -, 2 if * or /, 3 if ^, // -1 if anything else. */ private static int getPrecedence(char operator) { switch (operator) { case '(': case ')': return 0; case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; } // end switch return -1; } // end getPrecedence private static boolean isVariable(char character) { return Character.isLetter(character); } // end isVariable /** Evaluates a postfix expression.  Segment 5.18  @param postfix a string that is a valid postfix expression.  @return the value of the postfix expression. */  public static double evaluatePostfix(String postfix) { StackInterface valueStack = new LinkedStack<>(); int characterCount = postfix.length(); for (int index = 0; index < characterCount; index++) { char nextCharacter = postfix.charAt(index); switch(nextCharacter) { case 'a': case 'b': case 'c': case 'd': case 'e': valueStack.push(valueOf(nextCharacter)); break; case '+': case '-': case '*': case '/': case '^': Double operandTwo = valueStack.pop(); Double operandOne = valueStack.pop(); Double result = compute(operandOne, operandTwo, nextCharacter); valueStack.push(result); break; default: break; // Ignore unexpected characters } // end switch } // end for return (valueStack.peek()).doubleValue(); } // end evaluatePostfix private static double valueOf(char variable) { switch (variable) { case 'a': return 2.0; case 'b': return 3.0; case 'c': return 4.0; case 'd': return 5.0; case 'e': return 6.0; } // end switch return 0; // Unexpected character } // end valueOf private static Double compute(Double operandOne, Double operandTwo, char operator) { double result; switch (operator) { case '+': result = operandOne.doubleValue() + operandTwo.doubleValue(); break; case '-': result = operandOne.doubleValue() - operandTwo.doubleValue(); break; case '*': result = operandOne.doubleValue() * operandTwo.doubleValue(); break; case '/': result = operandOne.doubleValue() / operandTwo.doubleValue(); break; case '^': result = Math.pow(operandOne.doubleValue(), operandTwo.doubleValue()); break; default: // Unexpected character result = 0; break; } // end switch return result; } // end compute } // end Postfix 

--------------------------------------------------------------------------------------------------------------------------

Driver.java

--------------------------------------------------------------------------------------------------------------------------

/**  A driver that demonstrates the class Postfix.   @author Frank M. Carrano  @author Timothy M. Henry  @version 4.1 */ public class Driver { public static void main(String[] args) { System.out.println("Testing postfix expressions with " + "a = 2, b = 3, c = 4, d = 5, e = 6 "); testPostfix("a+b"); testPostfix("(a + b) * c"); testPostfix("a * b / (c - d)"); testPostfix("a / b + (c - d)"); testPostfix("a / b + c - d"); testPostfix("a^b^c"); testPostfix("(a^b)^c"); testPostfix("a*(b/c+d)"); System.out.println("Testing Question 6, Chapter 5: "); testPostfix("(a+b)/(c-d)"); // Question 6a, Chapter 5 testPostfix("a/(b-c)*d"); // Question 6b testPostfix("a-(b/(c-d)*e+f)^g"); // Question 6c testPostfix("(a-b*c)/(d*e^f*g+h)"); // Question 6d System.out.println("Testing Question 7, Chapter 5: "); System.out.println("Q7a: ae+bd-/ : " + Postfix.evaluatePostfix("ae+bd-/") + " "); System.out.println("Q7b: abc*d*- : " + Postfix.evaluatePostfix("abc*d*-") + " "); System.out.println("Q7c: abc-/d* : " + Postfix.evaluatePostfix("abc-/d*") + " "); System.out.println("Q7d: ebca^*+d- : " + Postfix.evaluatePostfix("ebca^*+d-") + " "); System.out.println(" Done."); } // end main public static void testPostfix(String infixExpression) { System.out.println("Infix: " + infixExpression); String postfixExpression = Postfix.convertToPostfix(infixExpression); System.out.println("Postfix: " + postfixExpression); System.out.println(" "); } // end testPostfix } // end Driver /* Testing postfix expressions with a = 2, b = 3, c = 4, d = 5, e = 6 Infix: a+b Postfix: ab+ Infix: (a + b) * c Postfix: ab+c* Infix: a * b / (c - d) Postfix: ab*cd-/ Infix: a / b + (c - d) Postfix: ab/cd-+ Infix: a / b + c - d Postfix: ab/c+d- Infix: a^b^c Postfix: abc^^ Infix: (a^b)^c Postfix: ab^c^ Infix: a*(b/c+d) Postfix: abc/d+* Testing Question 6, Chapter 5: Infix: (a+b)/(c-d) Postfix: ab+cd-/ Infix: a/(b-c)*d Postfix: abc-/d* Infix: a-(b/(c-d)*e+f)^g Postfix: abcd-/e*f+g^- Infix: (a-b*c)/(d*e^f*g+h) Postfix: abc*-def^*g*h+/ Testing Question 7, Chapter 5: Q7a: ae+bd-/ : -4.0 Q7b: abc*d*- : -58.0 Q7c: abc-/d* : -10.0 Q7d: ebca^*+d- : 49.0 Done. */ 

***************** Segment 5.4 *************************

--------------------------------------------------------------------------------------------------------------------------

Driver.java

--------------------------------------------------------------------------------------------------------------------------

/**  A driver that demonstrates a stack,  as done in Example 5.4.   @author Frank M. Carrano  @author Timothy M. Henry  @version 4.0 */ public class Driver { public static void main(String[] args) { StackInterface myStack = new ArrayStack<>(); myStack.push("Jim"); myStack.push("Jess"); myStack.push("Jill"); myStack.push("Jane"); myStack.push("Joe"); String top = myStack.peek(); // returns "Joe" System.out.println(top + " is at the top of the stack."); top = myStack.pop(); // removes and returns "Joe" System.out.println(top + " is removed from the stack."); top = myStack.peek(); // returns "Jane" System.out.println(top + " is at the top of the stack."); top = myStack.pop(); // removes and returns "Jane" System.out.println(top + " is removed from the stack."); System.out.println("Done."); } // end main } // end Driver /* Joe is at the top of the stack. Joe is removed from the stack. Jane is at the top of the stack. Jane is removed from the stack. Done. */