Expression parser using the shunting yard algorithm

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
#include
#include
#include
#include
using namespace std;

map 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)
{
coutnnext;
}
coutchnext;
}
coutchpriority[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>expr;
cout='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

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(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  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>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]> 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.

StackExchange Code Review Q#42448, answer score: 5