EECS268 : Lab4

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.