EECS268:Lab4

NOTICE

The majority of these problem are classic recursive problems with lots of solutions online. Do yourself a favor, and DO NOT go seeking solutions. Instead, seek help from our staff. Your better off figuring it out on your own steam, maybe with some guidance from us. Also, looking up a solution and turning it in as your own is still cheating.

Due time

This lab is due before your next lab session begins

Overview

This lab will consist of several independent exercises (1 program per exercise) that must all use recursion to solve various problems.

Some problems will have fairly short solutions, but declaring and using classes/objects is still required.

Exercise 1: Recursive Parenthesis checker

Create a program that takes a sequence of parenthesis from the command line. Your program will indicate whether or not it’s a balanced set of parenthesis (matching left and right, not just an equal number).

Solutions must be recursive!

Example:

$>./parens “(())”

The sequence (()) is balanced

$>./parens “))((”

The sequence ))(( is not balanced

$>./parens “((((((()))))))”

The sequence ((((((())))))) is balanced

$>./parens “(()()()()()()()()()())”

The sequence (()()()()()()()()()()) is balanced

Exercise 2: String Permutations

Create a program that takes a string from the command line and prints every permutation of that string

You may assume the string will contain all unique characters.

CLARIFICATION: You may print the permutations in any order, as long as you print them all.

$>./perm dog

d

do

dog

dg

dgo

o

od

odg

og

ogd

g

gd

gdo

go

god

HINT: You may use a use a loop inside of your recursive definition

Exercise 3: Good Old Fibonacci

The Fibonacci sequence is a famous numerical series in which every number (after the first two) is the sum of the previous two numbers added together. The sequence is defined as…

F0=0

F1=1

Fi=Fi-1 + Fi-2

For your reference, here are the first few numbers in the Fibonacci sequence:

0,1,1,2,3,5,8,12,21,34,55,89

Create a program that takes an integer and a flag from the user. The flag will indicate one of two options:

• -i

• Short for “ith” where the user wants to know the ith Fibonacci number (note the lowest valid would be zero)

• -v

• Short for “verify” where the user wants to know if the number given is in the Fibonacci sequnence

Example runs:

$>./fib -i 2

1

$>./fib -i 8

21

$>./fib -i 36

14930352

$>./fib -v 7

7 is not in the sequence

$>./fib -v 75025

75025 is in the sequence

Exercise 4:Parenthesis Checker Strikes Back!

Create a program that supports checking for multiple symbols and determines if they are balanced. You must now support (parenthesis), [brackets], and {braces}.

They will contain filler text, but you don’t have worry about the meaning of the text. Your goal is to determine if the symbols are balanced or not.

Examples:

$>./harderChecker “{{((A+b)-xyz)addf}sss}”

The sequence {{((A+b)-xyz)addf}sss} is balanced

$>./harderChecker “{{((A+b)-xyz}addf)sss}”

The sequence {{((A+b)-xyz}addf)sss} is not balanced

Notice that parenthesis much match with parenthesis, brackets with brackets, and braces with braces.

Rubric

Your solutions must be recursive. Any solutions that do use recursive will receive a zero.

• [10pts] Exercise 1

• [20pts] Exercise 2

• [20pts] Exercise 3

• [20pts] Exercise 4

• [10pts] Code design

• [5pts] Clean output

• [5pts] Zero segfaults/crashes

• [10pts] Documentation

• Comments: Pre conditions, Post conditions, Return descriptions in header files. Not require for hpp/cpp files

• Formatting: Rational use of white space and indentation. Header and implementation files easily readable

Emailing Your Submission

Once you have created the tarball with your submission files, email it to your TA. The email subject line must look like “[EECS 268] SubmissionName”:

[EECS 268] Lab 0#

Note that the subject should be exactly like the line above. Do not leave out any of the spaces, or the bracket characters (“[” and “]”). In the body of your email, include your name and student ID.