6
\$\begingroup\$

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;
}
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can solve must of your issues easily. 1) Don't use globals and start wrapping things inside a class. 2) Write stream operator operator<< to do the printing. 3) Use standard types that have already been built. \$\endgroup\$ – Martin York Feb 23 '14 at 16:28
  • \$\begingroup\$ Is there a particular reason for wrapping up things in a class? Regarding the rest i shall do so thank you \$\endgroup\$ – abhyudayasrinet Feb 23 '14 at 16:50
  • \$\begingroup\$ Yes. Wrapping things in classes makes the code more readable and maintainable. You are putting all the code the interacts with the data in the same place and protecting the data from mutation from an unexpected source. Thus making it wasier to maintain your invariants. You should avoid global mutable state as function with side affects are hard to test debug and validate. \$\endgroup\$ – Martin York Feb 23 '14 at 17:05
4
\$\begingroup\$

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);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.