Monday, 5 August 2013

Infix to post fix conversion and evaluation using stack

#include<iostream.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define SI 20
int ip(char ch)
{
    switch(ch)
    {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 3;
        case '^':
            return 6;
        case '(':
            return 9;
        case ')':
            return 0;
        default:
            return 7;
    }
}

int sp(char ch)
{
    switch(ch)
    {
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
            return 4;
        case '^':
            return 5;
        case '(':
            return 0;
        case ')':
            return -1;
        default:
            return 8;
    }
}

class stack
{

    char a[SI];
    int top;

public:
    stack(){top=-1;}
    void push(char elem);
    char pop();
    char peak();
};

void stack::push(char elem)
{
     ++top;
     a[top]=elem;
}

char stack::pop()
{
    char elem=a[top];
    top=top-1;
    return elem;
}

char stack::peak()
{
     char elem;
     elem=a[top];
     return elem;
}

int evaluate(char post[])
{
     stack e;
     for(int i=0;i<strlen(post);++i)
     {
        if(ip(post[i])==7)
        {
            e.push(post[i]);
        }
        else
        {
        int b,a;
        b=e.pop()-48;
        a=e.pop()-48;
        switch(post[i])
        {
            case '+':
                e.push(a+b+48);
                break;
            case '-':
                e.push(a-b+48);
                break;
            case '*':
                e.push(a*b+48);
                break;
            case '/':
                e.push(a/b+48);
                break;
            case '^':
                e.push(pow(a,b)+48);
                break;
            default:
                break;
        }
     }
     }
     return e.pop()-48;
}

void intopost(char infx[],char postfx[])
{
    int i=0,j=0;
    stack s;
    while(infx[0]!='('||infx[strlen(infx)-1]!=')')
      {
            cout<<"must provide expression within paranthesis:"<<endl ;
            gets(infx);
      }
      s.push(infx[0]);
    for(i=1;infx[i]!='\0';++i)
    {
         char nxt=infx[i];

         while(ip(nxt)<sp(s.peak()))
         {
                postfx[j]=s.pop();
                j=j+1;
                postfx[j]='\0';
         }
         if(ip(nxt)>sp(s.peak()))
                s.push(nxt);
         else
                s.pop();
    }
}

int main()
{
    char infx[SI],postfx[SI];
    int result;
    cout<<"enter infix expression within paranthesis:"<<endl;
    gets(infx);
    intopost(infx,postfx);
    cout<<"post fix expression is:"<<endl;
        puts(postfx);
        result=evaluate(postfx);
        cout<<"Result is :"<<result;
    return 0;
}


OUTPUT:
enter infix expression within paranthesis:
(2+(3*4)/6)
post fix expression is:
234*6/+
Result is : 4