Our Feeds

Tuesday, 17 November 2015

Ajith KP

Conversion and Evaluation of Prefix Expression in C++

Hello GuyZ,
     This is another question which may you have to solve during you MCA/BTech/BCA course. This program can read an expression and convert it to prefix expression, then evaluate the prefix expression. The assumption of the program is no unary operator is not going to support. If you found this program as usable don't forget to share the link with your classmates.



Source Code


/*
    [][][]
    [][][]
    [][][]
    [][][]  TerminalCoders.Blogspot.Com
    [][][]
    [][][]
    [][][]
*/
 
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;

template<typename T>
class stack
{
 T arr[1024];
 int ptr;
 public:
 stack()
 {
  ptr = 0;
 }
 int isEmpty()
 {
  if(ptr==0)return 1;
  return 0;
 }
 T top()
 {
  return arr[ptr-1];
 }
 void push(T c)
 {
  arr[ptr++] = c;
 }
 T pop()
 {
  return arr[--ptr];
 }
};

struct symtab
{
 char var;
 double val;
}sym[1024];

int isInSymtab(char c, int l){
 int i;
 for(i=0;i<l;i++)if(sym[i].var==c)return 1;
 return 0;
}

double getVal(char c, int l){
 int i;
 for(i=0;i<l;i++)if(sym[i].var==c)return sym[i].val;
}

int isOperator(char character)
{
    if (character == '+' || character == '-' || character == '*' || character == '/' || character=='^') {
        return 1;
    }    
    return 0;
}
int isOperand(char character)
{    
    if (isOperator(character) == 0 && character != '(' && character != ')' && !isdigit(character) && ((character>='a' && character<='z') || (character>='A' && character<='Z'))) {
        return 1;
    }
    return 0;
}

int isp(char op) {
 switch(op)
 {
  case '+':
  case '-':
   return 1;
   break;
  case '*':
  case '/':
   return 3;
   break;
  case '^':
   return 6;
   break;
 }
 return 0;
}

int icp(char op) {
 switch(op)
 {
  case '+':
  case '-':
   return 2;
   break;
  case '*':
  case '/':
   return 4;
   break;
  case '^':
   return 5;
   break;
 }
 return 0;
}
void reverse(char* str, int len) 
{
 for(int i=0; i<len/2; i++) 
 {
  char temp=str[i];
  str[i]=str[len-i-1];
  str[len-i-1]=temp;
 }
}


int main()
{
 char inf[1024], pre[1024], tmp[1024], *ptr;
 stack<char> s;
 cout<<"Infix: ";
 cin>>inf;
 reverse(inf, strlen(inf));
 ptr = inf;
 int i = 0, len = 0;
 while(*ptr!='\0')
 {
  if(isOperand(*ptr))
  {
   pre[i++] = *ptr;
  }
  else if(isOperator(*ptr))
  {
   while(!s.isEmpty() && s.top()!=')' && isp(s.top())>icp(*ptr))
   {
    pre[i++] = s.pop();
   }
   s.push(*ptr);
  }
  else if(isdigit(*ptr))
  {
   //pre[i++] = ' ';
   while(isdigit(*ptr))
   {
    pre[i++] = *ptr;
    *ptr++;
   }
   pre[i++] = ' ';
   *ptr--;
  }
  else if(*ptr==')')
  {
   s.push(*ptr);
  }
  else if(*ptr=='(')
  {
   while(!s.isEmpty())
   {
    if(s.top()==')')
    {
     s.pop();
     break;
    }
    pre[i++] = s.pop();
   }
  }
  *ptr++;
 }
 while(!s.isEmpty())
 {
  pre[i++]=s.pop();
 }
 pre[i] = '\0';
 reverse(pre, strlen(pre));
 cout<<"Prefix Expression: "<<pre<<endl;
 cout<<"\nEvaluating Prefix Expression...\n\n";
 stack<double> stk;
 reverse(pre, strlen(pre));
 ptr = pre;
 while(*ptr!='\0')
 {
  if(isOperand(*ptr)){
   if(isInSymtab(*ptr, len)){
    stk.push(getVal(*ptr, len));
   }
   else{
    double val;
    cout<<"Enter value for "<<*ptr<<": ";
    cin>>val;
    sym[len].var = *ptr;
    sym[len].val = val;
    stk.push(val);
    len++;
   }
  }
  else if(isdigit(*ptr)){
   int sum = 0;
   int x = 1;
   while(isdigit(*ptr)){
    sum+=(*ptr-'0')*x;
    x*=10;
    *ptr++;
   }
   *ptr--;
   stk.push(sum);
  }
  else if(isOperator(*ptr)){
   double res, a, b;
   a = stk.pop();
   b = stk.pop();
   switch(*ptr){
    case '+':res = a+b;break;
    case '-':res = a-b;break;
    case '/':res = a/b;break;
    case '*':res = a*b;break;
    case '^':res = pow(a, b);break;
   }
   stk.push(res);
  }
  *ptr++;
 }
 cout<<"Result: "<<stk.pop()<<endl;
}