Suppose you wanted to efficiently store and access plates in a cafeteria. The easiest way to do this is to stack the plates one on top of the other. When you have more plates available, you place the on the stack, and when someone needs a plate, they take the plate that is currently on top of the stack. There is no need to worry about how many plates there are in the stack, except being able to observe whether or not the stack is currently empty or not. What plate is five down the stack is irrelevant to the question of obtaining a plate from the stack.

Okay, a silly enough question; however, have you noticed that in Python and in C++, delimiters (round parentheses, square brackets, and curly braces; or just parentheses, brackets and braces) are always matched:

1. You cannot have a closing delimiter (), ], or }) before a corresponding opening delimiter (), [, or {).
2. Each opening delimiter must be matched with a following closing delimiter of the same style.
3. Each opening delimiter must be matched with one and only one closing delimiter of the same style.

This may seem sufficient, but you may have noticed it is impossible in Python to have the following:

    z = a*(b + c[d) - e]

All the above rules are satisfied by the above code, but this does not parse in Python regardless of the types of the characters. Thus, we need a fourth rule:

4. A closing delimiter must always have the same style as the last unmatched opening delimiter.

In the above code, it would be great when we get to the ) to be able to give an error message such as:

On line 57, expeciting a closing ']', but found ')'
    z = a*(b + c[d) - e]
------------------^

To do this, we can use an array as follows:

• The array delimiters[...] starts as empty and we will designate its capacity as N.
• We will store the number of items in the array as n, so initially, n = 0.
• Whenever we come across an opening delimiter,
• if n == N, we have already filled up the array, so signal an error: not enough memory is in the 'delimiters[...]' array;
• otherwise, we assign delimiters[n] the opening delimiter we came across, and we then increment n: ++n.
• Whenever we come across a closing delimiter,
  • if the array delimiters[...] is empty (that is, n == 0), we signal the error: Found an unmatched closing delimiter;
  • if the closing delimiter matches the last opening delimiter we put on the stack (that is, compare the closing delimiter and delimiters[n - 1]), then remove the top closing delimiter from the array (--n);
  • otherwise, the closing delimiter does not match the last unmatched opening delimiter, so signal an error: The current closing delimiter does not match the most recent unmatched opening delimiter.
• Finally, once we are finished parsing all the code,
• if the array delimiters[...] is empty (n == 0), all is good and we are finished;
• otherwise, there are opening delimiters that do not have matching closing delimiters, so signal an error: There are 'n' opening delimiters that do not have corresponding closing delimiters.

Did you think of all of these necessary rules and checks? If not, that's okay: this is your very first data structure.

To implement this data structure in C++, we will have a class, and this class can be viewed at replit.com. First, we begin with the class definition, which is in the file Delimiter_stack.hpp. This defines the private member variables of the class and the public member functions as well as the constructor:

#pragma once
#include <cstddef>

class Delimiter_stack {
  public:
    // The constructor
    Delimiter_stack();

    // A member function to push a new
    // opening delimiter onto the stack
    void push( char open );

    // A member function to pop an opening 
    // delimiter from the stack if the opening
    // delimiter matches the passed closing
    // delimiter.
    void pop( char close );

    // A function to check if the stack is empty
    bool empty() const;
  private:
    // Constants
    std::size_t static const CAPACITY_ = 32;

    std::size_t              size_;
    char array_[CAPACITY_];
};

We can now implement each of these member functions, and you can view this at Delimiter_stack.cpp.

Finally, the main.cpp function has the executable file.

Problem!

We just implemented a stack for one very specific purpose; however this means we need to write a new stack every single time we need such a data structure. This is not in any way efficient and it does not lead to re-usable code. Instead, we just need a vanilla stack data structure, and then use it to solve the given problem.

Like a stack of plates, a stack has a few operations you may want to perform on it:

• Ask if the stack is empty.
• Ask how many items are in the stack.
• Push something onto the stack.
• Examine the "top" of the stack; that is, the last thing that was pushed onto the stack.
• Pop the "top" of the stack; that is, remove from the stack the last item that was pushed onto the stack.

In this version, we author a stack class that stores any type of character. The parse(...) function simply uses the stack. Now, any program requiring a stack of characters can use this same code base without any changes.

Note, this is a nice time to point out that in the main() function, there is a test that causes each error to be thrown. This is comprehensive testing.

The Standard Library and templates

Finally, however, you should ask yourself is there any difference between a stack of characters and a stack of integers? The answer is, really, no. A character is one byte, and an int is four bytes, but beyond that, everything else is the same. For this reason, and because stacks are ubiquitous throughout programming, the standard library has a stack class, and you can tell it which type is to be stored in the one you create. See this replit that uses the standard library stack.

You may notice I was being a little sneaky: when I defined the member functions above for these stacks, I used the same member function names in the standard library. You can see the member functions and a description of the stack class at cplusplus.com or at cppreference.com.

In this code, I also integrate the other tests that cause errors.