Sans Pareil Technologies, Inc.

Key To Your Business

Lab 12 - Stack


We will illustrate the use of the stack data structure using some common examples for which stacks are used.

functions.h

Header file that declares some of the functions we will implement using stack.

#pragma once
#include <string>

namespace csc240
{
  bool isPalindrome( const std::string& text );
  std::string reverseWords( const std::string& words );
  bool checkParenthesis( const std::string& text );
}

functions.cpp

Implementation file that contains the implementations of the functions as well as associated unit test suites.

#include "catch.hpp"
#include "functions.h"

#include <stack>

namespace csc240
{
  bool isPalindrome( const std::string& text )
  {
    auto result = true;
    std::stack<char> stack;
    for ( auto c : text ) stack.push( c );

    for ( auto it = text.begin(); result && !stack.empty(); ++it )
    {
      result = ( *it == stack.top() );
      stack.pop();
    }

    return result;
  }

  SCENARIO( "Palindrome test using stack" )
  {
    GIVEN( "A function that checks an input string for palindrome" )
    {
      REQUIRE( isPalindrome( "1234321" ) );
      REQUIRE( isPalindrome( "abcba" ) );
      REQUIRE_FALSE( isPalindrome( "abc" ) );
    }
  }

  using Strings = std::vector<std::string>;

  Strings tokenise( const std::string& text, const std::string& delimiters = " " )
  {
    using std::string;
    Strings tokens;

    auto lastPos = text.find_first_not_of( delimiters, 0 );
    auto pos = text.find_first_of( delimiters, lastPos );

    while ( string::npos != pos || string::npos != lastPos )
    {
      tokens.emplace_back( text.substr( lastPos, pos - lastPos ) );
      lastPos = text.find_first_not_of( delimiters, pos );
      pos = text.find_first_of( delimiters, lastPos );
    }

    return tokens;
  }

  std::string reverseWords( const std::string & words )
  {
    auto strings = tokenise( words );
    std::stack<std::string> stack;

    for ( auto word : strings ) stack.push( word );
    std::stringstream ss;

    while ( !stack.empty() )
    {
      ss << stack.top();
      if ( stack.size() > 1 ) ss << ' ';
      stack.pop();
    }

    return ss.str();
  }

  SCENARIO( "Using a stack to reverse words in a sentence" )
  {
    GIVEN( "A function that reverses the words in an input sentence" )
    {
      std::string words{ "Some random text input" };
      REQUIRE( "input text random Some" == reverseWords( words ) );
      REQUIRE( "Some" == reverseWords( "Some" ) );
    }
  }

  bool isMatchingPair( char character1, char character2 )
  {
    if ( character1 == '(' && character2 == ')' ) return true;
    if ( character1 == '{' && character2 == '}' ) return true;
    if ( character1 == '[' && character2 == ']' ) return true;
    return false;
  }

  bool checkParenthesis( const std::string& text )
  {
    std::stack<char> stack;

    for ( auto c : text )
    {
      switch ( c )
      {
        case '[':
        case '{':
        case '(':
          stack.push( c );
          break;
        case ')':
        case '}':
        case ']':
          if ( stack.empty() ) return false;
          if ( ! isMatchingPair( stack.top(), c ) ) return false;
          stack.pop();
          break;
      }
    }

    return stack.empty();
  }

  SCENARIO( "Using a stack to check for properly balanced parenthesis" )
  {
    GIVEN( "A function that check for balanced parenthesis" )
    {
      REQUIRE( checkParenthesis( "[a{b(c)d}e]" ) );
      REQUIRE( checkParenthesis( "a{b(c)d}e" ) );
      REQUIRE( checkParenthesis( "ab(c)de" ) );
      REQUIRE( checkParenthesis( "abcde" ) );
      REQUIRE( checkParenthesis( "[]" ) );
      REQUIRE( checkParenthesis( "{}" ) );
      REQUIRE( checkParenthesis( "()" ) );
      REQUIRE( checkParenthesis( "[()]" ) );
      REQUIRE( checkParenthesis( "{[()]}" ) );
      REQUIRE_FALSE( checkParenthesis( "[a{b(c)d}e" ) );
      REQUIRE_FALSE( checkParenthesis( "[a{b(c)de]" ) );
      REQUIRE_FALSE( checkParenthesis( "[a{b(cd}e]" ) );
      REQUIRE_FALSE( checkParenthesis( "a{b(c)d}e]" ) );
      REQUIRE_FALSE( checkParenthesis( "ab(c)d}e]" ) );
      REQUIRE_FALSE( checkParenthesis( "abc)d}e]" ) );
    }
  }
}