Infix-to-postfix parser using Dijkstra's shunting yard algorithm

Question

I've been trying to expand my programming horizons, and have entered the world of grammars and parsing, which I'm brand new to. I have been improving a little implementation of Dijkstra's shunting yard algorithm that currently handles negatives and parentheses correctly (which took a bit of work). I'm well aware that I could make it much easier by using a parser generator, but for now I want to try to hand code it.

template <typename Iterator>
void inline skip_space(Iterator& head, Iterator last)
{
    while(head != last && std::isspace(*head)) ++head;
}

bool inline is_numeric(char ch)
{
    switch(ch)
    {
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
    case '0':
        return true;

    default:
        return false;
    }
}

// Pump characters though to output while input is currently a number, and advance head iterator past number
template <typename Iterator1, typename Iterator2>
bool inline process_number(Iterator1& head, Iterator1 last, Iterator2& output)
{
    skip_space(head, last);

    bool valid = false;

    while(head != last && is_numeric(*head)) valid = true, *output++ = *head++;
    if(valid && *head == '.')
    {
        *output++ = '.';
        while(is_numeric(*++head)) *output++ = *head;
    }
    *output++ = ' ';

    return valid;
}

// Get next symbol and advance head iterator past it
template <typename Iterator1, typename Iterator2>
char inline get_symbol(Iterator1& head, Iterator1 last, Iterator2 symbols_begin, Iterator2 symbols_end)
{
    using namespace std;

    head = find_first_of(head, last, symbols_begin, symbols_end);
    if(head == last) return 0;
    else return *head++;
}

// Requires at least an input iterator for Iterator1, and an output iterator for Iterator2
template <typename NumType = double, typename Iterator1, typename Iterator2>
bool parse_to_rpn(Iterator1 head, Iterator1 last, Iterator2 output)
{
    using namespace std;

    // Token list for matching
    static const char tokens[] = {'+', '-', '*', '/', '^', '(', ')'};

    // Map containing information about operators
    static map<char, tuple<unsigned int /* precedence */, bool /* is binary */, bool /* is left associative */>> operator_info
        {
            {'+', make_tuple(1U, true, true)},
            {'-', make_tuple(1U, true, true)},
            {'*', make_tuple(2U, true, true)},
            {'/', make_tuple(2U, true, true)},
            {'^', make_tuple(4U, true, false)},
            {'n', make_tuple(3U, false, true)}
        };

    // Operator stack
    stack<char> oper_stack;

    // Some defines to make my life a bit easier
    #define IS_BINARY(c) std::get<1>(operator_info.at(c))
    #define IS_LEFT_ASSOCIATIVE(c) std::get<2>(operator_info.at(c))
    #define PRECEDENCE(c) std::get<0>(operator_info.at(c))

    bool need_numeric = true;   // If true, parser looks for a number value (or a parenthesized expression)...
                                // If false, parser looks for an operator

    // Try block to isolate any exceptions; simply returns false if one is caught
    try {

    // Skip whitespace
    skip_space(head, last);
    while(head != last)
    {
        // Mode 1: looking for something that will evaluate to a number
        if(need_numeric)
        {
            if(head == last) return false;

            // Handle positive or negative sign properly if looking for a number
            else if(*head == '+')
            {
                ++head;
            }
            else if(*head == '-')
            {
                oper_stack.push('n');   // Push unary negation operator onto stack
                ++head;
            }

            if(head == last) return false;
            else if(*head == '(')
            {
                oper_stack.push('(');   // Push left parenthesis onto stack
                ++head;
            }
            else if(process_number(head, last, output)) need_numeric = false;    // If a number was found, switch modes
            else return false;
        }

        // Mode 2: looking for an operator
        else
        {
            char symbol = get_symbol(head, last, begin(tokens), end(tokens));   // Get next symbol

            if(symbol == '(') return false;     // Mistmatched parenthesis
            else if(symbol == ')')              // Pop operators off stack until matching parenthesis
            {
                if(oper_stack.size() == 0) return false;    // Mismatched parenthesis
                while(oper_stack.top() != '(')
                {
                    if(oper_stack.size() == 1) return false;    // Mismatched parenthesis
                    *output++ = oper_stack.top();
                    oper_stack.pop();
                }
                oper_stack.pop();
            }

            // The core of this parser: Dijkstra's shunting yard algorithm
            else if(IS_BINARY(symbol))
            {
                if(IS_LEFT_ASSOCIATIVE(symbol))
                {
                    while(oper_stack.size() > 0 && oper_stack.top() != '(' && PRECEDENCE(symbol) <= PRECEDENCE(oper_stack.top()))
                    {
                        *output++ = oper_stack.top();
                        oper_stack.pop();
                    }
                    oper_stack.push(symbol);
                }
                else
                {
                    while(oper_stack.size() > 0 && oper_stack.top() != '(' && PRECEDENCE(symbol) < PRECEDENCE(oper_stack.top()))
                    {
                        *output++ = oper_stack.top();
                        oper_stack.pop();
                    }
                    oper_stack.push(symbol);
                }

                need_numeric = true;    // Binary operator needs another operand, obviously; switch modes
            }
            else
            {
                while(oper_stack.size() > 0 && oper_stack.top() != '(' && PRECEDENCE(symbol) <= PRECEDENCE(oper_stack.top()))
                {
                    *output++ = oper_stack.top();
                    oper_stack.pop();
                }
                oper_stack.push(symbol);
            }
        }
        skip_space(head, last);
    }

    }
    catch(...)
    {
        return false;
    }

    // Pop remaining operators into output
    while(oper_stack.size())
    {
        if(oper_stack.top() == '(') return false;   // Mismatched parenthesis
        *output++ = oper_stack.top();
        oper_stack.pop();
    }

    #undef IS_BINARY
    #undef IS_LEFT_ASSOCIATIVE
    #undef PRECEDENCE
}

Again, I'm really new to writing parsers, so how can I clean this up and make it more extensible? My next goal is to parse into a tree instead of text-based RPN notation. I figure that won't be too difficult in itself, but I'd also like to later include the ability to handle operators of arbitrary length, and possibly even function names and variables. To be able to do that, would it be necessary (or at least prudent) to write a separate tokenizer?

A side question: for implementing a parse tree, would it be a better choice to use an abstract base class for all nodes and implement leaf nodes and operator/function nodes as children, or to use a struct containing an ID of some sort, and a union that contains all the necessary data for each possible type of node?

Answer 1

A few tips:

• Your function is_numeric is rather useless. There is a function named std::isdigit in the standard header <cctype> which does exactly the same thing.
• Instead of skip_space, I would have named the functions skip_spaces. skip_space is a misleading name since the function may actually skip many spaces at once.

• This piece of code:

  if(head == last) return 0;
  else return *head++;
  

  could be rewritten as such (without the else and with {} after the if):

  if (head == last)
  {
      return 0;
  }
  return *head++;
  

  You should always put curly braces after an if clause. It's not required, but most of the guidelines will tell you to do so. It makes it easier to extend your code to avoid errors. By the way, please, never do this again:

  while(head != last && is_numeric(*head)) valid = true, *output++ = *head++;
  

  You should really use one line per statement, and separate your statements by ;, not by ,. You should have written this instead:

  while (head != last && std::isdigit(*head))
  {
      valid = true;
      *output++ = *head++;
  }
  

• Your function process_number accepts numbers contaning a dot or ending with a dot but does not accept as valid numbers beginning with a dot, which is rather strange. You should either accept numbers beginning with a dot or forbid number ending with a dot.

• The following macros are not needed:

  #define IS_BINARY(c) std::get<1>(operator_info.at(c))
  #define IS_LEFT_ASSOCIATIVE(c) std::get<2>(operator_info.at(c))
  #define PRECEDENCE(c) std::get<0>(operator_info.at(c))
  

  You can replaced them by inline functions, or even by lambdas since it seems that you are using C++11.

• You use an std::tuple to represent the information associated to an operator. And as you can see, you are forced to name your parameters in the comments and to use positional arguments (std::get<...>). What you need are named parameters to make it clear. Use a plain old struct instead of std::tuple:

  struct Operator
  {
      unsigned precedence;
      bool is_binary;
      bool is_left_associative;
  };
  

  It will allow you to simplify your map declaration even further thanks to aggregate initialization:

  static map<char, Operator> operator_info
  {
      { '+', { 1U, true, true } },
      { '-', { 1U, true, true } },
      { '*', { 2U, true, true } },
      { '/', { 2U, true, true } },
      { '^', { 4U, true, false } },
      { 'n', { 3U, false, true } }
  };
  

• Your function get_symbol is supposed to return a char but when there is an error, you simply write return 0;.