<main()>= (U→)

int 
main() 

  std::string tag
  string_stack tags

  while read_tag(std::cin, tag)
    if open_tag(tag)
      tags.push(tag)
    else 
      if tags.empty()
        err(std::string("No matching open tag for ") + tag)
      const std::string t = tags.pop()
      if not paired_tags(t, tag)
        err(std::string("Tag mismatch between ") + t + " and " + tag)

  if not tags.empty()
    err(std::string("Tag ") + tags.pop() + " unmatched at end-of-input")

  exit(EXIT_SUCCESS)

Defines main (links are to index).

<main.cc>=

#include <string>
#include <iostream>
#include <cstdlib>
#include <cassert>
#include "string-stack.h"


// Tag elements.

   const char
     tag_open_mark = '[',
     tag_close_mark = ']',
     tag_end_mark = '/'


// Deja vu c++ style.

   static bool read_tag(std::istream &, std::string &)
   static bool open_tag(const std::string &)
   static bool paired_tags(const std::string &, const std::string &)
   static bool skip_until(std::istream &, char)
   static std::string read_until(std::istream &, char)
   static std::string trim(const std::string &)
   static void err(const std::string &)


static void
check_tag(const std::string & tag) 
  
  // Check the given tag for syntax; die with an error if anything's wrong.

  if tag.empty()
    err("Empty tag")

  size_t s = 0
  if tag[0] == tag_end_mark
    s++
  const size_t n = tag.size()

  while ((s < n) and isalnum(tag[s++])) { }

  if s < n
    err("Non-alphanumeric character in tag name")


static void
err(const std::string & emsg) 

  // Print the given error message and die.

  std::cerr << "! " << emsg << ".\n"
  exit(EXIT_FAILURE)


#ifdef MAINTESTING

  // g++ -o maintesting -g -DMAINTESTING -ansi -pedantic -Wall main.cc ∧ ./maintesting

  int 
  main() 
    assert(open_tag("joe"))
    assert(not open_tag("/joe"))
    assert(paired_tags("joe", "/joe"))
    assert(not paired_tags("joe", "/blow"))
    std::string str = "hello"
    assert(trim(std::string("\n ") + str + " \n") == str)
    assert(trim(str + " \n") == str)
    assert(trim(std::string("\n ") + str) == str)
    assert(trim(str) == str)

#else

  <main()>

#endif


static bool
open_tag(const std::string & tag) 

  // Return true iff the given tag is an open tag.

  return not tag.empty() ∧ (tag[0] ≠ tag_end_mark)


static bool 
paired_tags(const std::string & otag, const std::string & ctag) 

  // Return true iff the given tags are a matched open-close pair.

  return 
        open_tag(otag) 
    and not open_tag(ctag) 
    and not ctag.empty()
    and (ctag.compare(1, ctag.size() - 1, otag) == 0)


static bool
read_tag(std::istream & is, std::string & tag) 

  // Read from the given input stream the next tag and store it in the given
  // reference.  Return true of a tag was read; false otherwise

  if not skip_until(is, tag_open_mark)
    return false

  tag = trim(read_until(is, tag_close_mark))
  check_tag(tag)

  return true


static std::string
read_until(std::istream & is, char c) 

  // Read and store characters from the given input stream until given
  // character is read (which is not stored) or there are no more characters to
  // read.  The characters read are stored in the string returned.

  std::string tag
  const unsigned n = 16
  char t[n]
  unsigned i = 0

  while ((t[i++] = is.get()) ≠ c) ∧ (is.gcount() > 0)
    if i ≥ n
      tag.append(t, n)
      i = 0
  if is.gcount() < 1
    err(std::string("Unexpected eof while searching for '") + c + "'")

  assert((i > 0) ∧ (t[i - 1] == c))
  tag.append(t, i - 1)

  return tag


static bool
skip_until(std::istream & is, char c) 

  // Read and toss characters from the given input stream until given character
  // is read (which is also tossed) or there are no more characters to read.
  // Return true iff the given character was read.

  while ((is.get() ≠ c) ∧ (is.gcount() > 0)) { }

  return is.gcount() > 0
  

static std::string
trim(const std::string & str) 

  // Return a copy of the given string stipped of all leading and trailing
  // space characters.

  const char * const space_chars = "\n \t\v"

  size_t s = str.find_first_not_of(space_chars)
  if s == std::string::npos
    s = 0

  size_t e = str.find_last_not_of(space_chars)
  if e == std::string::npos
    e = str.size()
  else
    e++

  return str.substr(s, e - s)

Defines main.cc (links are to index).

<strstk public methods>= (U→)

// Return true iff this stack is empty.

   bool empty() const


// Return true iff this stack is full.

   bool full() const


// Pop and return the top string in this stack; die with an error message 
// if there's no string to pop.

   std::string pop()


// Push the given string on this stack; die with an error message if
// there's no more room.

   void push(const std::string & str)


// Create a new empty stack capabile of holding the given number of 
// strings; die with an error message if the given number of strings isn't
// positive.

   strstk(unsigned size)


// Get rid of this stack.

  ~strstk()

<strstk.h>=

#ifndef _strstk_h_defined_
#define _strstk_h_defined_

#include <cassert>
#include <string>

class strstk 

  public:

    <strstk public methods>

  private:

    // The stacked strings.
    // Invariant:  strings ≠ 0.

       std::string * strings


    // Where the next string pushed goes.
    // Invariant:  0 ≤ next_top ≤ max.

       unsigned next_top


    // How many strings can be pushed.
    // Invariant:  0 < max.

       unsigned max


    // Fill out the rule of three.

       strstk(const strstk &) { }
       strstk operator = (const strstk &) { return *this; }


#endif

Defines strstk.h (links are to index).

<strstk.cc>=

#include "strstk.h"


bool strstk::
empty() const 
  return next_top == 0


bool strstk::
full() const 
  return next_top == max


std::string strstk::
pop() 
  assert(not empty())
  return strings[--next_top]


void strstk::
push(const std::string & str) 
  assert(not full())
  strings[next_top++] = str


strstk::
strstk(unsigned size) 
  : strings(new std::string [size]), next_top(0), max(size) 
  assert(size > 0)


strstk::
~strstk() 
  delete [] strings


#ifdef STRSTKTESTING

// g++ -o strstktesting -g -DSTRSTKTESTING -ansi -pedantic -Wall strstk.cc ∧ ./strstktesting

int 
main() 
  strstk sstk(16)
  assert(not sstk.full())
  assert(sstk.empty())
  std::string str = "hello"
  sstk.push(str)
  assert(not sstk.full())
  assert(not sstk.empty())
  assert(sstk.pop() == str)
  assert(not sstk.full())
  assert(sstk.empty())

  std::string str2 = "bye"

  sstk.push(str)
  sstk.push(str2)
  assert(sstk.pop() == str2)
  assert(sstk.pop() == str)
  assert(sstk.empty())

#endif

Defines strstk.cc (links are to index).

<string-stack public methods>= (U→)

// Return true iff this string stack is empty.

   bool empty() const


// Pop and return the top of this string stack; die with an error if the
// stack's empty.

   std::string pop()


// Push the given string on the top of this string stack.

   void push(const std::string &)


// Create a new, empty string stack.

   string_stack()


// Get rid of this string stack.

  ~string_stack()

<string-stack.h>=

#ifndef _string_stack_h_defined_
#define _string_stack_h_defined_

#include <string>
#include "strstk.h"

class string_stack 

  public:
  
    <string-stack public methods>

  private:

    // A link in the string-stack list.

       struct strstk_link 

         strstk_link * next
         strstk sstk

         strstk_link(unsigned size, strstk_link * next)
           : next(next), sstk(size) 


    // The head of the string-block list.
    // Invariant: strstk_head ≠ 0 → !strstk_head→sstk.empty().

       strstk_link * strstk_head


    // Fill out the rule of three.

       string_stack(const string_stack &) { }
       string_stack operator = (const string_stack &) { return *this; }

#endif

Defines string-stack.h (links are to index).

<string-stack.cc>=

#include "string-stack.h"


bool string_stack::
empty() const 
  return (strstk_head == 0)


std::string string_stack::
pop() 

  assert(not empty() and not strstk_head→sstk.empty())
  std::string str = strstk_head→sstk.pop()

  if strstk_head→sstk.empty()
    strstk_link * h = strstk_head→next
    delete strstk_head
    strstk_head = h

  return str


void string_stack::
push(const std::string & str) 
  if (strstk_head == 0) ∨ (strstk_head→sstk.full())
    strstk_head = new strstk_link(16, strstk_head)
  strstk_head→sstk.push(str)


string_stack::
string_stack()
  : strstk_head(0) 


string_stack::
~string_stack() 
  strstk_link * s = strstk_head
  while s
    strstk_link * n = s→next
    delete s
    s = n


#ifdef STRINGSTACKTESTING

// g++ -o stringstacktesting -g -DSTRINGSTACKTESTING -ansi -pedantic -Wall string-stack.cc strstk.cc ∧ ./stringstacktesting

int 
main() 
  string_stack sstk
  assert(sstk.empty())
  std::string str = "hello"
  sstk.push(str)
  assert(not sstk.empty())
  assert(sstk.pop() == str)
  assert(sstk.empty())

  std::string str2 = "bye"

  sstk.push(str)
  sstk.push(str2)
  assert(sstk.pop() == str2)
  assert(sstk.pop() == str)
  assert(sstk.empty())

#endif

// $Log: string-stack.cc,v $
// Revision 1.1  2008/12/17 06:14:47  rclayton
// Initial revision
//

Defines string-stack.cc (links are to index).