import java.util.*;

public class InfixExpression { public static boolean hasBalancedParenthesis(String infix) { return false; } public static String getPostfixFromInfix(String infix) { return null; } public static int evaluatePostfix(String expr) { return 0; } public static int evaluateInfix(String infix) { return 0; } public static void main(String[] args) { System.out.println(evaluatePostfix("2 5 * 2 +")); System.out.println(evaluatePostfix("4 7 *")); System.out.println(getPostfixFromInfix("2 / ( 12 + 3 ) * 20")); System.out.println(evaluateInfix("2 / ( 12 + 3 ) * 20")); } }

import static org.junit.Assert.*; import org.junit.Test;

class InfixExpressionUnitTests {

@Test void balancedParens() { assertTrue(InfixExpression.hasBalancedParenthesis("(2 + 3)")); } @Test void evaluatePostfix() { assertEquals(28, InfixExpression.evaluatePostfix("4 7 *")); } @Test void evaluateInfixToPostfix() { assertEquals("4 7 *", InfixExpression.getPostfixFromInfix("4 * 7")); } @Test void evaluateInfix() { assertEquals(28, InfixExpression.evaluateInfix("4 * 7")); } }

Outcomes: Use Java's Collection classes (specifically, java.util.Stack) Implement algorithms that use a stack o Implement an algorithm to convert infix expressions into postfix expressions Implement an algorithm to evaluate postfix expressions Implement an algorithm to determine if the parentheses in an expression are balanced Develop JUnit tests O . Preliminaries: Review sections from Object-Oriented Data Structures Using Java, 4th Edition Chapter 2: Stacks The textbook's algorithm for balanced parentheses allows different types of brackets (e.g., [], 0), {}, and >). In this problem, we only consider (). Section 2.9 describes the algorithm for evaluating postfix expressions. The textbook's algorithm assumes the expression is correct; whereas, this project does not make that assumption. Evaluating a postfix expression . General requirements: Follow good programming practices. Format your code so that it is readable using generally accepted guidelines for formatting source code. Don't make code more complicated than it needs to be. If you find yourself repeating code, cutting and pasting code, etc, write a method to perform that task. Specific requirements: Implement the InfixExpression class that has the following methods: public class InfixExpression { public static boolean hasBalancedParenthesis(String infix) public static int evaluatePostfix(String postfix) public static string getPostfixFromInfix(String infix) public static int evaluateInfix(String infix) } (15 points) private static boolean hasBalancedParenthesis(String infix) returns true if the infix expression has balanced parentheses, and false otherwise. Use the algorithm described in videos for checking for balanced parentheses. You can ignore operators and numeric values when performing this operation. Use Java's Stack class to help in implementing this method. Some examples that have balanced parenthesis: o (2 + 3) + (3 + 4 + (5 + 6)) (((3) ) ) Some examples that are unbalanced: * * 0 o (2 + 3)) (3 + 4 + (5 * 6)) ((2 + 3) (3 + 4 + (5 + 6)) (((4 (20 points) public static int evaluate Postfix() returns the evaluation of the postfix expression. IllegalArgumentException is thrown if an operation is attempted without two numbers on the stack, or if there are more than one value remaining on the stack. Here are some examples of how the methods should operate: 2 3 * 4 + + 10 0 4 2 / 10 + 12 Here are cases that should result in an IllegalArgumentException being thrown: 1 2 3 + 2 + 2 (30 points) public static string getPostfixFromInfix(string infix) returns the trimmed, space-delimited postfix expression that corresponds to the given infix expression. This method throws an IllegalArgumentException if the infix expression has unbalanced parenthesis. For example, if the infix expression is "3 +4" then getPostfixFromInfix should return "3 4 +" The operands (numbers) will all be int values. The 5 valid operators are + -*/% (the % is the modulus operator, and has the same level of precedence as * and/). Exponentiation (i.e., ^) will not be included in the set of operators. Suggestions for parsing the infix expression: Java's String class has a split() method that you could use to convert your infix expression tokens into a string array. Once you have it in array form, converting to postfix will be more straightforward. Alternatively, Java's Scanner class can be used for parsing a string, by passing that string as a parameter to the Scanner constructor. The postfix expression should be returned with a single space separating each operand or operator from each adjacent operand or operator, and with no leading or trailing spaces. (15 points) public static int evaluateInfix(String infix) This method should evaluate the expression, returning the integer result of the calculation. For example, if the infix expression is "13 + 4" then evaluate() should return 17. Throw an IllegalArgumentException if the infix expression has an imbalance of parenthesis. All calculations should be integer calculations. So, for example, the value of the infix expression "7 / 2" should be 3, and not 3.5. Do not do anything special to handle dividing by 0 or computing modulus where the second operand is 0. Just let Java handle that the way that Java likes to handle that. a O Some notes about the infix expressions: The infix expressions will typically be legal, with one possible exception: parenthesis may be unbalanced. Unbalanced parenthesis will be the only way that an infix expression will be incorrect. You may assume that the expression is valid in all other ways. Some assumptions you should make: The only valid operators you will encounter are + - * / % are all at the highest precedence are all at the lowest precedence There may be parentheses ( ) All numbers will be integers (positive, negative, or zero) */% + o O Two consecutive numeric values will be separated by one of the operators. All tokens in the infix expression will be space-delimited. All our testing will be done with space-delimited expressions. That is, there will always be one or more spaces between numbers, operators, and parentheses. So, for example: We could test with this: ( 4 + -5 ) We could test with this: ( 4 -5 ) But we would not test with this: (4 + -5 ) And we would not test with this: 4+-5 1 1 + 1 Testing (20 points): You must test your InfixExpression class by adding tests to InfixExpressionUnitTests. The quality and thoroughness of your tests will be the primary factor when scoring your tests. Some things to consider: . Test hasBalancedParenthesis with both balanced and imbalanced expressions. Make sure that you try expressions with deeply nested parentheses. Test evaluatePostfix with both legal and illegal postfix expressions. Test getPostfixFromInfix with both balanced and unbalanced expressions. Test evaluateInfix with both balanced and unbalanced expressions. Here are a few examples you could use for testing, but you should create more examples on your own. Infix: 4 + 7 * 6 - 10 Postfix: 4 7 6 * + 10 Result: 36 Infix: ( 5 + 4) / ( 4 - 1) Postfix: 5 4 + 4 1 - / Result: 3 Infix: ( 5+ ( 4 Invalid 3 - 6 ) Infix: 10 % 3 + 4 Postfix: 10 3 % 4 + Result: 5 Infix expression: 10 + 2 % 3 Postfix: 10 2 3 % + Result: 12 Make up your own cases using this website and comparing results