Calculating string expressions

This was an old code-blog note about evaluating basic arithmetic expressions from strings for Otaku+.

The archived post described converting a string expression into an infix queue, then into a postfix queue, while stacking operators along the way. The source used STL stack and queue and handled basic operators, parentheses, and unary minus priority.

Historical context

This is not a standalone tool like the RO utilities. It is a small programming note from the same renos.tk period, useful mostly as a snapshot of the kind of C++ problem-solving notes that lived beside the downloadable utilities.

Archived source

The original post included the source inline:

#include <stack>
#include <queue>
#include "stdio.h"
using namespace std;

typedef struct tstack
{
    int val;
    char OP;
    int priority;
};

int Expression(const char *src, int *out, char *error)
{
    queue<tstack> infix;
    queue<tstack> postfix;
    stack<tstack> token;
    tstack op;
    size_t src_len = strlen(src);

    char val[10]; //max 10 digits
    int j = 0;

    //create infix queue
    for(int i = 0; i < src_len; i++)
    {
        if(isdigit(src[i]))
        {
            val[j] = src[i];
            j++;
        }
        else
        {
            if((!i || !j) && src[i] == '-') // minus as sign should have max high priority
                op.priority = 1;
            else if(src[i] == '-' || src[i] == '+') //add or minus have lowest priority
                op.priority = -1;
            else if(src[i] == '*' || src[i] == '/') //multiply or divide have second highest priority
                op.priority = 0;
            else if(src[i] == '(' || src[i] == ')')
                op.priority = 2;
            else if(src[i] == ' ') //no operation between two operands
            {
                if(j && isdigit(src[i + 1]))
                {
                    sprintf(error, "waiting operator before %s", &src[i]);
                    return 0;
                }
            }
            else
            {
                sprintf(error, "%c is unknown", src[i]);
                return 0;
            }

            if(j && src[i] != ' ')
            {
                val[j] = 0;
                tstack oval = {atoi(val), 0, 0};
                infix.push(oval);
                j = 0;
            }

            if(src[i] != ' ')
            {
                op.OP = src[i];
                infix.push(op);
            }
        }
    }
    if(j)
    {
        val[j] = 0;
        tstack oval = {atoi(val), 0, 0};
        infix.push(oval);
    }
    //create postfix queue
    while(!infix.empty())
    {
        if(infix.front().OP)
        {
            if(token.empty())
                token.push(infix.front());
            else
            {
                if(infix.front().OP == '(')
                    token.push(infix.front());
                else if(infix.front().OP == ')')
                {
                    while(token.top().OP != '(')
                    {
                        postfix.push(token.top());
                        token.pop();
                    }
                    token.pop();
                }
                else if(infix.front().priority > token.top().priority)
                    token.push(infix.front());
                else if(infix.front().priority == token.top().priority)
                {
                    postfix.push(token.top());
                    token.pop();
                    token.push(infix.front());
                }
                else if(infix.front().priority < token.top().priority)
                {
                    while(token.top().OP != '(')
                    {
                        postfix.push(token.top());
                        token.pop();
                    }
                    token.push(infix.front());
                }
            }
        }
        else
            postfix.push(infix.front());

        infix.pop();
    }
    //check if there are still ops at stack
    while(!token.empty())
    {
        postfix.push(token.top());
        token.pop();
    }
    //calculate result
    while(!postfix.empty())
    {
        if(postfix.front().OP)
        {
            if(postfix.front().OP == '-' && postfix.front().priority == 1) //check if its sign
                token.top().val*=-1;
            else
            {
                if(token.empty())
                {
                    sprintf(error, "syntax error", postfix.front().OP);
                    return 0;
                }

                tstack oval = token.top();
                token.pop();

                if(token.empty())
                {
                    sprintf(error, "syntax error", postfix.front().OP);
                    return 0;
                }

                switch(postfix.front().OP)
                {
                    case '+':token.top().val+=oval.val;break;
                    case '-':token.top().val-=oval.val;break;
                    case '*':token.top().val*=oval.val;break;
                    case '/':
                        if(oval.val)
                            token.top().val/=oval.val;
                        else
                        {
                            sprintf(error, "can't divide by zero");
                            return 0;
                        }
                    break;
                    default:
                        sprintf(error, "%c o.O''", postfix.front().OP);
                        return 0;
                }
            }
        }
        else
            token.push(postfix.front());

        postfix.pop();
    }

    if(!token.empty())
        *out = token.top().val;

    return 1;
}