Data structure and alogorithm

/** @file assg09-tests.cpp * @brief Unit tests for Assignment 09 using stacks. * * @author Jane Programmer * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 09 * @date June 1, 2020 * * Assignment 09 using stacks. Use the given Stack ADT to implement a set of * functions/algorithms. This file has catch2 unit tests you need to test and * implement the functions for your assignment. */ #define CATCH_CONFIG_MAIN #include "catch.hpp" #include "Stack.hpp" #include "assg09-stackfun.hpp" using namespace std; /** test doParenthesisMatch() functions. This is the first function * you are to implement for this assignment. */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the some doParenthesisMatch() function. TEST_CASE("<doParenthesisMatch()> test doParenthesismatch function", "[function]") { // by definition an empty expression should be considered as balanced. // Does your function handle an empty expression correctly? CHECK( doParenthesisMatch("") ); // test balanced expressions, from simple cases to more complex ones. // All of these match so the function should return true for all of them CHECK( doParenthesisMatch("()") ); CHECK( doParenthesisMatch("()()") ); CHECK( doParenthesisMatch("(())") ); CHECK( doParenthesisMatch("(())((()))") ); CHECK( doParenthesisMatch("(()((())))") ); CHECK( doParenthesisMatch("((((()))(()((()))))()(()))") ); // now test detects unbalanced expressions CHECK_FALSE( doParenthesisMatch("(") ); CHECK_FALSE( doParenthesisMatch(")") ); CHECK_FALSE( doParenthesisMatch("()(") ); CHECK_FALSE( doParenthesisMatch("(()))") ); CHECK_FALSE( doParenthesisMatch("((()(())())") ); CHECK_FALSE( doParenthesisMatch("((((()))(()((())))()(()))") ); } */ /** test decodeIDSequence() functions. */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the some decodeIDSequence() function. TEST_CASE("<decodeIDSequence()> test decodeIDSequence function", "[function]") { // the empty squence should return simply 1 as the sequence CHECK( decodeIDSequence("") == "1" ); // simple cases of only I increase CHECK( decodeIDSequence("I") == "12" ); CHECK( decodeIDSequence("II") == "123" ); CHECK( decodeIDSequence("III") == "1234" ); CHECK( decodeIDSequence("IIIIII") == "1234567" ); // simple cases of only D decrease CHECK( decodeIDSequence("D") == "21" ); CHECK( decodeIDSequence("DD") == "321" ); CHECK( decodeIDSequence("DDDD") == "54321" ); CHECK( decodeIDSequence("DDDDDDD") == "87654321" ); // general case with mixed I and D increases and decreases CHECK( decodeIDSequence("ID") == "132" ); CHECK( decodeIDSequence("DI") == "213" ); CHECK( decodeIDSequence("IDIDII") == "1325467" ); CHECK( decodeIDSequence("IIDDIDID") == "125437698" ); CHECK( decodeIDSequence("IDIDDIDIIIIDDDDIDDIII") == "13265487910111615141312191817202122" ); } */ /** test insertItemOnSortedStack() functions. */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the some insertItemOnSortedStack() function. TEST_CASE("<insertItemOnSortedStack()> test insertItemOnSorted function", "[function]") { // stacks should be sorted in descending order, highest value on top of stack LStack<int> istack; // test on an emtpy stack insertItemOnSortedStack(4, istack); int exp1[] = {4}; AStack<int> stackExp1(exp1, 1); CHECK( istack == stackExp1 ); // test insert on top of stack insertItemOnSortedStack(7, istack); int exp2[] = {4, 7}; AStack<int> stackExp2(exp2, 2); CHECK( istack == stackExp2 ); // test insert on bottom of stack insertItemOnSortedStack(2, istack); int exp3[] = {2, 4, 7}; AStack<int> stackExp3(exp3, 3); CHECK( istack == stackExp3 ); // test insert somewhere on stack insertItemOnSortedStack(6, istack); int exp4[] = {2, 4, 6, 7}; AStack<int> stackExp4(exp4, 4); CHECK( istack == stackExp4 ); // test insert somewhere on stack insertItemOnSortedStack(3, istack); int exp5[] = {2, 3, 4, 6, 7}; AStack<int> stackExp5(exp5, 5); CHECK( istack == stackExp5 ); // repeat but use a stack of strings. // also we'll use an AStack for the test stack, and LStack for expected AStack<string> sstack; // test on an emtpy stack string item = "foxtrot"; insertItemOnSortedStack(item, sstack); string exp6[] = {"foxtrot"}; LStack<string> stackExp6(exp6, 1); CHECK( sstack == stackExp6 ); // test insert on top of stack item = "whisky"; insertItemOnSortedStack(item, sstack); string exp7[] = {"foxtrot", "whisky"}; LStack<string> stackExp7(exp7, 2); CHECK( sstack == stackExp7 ); // test insert on bottom of stack item = "alpha"; insertItemOnSortedStack(item, sstack); string exp8[] = {"alpha", "foxtrot", "whisky"}; LStack<string> stackExp8(exp8, 3); CHECK( sstack == stackExp8 ); // test insert somewhere on stack item = "charlie"; insertItemOnSortedStack(item, sstack); string exp9[] = {"alpha", "charlie", "foxtrot", "whisky"}; LStack<string> stackExp9(exp9, 4); CHECK( sstack == stackExp9 ); // test insert somewhere on stack item = "romeo"; insertItemOnSortedStack(item, sstack); string exp10[] = {"alpha", "charlie", "foxtrot", "romeo", "whisky"}; LStack<string> stackExp10(exp10, 5); CHECK( sstack == stackExp10 ); } */ /** test sortStack() functions. */ /* uncomment the test cases 1 at a time. This test case tests implementation * of the some sortStack() function. TEST_CASE("<sortStack()> test sortStack function", "[function]") { // sort an empty stack LStack<int> istack; sortStack(istack); AStack<int> stackExp1; CHECK( istack == stackExp1 ); // sort stack with single item istack.push(5); sortStack(istack); int exp2[] = {5}; AStack<int> stackExp2(exp2, 1); CHECK( istack == stackExp2 ); // sort already sorted stacks istack.push(7); istack.push(9); istack.push(11); sortStack(istack); int exp3[] = {5, 7, 9, 11}; AStack<int> stackExp3(exp3, 4); CHECK( istack == stackExp3 ); // add items out of order and sort istack.push(1); istack.push(15); istack.push(6); istack.push(8); istack.push(11); sortStack(istack); int exp4[] = {1, 5, 6, 7, 8, 9, 11, 11, 15}; AStack<int> stackExp4(exp4, 9); CHECK( istack == stackExp4 ); // sort a stack that is in reverse order istack.clear(); istack.push(15); istack.push(11); istack.push(9); istack.push(7); istack.push(6); istack.push(4); istack.push(3); istack.push(1); sortStack(istack); int exp5[] = {1, 3, 4, 6, 7, 9, 11, 15}; AStack<int> stackExp5(exp5, 8); CHECK( istack == stackExp5 ); // perform same tests but with a stack of strings // sort an empty stack AStack<string> sstack; sortStack(sstack); LStack<string> stackExp6; CHECK( sstack == stackExp6 ); // sort stack with single item sstack.push("mike"); sortStack(sstack); string exp7[] = {"mike"}; LStack<string> stackExp7(exp7, 1); CHECK( sstack == stackExp7 ); // sort already sorted stacks sstack.push("papa"); sstack.push("sierra"); sstack.push("victor"); sortStack(sstack); string exp8[] = {"mike", "papa", "sierra", "victor"}; LStack<string> stackExp8(exp8, 4); CHECK( sstack == stackExp8 ); // add items out of order and sort sstack.push("alpha"); sstack.push("x-ray"); sstack.push("tango"); sstack.push("oscar"); sstack.push("mike"); sortStack(sstack); string exp9[] = {"alpha", "mike", "mike", "oscar", "papa", "sierra", "tango", "victor", "x-ray"}; LStack<string> stackExp9(exp9, 9); CHECK( sstack == stackExp9 ); // sort a stack that is in reverse order sstack.clear(); sstack.push("yankee"); sstack.push("quebec"); sstack.push("november"); sstack.push("november"); sstack.push("lima"); sstack.push("hotel"); sstack.push("echo"); sstack.push("bravo"); sortStack(sstack); string exp10[] = {"bravo", "echo", "hotel", "lima", "november", "november", "quebec", "yankee"}; LStack<string> stackExp10(exp10, 8); CHECK( sstack == stackExp10 ); } */