C++ Calculator using Shunting Yard Algorithm

#if 0
g++ -o ${0:0:${#0}-4} $0; exit
#else
/*---------------------------------------------------------------*\
| Basic Calculator using Shunting Yard Algorithm       <calc.cpp> |
|                                                                 |
+-----------------------------------------------------------------+
| This program is free software; you can redistribute it and/or   |
| modify it under the terms of the GNU General Public License as  |
| published by the Free Software Foundation; either version 3 of, |
| or the License (at your option) any later version.              |
|                                                                 |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of  |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the   |
| GNU General Public License for more details.                    |
+-----------------------------------------------------------------+
| Author: blackberry                   <src.blackberry@yahoo.com> |
| Date:   2011-09-24 (original version); 2017-08-16 (minor fixes) |
\*---------------------------------------------------------------*/

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stack>
#include <map>
#include <cmath>


typedef enum _SY_TOKEN_TYPE
{
    SY_TT_OPERATOR, SY_TT_NUMBER
} SY_TOKEN_TYPE;

typedef struct _SY_TOKEN
{
    SY_TOKEN_TYPE type;
    union
    {
        char op;
        double num;
    };

    _SY_TOKEN(void) : type(SY_TT_NUMBER), num(0) { }
    _SY_TOKEN(char _op) : type(SY_TT_OPERATOR), op(_op) { }
} SY_TOKEN;

typedef enum _SY_OP_ASSOCTYPE
{
    SY_OP_LEFTASSOC, SY_OP_RIGHTASSOC
} SY_OP_ASSOCTYPE;

typedef std::stack<SY_TOKEN *> SY_TOKEN_STACK;

SY_TOKEN_STACK *sy_tokenize(char *str)
{
    char prevchar = 0;
    SY_TOKEN *tok;
    SY_TOKEN_STACK inp;
    SY_TOKEN_STACK *stream = new SY_TOKEN_STACK;
    double _exp, multiplier;
    bool negnum;

    for(; *str; str++)
    {
        if (strchr(" \t\r\n", *str)) continue;
        switch(*str)
        {
            case '+': case '-': case '*': case '/':
            case '(': case ')': case '^':
                if (*str != '-' || (*str == '-' && !strchr("(*/^", prevchar) && prevchar))
                {
                    if (*str == '(' && strchr("0123456789)", prevchar) && prevchar)
                        inp.push(new SY_TOKEN('*'));
                    inp.push(new SY_TOKEN(*str));
                    if (*str == ')' && isdigit(str[1]))
                        inp.push(new SY_TOKEN('*'));
                    break;
                }
            case '0': case '1': case '2': case '3': case '4':
            case '5': case '6': case '7': case '8': case '9':
                tok = new SY_TOKEN;
                _exp = 1;
                negnum = (*str == '-');
                if (*str == '-') str++;
                multiplier = 10;
                for(; *str; str++)
                {
                    if (*str == '.')
                    {
                        if (multiplier == 0.1 || !isdigit(str[1]))
                            return 0;
                        _exp = 0.1;
                        multiplier = 0.1;
                        continue;
                    }
                    if (*str < '0' || *str > '9')
                    {
                        break;
                    }
                    tok->num = tok->num * _exp + (*str - '0');
                    _exp *= multiplier;
                }
                str--;
                if (negnum) tok->num *= -1;
                inp.push(tok);
                break;
            default:
                return 0;
        }
        prevchar = *str;
    }

    while(inp.size())
    {
        stream->push(inp.top());
        inp.pop();
    }
    return stream;
}

unsigned int sy_op_precedence(SY_TOKEN *op)
{
    std::map<char, unsigned int> prectab;
    prectab['^'] = 3;
    prectab['*'] = 2;
    prectab['/'] = 2;
    prectab['+'] = 1;
    prectab['-'] = 1;
    return prectab[op->op];
}

SY_OP_ASSOCTYPE sy_op_assoctype(SY_TOKEN *op)
{
    return op->op == '^' ? SY_OP_RIGHTASSOC : SY_OP_LEFTASSOC;
}

SY_TOKEN_STACK *sy_rearrange(SY_TOKEN_STACK *inp)
{
    SY_TOKEN_STACK *out_stack = new SY_TOKEN_STACK;
    SY_TOKEN_STACK op_stack;

    while(!inp->empty())
    {
        SY_TOKEN *tok = inp->top();
        inp->pop();

        if (tok->type == SY_TT_NUMBER)
        {
            out_stack->push(tok);
        }
        else switch(tok->op)
        {
            case '+': case '-': case '*': case '/': case '^':
                while(op_stack.size())
                {
                    if ((sy_op_assoctype(op_stack.top()) == SY_OP_RIGHTASSOC && sy_op_precedence(tok) < sy_op_precedence(op_stack.top())) || (sy_op_assoctype(op_stack.top()) == SY_OP_LEFTASSOC && sy_op_precedence(tok) <= sy_op_precedence(op_stack.top())))
                    {
                        out_stack->push(op_stack.top());
                        op_stack.pop();
                    }
                    else break;
                }
            case '(':
                op_stack.push(tok);
                break;
            case ')':
                while(op_stack.size() && op_stack.top()->op != '(')
                {
                    out_stack->push(op_stack.top());
                    op_stack.pop();
                }

                if (!op_stack.size())
                    return 0;
                delete tok;
                delete op_stack.top();
                op_stack.pop();
                break;
        }
    }
    while(op_stack.size())
    {
        out_stack->push(op_stack.top());
        op_stack.pop();
    }
    return out_stack;
}

double sy_eval_token_stack(SY_TOKEN_STACK *out_stack)
{
    if (!out_stack->size())
        return NAN;
    SY_TOKEN tok = *(out_stack->top());
    delete out_stack->top();
    out_stack->pop();

    if (tok.type == SY_TT_NUMBER)
    {
        return tok.num;
    }
    else
    {
        double op2 = sy_eval_token_stack(out_stack);
        double op1 = sy_eval_token_stack(out_stack);

        if (op1 == NAN || op2 == NAN)
            return NAN;

        switch(tok.op)
        {
            case '+':
                return op1 + op2;
            case '-':
                return op1 - op2;
            case '*':
                return op1 * op2;
            case '/':
                if (op2 == 0)
                    return NAN;
                return op1 / op2;
            case '^':
                return pow(op1, op2);
            default:
                return NAN;
        }
    }
}

double sy_eval_expr(char *str)
{
    SY_TOKEN_STACK *ts;
    double result;

    if (!(ts = sy_tokenize(str)))
        return NAN;
    if (!(ts = sy_rearrange(ts)))
        return NAN;
    result = sy_eval_token_stack(ts);

    if (ts->size())
    {
        while(ts->size())
        {
            delete ts->top();
            ts->pop();
        }
        return NAN;
    }

    return result;
}

int main(void)
{
    while(!feof(stdin))
    {
        char buffer[1024];
        printf("$ ");
        fgets(buffer, sizeof(buffer), stdin);
        if (!strcmp(buffer, "\n")) break;
        printf("    = %g\n", sy_eval_expr(buffer));
    }
    return 0;
}

/* ----------------------------------------------------------- */
#endif