infix to postfix conversion and evaluation of postfix

Program to convert infix expression to postfix and evaluate the postfix expression

PROGRAM

#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<cctype>

Using namespace std;

class infix

{

char in[20],post[20],stack[20];

int top,s[50],cp,co;

public:

      infix()

      {

      top=-1;

      co=cp=0;

      }

      void read();

      void errorcheck();

      void display();

      void convert();

      int evaluate();

      int prior(char c);

      void push(char c);

      void push1(int val);

      int pop1();

      char pop();

};

void infix::read()

{

cout<<"Enter the infix expression:";

gets(in);

}

void infix::display()

{

cout<<"The infix expression is ";

puts(in);

cout<<"The postfix expression is ";

puts(post);

}

void infix::errorcheck()

{

int i=0;

do

{

if(isalpha(in[i]))

co++;

else if(in[i]=='(')

cp++;

else if(in[i]==')')

cp--;

else

co--;

i++;

}while(in[i]!='\0');

if((cp!=0)||(co!=1))

cout<<"\nInvalid expression";

}

void infix::push(char c)

{

top=top+1;

stack[top]=c;

}

void infix::push1(int val)

{

top=top+1;

s[top]=val;

}

int infix::pop1()

{

int temp;

temp=s[top];

top=top-1;

return temp;

}

char infix::pop()

{

char t;

t=stack[top];

top=top-1;

return t;

}

int infix::prior(char c)

{

switch(c)

{

case '+':

case '-':return 1;

case '*':

case '/':return 2;

case '^':return 3;

}

}

void infix::convert()

{

int i=0,k=0;

char c;

do

{

     if(isalpha(in[i]))

     post[k++]=in[i];

     else if(in[i]=='(')

     push(in[i]);

     else if(in[i]==')')

     {

      while(top>=0)

      {

      c=pop();

      if(c!='(')

      post[k++]=c;

      else

      break;

      }

     }

     else if(!isalpha(in[i]))

     {

      if(top==-1)

      push(in[i]);

      else

      {

      while(top>=0)

      {

      c=pop();

      if(c=='(')

      {

      push(c);

      break;

      }

      else

      {

      if(prior(c)<prior(in[i]))

      {

      push(c);

      break;

      }

      else

      post[k++]=c;

      }//else

     }//while

     push(in[i]);

     }//else

     }

     i++;

     }while(in[i]!='\0');

     while(top>=0)

     post[k++]=pop();

     post[k]='\0';

     }

     int infix::evaluate()

     {

       top=-1;

     int i=0,val;

     do

     {

      if(isalpha(post[i]))

      {

      cout<<"Enter the value for "<<post[i];

      cin>>val;

      push1(val);

      }

      else

      {

      int op1,op2;

      op1=pop1();

      op2=pop1();

      switch(post[i])

      {

      case '+':val=op1+op2;

                  break;

      case '-':val=op1-op2;

                  break;

      case '*':val=op1*op2;

                  break;

      case '/':val=op1/op2;

                  break;

      case '^':val=pow(op1,op2);

                  break;

      }

      push1(val);

      }i++;

      }while(post[i]!='\0');

      return pop1();

      }

     void main()

     {

     infix p;

       int v;

       p.read();

     p.errorcheck();

       p.convert();

       p.display();

       v=p.evaluate();

       cout<<"The result is "<<v;

     getch();

     }

OUTPUT

Enter the infix expression:a+b*c

The infix expression is a+b*c

The postfix expression is abc*+

Enter the value for a  3

Enter the value for a  5

Enter the value for a  1

The result is 8

Sparse matrix addition

program to implement sparse matrix addition using array

PROGRAM

#include<iostream.h>

using namespace std;

class sparse

{

      int a[20][20],b[20][20],k;

      public:

                  int m,n;

                  void read();

                  void display();

                  void convert();

                  void add(sparse,sparse);

                  void sparsedisp();

                  void original();

};

void sparse::read()

{

      int i,j;

      cout<<”Enter the order of matrix:”;

      cin>>m>>n;

      cout<<”Enter the elements:\n”;

      for(i=0;i<m;i++)

      {

      for(j=0;j<n;j++)

      {

      cin>>a[i][j];

      }

      }

}

void sparse::display()

{

      int i,j;

      for(i=0;i<m;i++)

      {

      for(j=0;j<n;j++)

      {

      cout<<a[i][j]<<”\t”;

      }

      cout<<”\n”;

      }

}

void sparse::convert()

{

      int i,j,k=1;

      for(i=0;i<m;i++)

      {

      for(j=0;j<n;j++)

      {

      if(a[i][j]!=0)

      {

      b[k][0]=i;

      b[k][1]=j;

      b[k][2]=a[i][j];

      k=k+1;

      }

      }

}

      k=k-1;

      b[0][0]=m;

      b[0][1]=n;

      b[0][2]=k;

}

void sparse::sparsedisp()

{

      int i,j;

      k=b[0][2];

      for(i=0;i<k+1;i++)

      {

      for(j=0;j<3;j++)

      {

      cout<<b[i][j]<<”\t”;

      }

      cout<<”\n”;

      }

}

void sparse::add(sparse s1,sparse s2)

{

      int i=1,j=1,k=1;

      while((i<=s1.k)&&(j<=s2.k))

      {

      if(s1.b[i][0] < s2.b[j][0])

      {

      b[k][0]=s1.b[i][0];

      b[k][1]=s1.b[i][1];

      b[k][2]=s1.b[i][2];

      i++;

      k++;

      }

      else if( s1.b[i][0] > s2.b[j][0])

      {

      b[k][0]=s2.b[j][0];

      b[k][1]=s2.b[j][1];

      b[k][2]=s2.b[j][2];

      j++;

      k++;

}

else

{

      if(s1.b[i][1] < s2.b[j][1])

      {

      b[k][0]=s1.b[i][0];

      b[k][1]=s1.b[i][1];

      b[k][2]=s1.b[i][2];

      i++;

      k++;

}

else if( s1.b[i][1] > s2.b[j][1])

{

      b[k][0]=s2.b[j][0];

      b[k][1]=s2.b[j][1];

      b[k][2]=s2.b[j][2];

      j++;

      k++;

}

else

{

      b[k][0]=s1.b[i][0];

      b[k][1]=s1.b[i][1];

      b[k][2]=s1.b[i][2]+s2.b[j][2];

      i++;

      k++;

      j++;

}

}

}

while(i<=s1.k)

{

      b[k][0]=s1.b[i][0];

      b[k][1]=s1.b[i][1];

      b[k][2]=s1.b[i][2];

      i++;

      k++;

}

while(j<=s2.k)

{

      b[k][0]=s2.b[j][0];

      b[k][1]=s2.b[j][1];

      b[k][2]=s2.b[j][2];

      j++;

      k++;

}

k=k-1;

b[0][0]=s1.m;

b[0][1]=s2.n;

b[0][2]=k;

m=s1.m;

n=s2.n;

}

void sparse::original()

{

      int i,j;

      for(i=0;i<m;i++)

      for(j=0;j<n;j++)

      a[i][j]=0;

      for(i=1;i<=k;i++)

      {

                  int r=b[i][0];

                  int c=b[i][[1];

                  a[r][c]=b[i][2];

      }

}

int main()

{

      sparse s1,s2,s3;

      s1.read();

      cout<<”Matrix is:\n”;

      s1.display();

      s1.convert();

      cout<<”The sparse matrix is:\n”;

      s1.sparsedisp();

      s2.read();

      cout<<”Matrix is:\n”;

      s2.display();

      s2.convert();

      cout<<”The sparse matrix is:\n”;

      s2.sparsedisp();

      s3.add(s1,s2);

      cout<<”\nThe resultant sparse matrix is:\n”;

      s3.sparsedisp();

      s3.original();

      cout<<”The resultant matrix is:\n”;

      s3.display();

      return 0;

}

OUTPUT

Enter the order of matrix:2

2

Enter the elements:

2

0

0

3

Matrix is:

2                0

0                3

The sparse matrix is:

2       2       2

0       0       2

1       1       3

Enter the  order of matrix:2

2

Enter the elements:

3

0

4

0

Matrix is:

3                0

4                0

The sparse matrix is:

2       2       3

0       0       3

1       0       4

The resultant sparse matrix is:

2       2       3

0       0       5

1       0       4

1       1       3

The resultant matrix is:

5                0

4                3