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

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
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
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
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
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> operator

A few tips:

• Your function is_numeric is rather useless. There is a function named std::isdigit in the standard header ` 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(operator_info.at(c))
#define IS_LEFT_ASSOCIATIVE(c) std::get(operator_info.at(c))
#define PRECEDENCE(c) std::get(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 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;`.

StackExchange Code Review Q#46136, answer score: 8