Chapter 18 Exercise Set 1: Stack Applications

1. Write a function named split_on_spaces that takes a string as an argument and returns a vector of strings by separating the argument using spaces as the delimiter. The following doctests will make this task explicit:

   TEST_CASE("Test split_on_spaces") {
       vector<string> tokens = split_on_spaces("4 5 +");
       CHECK(tokens.size() == 3);
       tokens = split_on_spaces("4 5 + 6 *");
       CHECK(tokens.size() == 5);
       CHECK(tokens[0] == "4");
       CHECK(tokens[1] == "5");
       CHECK(tokens[2] == "+");
   }
   

2. Write a Boolean function named is_valid_infix_expression that takes a string containing a mathematical expression with +, -, *, /, and % operators, parentheses, (), for grouping, and numeric (digits) and variable (letters) operands, and returns true if the expression is valid and false if it is not.

   TEST_CASE("Test is_valid_infix_expression") {
       string expr = "(4 + a) / c"
       CHECK(is_valid_infix_expression(expr) == true);
       string expr = "(x * ((5 - d) + c) - y) * 2"
       CHECK(is_valid_infix_expression(expr) == true);
       string expr = "(x * ((5 - d) + c - y) * 2"
       CHECK(is_valid_infix_expression(expr) == false);
   }
   

3. Write a Boolean function named has_matching_tags that takes a string containing HTML source and returns true if each open tag has a corresponding closing tag in the right place.

4. Investigate the famous Towers of Hanoi puzzle, write a C++ program to print the steps to move a tower of size n using recursion (introduced in chapter 4 Recursion), and explain how this illustrates the relationship between stacks and recursion.