This assignment has two parts. Part 1 is a practice of designing and implementing small recursive methods and Part 2 is an implementation of an application using the stack data structure.

Part 1 (40 points)

Create a file named RecursionPractice.java and implement the following two methods within the file.

(1). Write a recursive Java method named recursiveProduct that computes the product of two integers, m and n, using only additions and subtractions, as described below:

recursiveProduct (int m, int n)

Input: integers m and n

returns m * n

Note that m and n could be a negative number, 0, or a positive number. If you invoke the method with m = 10 and n = -20, the expected output is:

Recursive product: 10 times 20 is 200

(2). Write a recursive Java method named findFixedSumPairs that implements the following requirements:

Given an array of positive integers A and an integer k, the program prints every pair of integers in A, sum of which equals k.

Assume that all integers in A are distinct and they are sorted in the increasing order.

For example, suppose that you have the following main method in your program:

public static void main(String[] args) {

int[] a = {1, 5, 8, 11, 14, 15, 20, 23, 25, 28, 30, 34};

int k;

k = 43;

System.out.println(k = + k);

findFixedSumPairs(a, k);

}

Then, the output of your program should be:

Fixed sum: k = 43

a = [1, 5, 8, 11, 12, 14, 15, 20, 21, 22, 23, 25, 28, 30, 34, 36]

a[6] = 15, a[12] = 28 a[7] = 20, a[10] = 23

a[8] = 21, a[9] = 22

Note that the findFixedSumPairs itself is not a recursive method. You must write a separate, recursive method with additional parameters, which is invoked within the findFixedSumPairs method. Name this method recursiveFixedSumPairs. You need to determine appropriate input parameters of this method. The Section 5.4 in page 214 of the textbook discusses this issue. You may want to study this section.

An incomplete RecursionPractice.java code is posted on Blackboard. A main method is also written to test the above recursive methods. You need to complete the remaining part of RecursionPractice.java.

Part 2 (60 points)

You are required to write a Java program named InfixEvaluation.java that evaluates and produces the value of a given arithmetic expression using a stack data structure. For example, if the given expression is (2 + (5 * 3)), your program must produce 17. As another example, consider the expression ((4 2) * ((9 3) / 2)). Given this expression, your program must produce 6.

We make the following assumptions about the input expression:

• All operands are positive integers.
• Only the following operators are allowed: +, , *, and /
• Expression is fully parenthesized. In other words, each operator has a pair of ( and ) surrounding its two operands.

Your program must read a number of arithmetic expressions from an input file, named infix_expressions.txt, and produce an output. A sample input file is shown below:

( ( 2 + 5 ) * 3 )

( ( ( 3 + 2 ) * 3 ) ( 6 / 2 ) )

( ( ( 7 5 ) * 2 ) / ( 10 8 ) )

Each line has one arithmetic expression. Operands, operators, and parentheses are separated by a space(s). So, you can use a space, or spaces, as a delimiter when tokenizing an expression. The expected output for the above input is:

The value of ( ( 2 + 5 ) * 3 ) is 21

The value of ( ( ( 3 + 2 ) * 3 ) ( 6 / 2 ) ) is 12

The value of ( ( ( 7 5 ) * 2 ) / ( 10 8 ) ) is 2

Note that a given expression is repeated in the corresponding output. You must write the output on the screen.

A pseudocode is given below. You must implement this pseudocode.

Read an input expression from the input file, tokenize it, and store the tokens in a linear data structure, such as an array. Then, do the following for each expression.

Create two stacks one for operands and the other for operators

Scan the tokens in the linear data structure from left to right and perform the following:

• If a token is an operand, push it to the operand stack.
• If a token is an operator, push it to the operator stack.
• If a token is a right parenthesis, pop two operands from the operand stack and pop an operator from the operator stack and apply it to the operands. The result is pushed back to the operand stack.
• If a token is a left parenthesis, ignore it.
• After all tokens are processed, what is left in the operand stack is the result.

Repeat the same process for all expressions in the input file.

We assume that all expressions in the input file are valid (i.e., you dont need to check for invalid expressions).

For the two stacks, you must use the LinkedStack.java class that is included in the textbooks source code collection. You may not use Javas stack class or a stack class defined by somebody else. Note that you must not modify the LinkedStack.java class. Name your program as InfixEvaluation.java.

Documentation

No separate documentation is needed. However, you must include sufficient inline comments within your program.

Deliverables

You need to submit the following files:

• java
• java
• All other necessary files, including:

o LinkedStack.java o Stack.java o SinglyLinkedList.java o Other files, if any

Combine all files that are necessary to compile and run your program into a single archive file. Name the archive file LastName_FirstName_hw2.EXT, where EXT is an appropriate file extension, such as zip or rar. Then, upload it to Blackboard.