Expression parser using the shunting yard algorithm

Question

I am trying to implement an expression parser via the shunting yard algorithm about which I learnt here.

I am able to get the correct results for the cases I'm testing, but I think it would be better if someone experienced could go through it and verify it. Also, I plan to add more operators, such as '!' (factorial), sine, cosine, etc. Is there anything I should keep in mind before going forth with them?

#include<cmath>
#include<string>
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;

map <char,int> priority;

struct numstack
{
    double n;
    numstack *next;
}*numtop=0;

struct opstack
{
    char ch;
    opstack *next;
}*optop=0;

void pushNum(double n)
{
    struct numstack *newnode=new numstack[sizeof(numstack)];
    newnode->n=n;
    newnode->next=0;
    newnode->next=numtop;
    numtop=newnode;
}

void pushOp(char ch)
{
    struct opstack *newnode=new opstack[sizeof(opstack)];
    newnode->ch=ch;
    newnode->next=0;
    newnode->next=optop;
    optop=newnode;
}

double popNum()
{
    struct numstack *node=numtop;
    double n=numtop->n;
    numtop=numtop->next;
    delete node;
    return n;
}

char popOp()
{
    struct opstack *node=optop;
    char ch=optop->ch;
    optop=optop->next;
    delete node;
    return ch;
}


void display(numstack *head1,opstack *head2)
{
    if(head1!=0)
    {
        while(head1!=0)
        {
            cout<<head1->n<<"  ";
            head1=head1->next;
        }
        cout<<endl;
    }
    if(head2!=0)
    {
        while(head2!=0)
        {
            cout<<head2->ch<<"  ";
            head2=head2->next;
        }
        cout<<endl;
    }
}

bool Operator(char ch)
{
    string operators="+-*/(^";
    if(operators.find(ch)!=string::npos)
        return true;
    return false;
}

bool evaluate(char ch)
{
    if(optop==0)
        return false;
    if(priority[ch]==-1)
        return false;
    cout<<"ch : "<<ch<<" optop : "<<optop->ch<<endl;
    if(priority[ch]>priority[optop->ch])
        return false;
    return true;
}

void initialize()
{
    priority['+']=2;
    priority['-']=2;
    priority['*']=3;
    priority['/']=3;
    priority['^']=4;
    priority['(']=-1;
}
int main()
{
    initialize();
    double a,b;
    char expr[1000];
    cout<<"Enter expression to evaluate : \n\n"; //1+2-3*4+8-1
    cin>>expr;
    cout<<endl;
    int len=strlen(expr);
    for(int i=0;i<len;i++)
    {
        cout<<"character : "<<expr[i]<<endl;
        if(expr[i]==')')
        {
            char ch=popOp();
            while(ch!='(')
            {
                a=popNum();
                b=popNum();

                cout<<"a:"<<a<<" b:"<<b<<" op:"<<ch<<endl;
                if(ch=='+')
                    pushNum(a+b);
                else if(ch=='-')
                    pushNum(b-a);
                else if(ch=='*')
                    pushNum(a*b);
                else if(ch=='/')
                    pushNum(b/a);

                ch=popOp();
            }

        }
        else if(Operator(expr[i]))
        {
            if(evaluate(expr[i]))
            {
                a=popNum();
                b=popNum();
                char ch=popOp();
                cout<<"a:"<<a<<" b:"<<b<<" op:"<<ch<<endl;
                if(ch=='+')
                    pushNum(a+b);
                else if(ch=='-')
                    pushNum(b-a);
                else if(ch=='*')
                    pushNum(a*b);
                else if(ch=='/')
                    pushNum(b/a);
                else if(ch=='^')
                    pushNum( pow((double)b,(double)a));
                pushOp(expr[i]);
            }
            else
                pushOp(expr[i]);
        }
        else
        {
            string num;
            for(int j=i;expr[j]>='0' && expr[j]<='9';j++)
                num+=expr[j];
            pushNum(atoi(num.c_str()));
        }
        display(numtop,0);
        display(0,optop);
    }
    while(optop!=0)
    {
        char ch=popOp();
        a=popNum();
        b=popNum();
        cout<<"a:"<<a<<" b:"<<b<<" op:"<<ch<<endl;
        if(ch=='+')
            pushNum(a+b);
        else if(ch=='-')
            pushNum(b-a);
        else if(ch=='*')
            pushNum(a*b);
        else if(ch=='/')
            pushNum(b/a);
        else if(ch=='^')
            pushNum(pow((double)b,(double)a));
        display(numtop,0);
        display(0,optop);
    }
    cout<<"result = "<<popNum()<<endl;
    return 0;
}

Answer 1

Dont do this:

struct numstack
{
    double n;
    numstack *next;
}*numtop=0;  // <---- WHAT
             // Type and variable declaration all crammed together..

Its not as if you need to save space so be clear.

struct Numstack
{
    double n;
    numstack *next;
};
Numstack*   numtop=nullptr; // USE nullptr over 0.

You though it was worth implementing your type specific singly linked list?

void pushNum(double n)
void pushOp(char ch)
double popNum()
char popOp()

It is not only a waste of time, but probably much less efficient than std::list (it uses pool allocations to prevent repeated requests to the runtime memory management system).

Also did you really want a review on that?

void display(numstack *head1,opstack *head2)

Would be much clearer to write output operators for the two different types!

// As it is std::list can easily be printed:
std::copy(head1.begin(), head1.end(), std::ostream_iterator<double>(std::cout, " "));
std::cout << "\n";

This object never changes and is only used for lookup.

string operators="+-*/(^";

// so make it const.
// Also make it static so we only construct it once
// the identifier `operators` is a bit close to the keyword for me.
static string const operator = "+-*/(^";

Don't write if statements that return true or false

if(operators.find(ch)!=string::npos)
    return true;
return false;

// easier to write and read

return operators.find(ch)!=string::npos);

Don't use global variables.

map <char,int> priority;
bool evaluate(char ch) { /* uses priority */}

It is also immutable so you should not have used Initialize() to set it up. Should have used the maps constructor. But it would have been even better if you wrapped this functionality into an class.

What happens if I type a 200 character expression?

char expr[1000];
cout<<"Enter expression to evaluate : \n\n"; //1+2-3*4+8-1
cin>>expr;

Prefer to use a ccontainer that automatically expands:

std::string expr;
std::cout<<"Enter expression to evaluate : \n\n"; //1+2-3*4+8-1
std::getline(std::cin, expr);

Also operator>> is probably not the best to use for user intput. User input is line based while operator>> is space based. It reads upto the first space and then stops. Users normally type a line at a time before expecting feedback.

The main algorithm is too complicated to follow without more detailed comments. There should be a description of what is happening in there.

This seems very hard way to read a number.

        string num;
        for(int j=i;expr[j]>='0' && expr[j]<='9';j++)
            num+=expr[j];
        pushNum(atoi(num.c_str()));

 // Why not use the built in stream operators.

 double number;
 std::stringstream  exprStr(expr);

 expr >> number;

Don't use C style casts.

pushNum(pow((double)b,(double)a));

C++ has four explicit cast operators use those:

static_cast        // Most often used.
dynamic_cast       // If used means you have not correctly implemented the appropriate virtual method.
reinterpret_cast   // If used you should be casting to void* or char* for use with C library.
const_cast         // If used means you are doing something wrong probably.

But you need none of those.
Since a and b are already double.

Answer 2

Step 1:

Wrap your global state into classes.

class Stack
{
    std::list<double>   numtop;
    std::list<char>     optop;
    public:

    friend std::ostream& operator<<(std::ostream& s, Stack const& data)
    {
        std::copy(data.numtop.begin(), data.numtop.end(), std::ostream_iterator<double>(s, " "));
        s << "\n";
        std::copy(data.optop.begin(),  data.optop.end(),  std::ostream_iterator<char>(s, " "));
        s << "\n";
        return s;
    }
    void push(double v) {numtop.push_front(v);}
    void push(char v)   {optop.push_front(v);}

    double popNum()     {double result = numtop.front();numtop.pop_front();return result;}
    char   popOp()      {char result = optop.front();optop.pop_front();return result;}

    char   peekOp()     {return optop.front();}

    bool   empty() const{return optop.empty();}
};

class Priority
{
    std::map <char,int> priority;
    Stack&              stack;
    public:
    Priority(Stack& s)
        : stack(s)
    {
        priority['+']=2;
        priority['-']=2;
        priority['*']=3;
        priority['/']=3;
        priority['^']=4;
        priority['(']=-1;
    }
    bool evaluate(char ch)
    {
        if(stack.empty())
            return false;
        if(priority[ch]==-1)
            return false;
        std::cout<<"ch : "<<ch<<" optop : "<<stack.peekOp()<<std::endl;
        if(priority[ch]>priority[stack.peekOp()])
            return false;
        return true;
    }
    bool Operator(char ch)
    {
        static std::string const operators="+-*/(^";
        return (operators.find(ch)!=std::string::npos);
    }
};

Now use like this:

int main()
{
    Stack       stack;
    Priority    priority(stack);