## Description

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 don’t need to check for

invalid expressions).

For the two stacks, you must use the LinkedStack.java class that is included in the textbook’s

source code collection. You may not use Java’s 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:

RecursionPractice.java

InfixEvaluation.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.

Grading

Part 1 – (1): Your facilitator will run your program with 3 different input pairs and 5 points will

be deducted for each wrong output.

Part 1 – (2): Your facilitator will run your program with three different k values and 5 points will

be deducted for each wrong output.

Part 2: Your program will be tested with 4 input expressions and 5 points will be deducted for each

wrong output.

Points will be deducted up to 20 points if your program does not have sufficient inline comments.