/*******************************************************
APPLICATION : Evaluation of Prefix Expression
CODED BY : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE : 2010 - June - 11
********************************************************/
#include "iostream.h"
#include "conio.h"
#include "stdio.h"
#include "math.h"
#include "string.h"
template "class T"
class stack
{
private:
T *arr;
int TOP,MAXSTK;
public:
stack()
{
MAXSTK = 31;
arr = new T[MAXSTK];
TOP = 0;
}
stack(int n)
{
MAXSTK = n + 1;
arr = new T[MAXSTK];
TOP = 0;
}
friend void push(stack &,T);
friend T pop(stack &);
friend int empty(stack);
~stack()
{
delete arr;
}
};
template "class T"
void push(stack "T" &s, T item)
{
if(s.TOP != s.MAXSTK)
{
s.TOP += 1;
s.arr[s.TOP] = item;
}
else
cout << "\nStack Overflow.";
}
template "class T"
T pop(stack "T" &s)
{
T temp;
if(s.TOP != 0)
{
temp = s.arr[s.TOP];
s.TOP -= 1;
return temp;
}
else
{
temp = -999;
return temp;
}
}
template "class T"
int empty(stack "T" s)
{
if(s.TOP == 0)
return 1;
else
return 0;
}
int main()
{
char prefix[30],temp[2];
int i = 0;
float item;
cout << "Enter a Valid Prefix Expression,\n";
cout << "Write Expression in One Line Seperated by Space,\n";
cout << "Hit Enter when Finished\n\n";
prefix[i - 1] ='\0';
while(prefix[i-1] != '\n')
prefix[i++] = getchar();
stack "float" stk(50);
float value,operand1,operand2;
int j = i - 2,pos,k;
while(j >= 0)
{
pos = 0;
if(prefix[j] >= '0' && prefix[j] <= '9')
{
temp[0] = prefix[j]; // Save Prefix[j] to temp
i = j - 1;
k = 1;
if(prefix[j-1] != ' ') //Check for next character, If not Space
{
while(prefix[i] != ' ') //While space is not found
{
temp[k++] = prefix[i--]; //Save Prefix[i] to temp
pos++; //Increase Position
}
pos += 2;//At Last Increase Position by 2 to Skip Space
}
else //If a Single Character
pos = 2; //Skip Space
temp[k] = '\0'; //End String temp
strrev(temp);
item = atof(temp); //Convert string temp to float and store to item
push(stk,item); //Push to stack
}
else if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '$' || prefix[j] == 'l' || prefix[j] == '#' || prefix[j] == ' ')
{
operand1 = pop(stk);
if(operand1 == -999)
break;
if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '$')
{
operand2 = pop(stk);
if(operand2 == -999)
break;
}
if(prefix[j] == '+')
value = operand1 + operand2;
if(prefix[j] == '-')
value = operand1 - operand2;
if(prefix[j] == '*')
value = operand1 * operand2;
if(prefix[j] == '/')
{
if(operand2 != 0)
value = operand1 / float(operand2); //Cast one operand to float
else
{
cout << "\nError ! Cannot Divide by Zero";
getch();
return 0;
}
}
if(prefix[j] == '$')
value = pow(operand1,operand2);
if(prefix[j] == 'l')
value = log10(float(operand1));
if(prefix[j] == '#')
value = sqrt(operand1);
push(stk,value);
pos = 2;
}
else
{
cout << "\nError : Illegal Character";
getch();
return 0;
}
j -= pos;
}
float Result = pop(stk);
if(Result == -999 || !empty(stk)) //If Underflow Condition or stack is not empty, Print Error message and exit
{
cout << "\nError : The Given Prefix Expression is Not Valid.";
getch();
return 0;
}
else
cout << "\nResult = " << Result;
getch();
return 0;
}
No comments:
Post a Comment