Evaluating expression of the form "231+-43*3/56$"
☻Alogorithm to Evaluate Postfix Expression:
opndstk = the empty stack;
while (not end of input){
symb = next input char*acter;
if (symb is an operand)
opndstk.push(symb);
else{
opnd2 = opndstk.pop();
opnd1 = opndstk.pop();
value = result of applying symb to opnd1 and opnd2;
opndstk.push(value) }
☻Here's the Code for Evaluating Postfix Expression in Stacks:
//Evaluating Postfix expression
#include <iostream>
#include <process.h>
#include <string>
#include <math.h>
using namespace std;
int calc (int op1, int op2, char ch);
template <class Type>
//stack class
class Stack
{
private:
Type *stack;
int top;
int Maxsize;
public:
//1-argument constructor
Stack(int Max)
{
stack = new Type[Max];
top = -1;
Maxsize = Max;
}
//Boundary check, function to check weather stack is Empty or not.
bool isempty()
{
return (top==-1);
}
//Boundary check, function to check weather stack is Full or not.
bool isfull()
{
if (top == Maxsize)
return true;
else
return false;
}
//function to push value into stack
void push(Type val)
{
if (!isfull())
{
top++;
stack[top] = val;
}
else
{
cout << "stack overflow";
exit(1);
}
}
//function to Pop out value from the stack
Type pop()
{
if (!isempty())
{
int x = stack[top];
top--;
return x;
}
else
{
cout << "stack underflow";
exit(1);
}
}
};
//Main Function
void main()
{
Stack<int> s(4);
string exp;
int op1, op2, r;
cout << "Enter postfix expression";
cin >>exp;
for (int i=0; i< exp.length(); i++)
{
char symb= exp[i];
if (symb >='0' && symb <= '9') // if 0perand
s.push(symb - '0');//converting into integer using ASCII codes
else
{
op2 = s.pop();
op1 = s.pop();
r = calc(op1, op2, symb); //function call
s.push(r); // push result into stack.
}
}
cout << "Result is "<< s.pop();
}
//definition of the function to operations:
int calc (int op1, int op2, char ch)
{
switch (ch)
{
case '+': return op1+op2; break;
case '-': return op1-op2; break;
case '*': return op1*op2; break;
case '/': return op1/op2; break;
case '$': return pow(op1,op2);break; //calling power calculating function using “math.h”
}
}
No comments:
Post a Comment