Stacks: Evaluation of Expression

Evaluation of Expression

 

Algorithm for evaluation of postfix

1. Read the postfix expression from left to right.

2. If the input symbol read is an operand then push it onto the stack.

3. If the operator is read POP two operands and perform arithmetic operations if

operator is

+         then result = operand 1 + operand 2

‒          then result = operand 1 ‒ operand 2

*         then result = operand 1 * operand 2

/          then result = operand 1 / operand 2

4. Push the result onto the stack.

5. Repeat steps 1 ‒ 4 till the postfix expression is not over.

For example: Consider postfix expression ‒

AB + C ‒ BA + C $ ‒ for A = 1, B = 2 and C = 3

Now as per the algorithm of postfix expression evaluation, we scan the input from left to right. If operand comes we push them onto the stack and if we read any operator, we must pop two operands and perform the operation using that operator. Here $ is taken as exponential operator.

C++ Program

/***************************************************************************

Program to evaluate a given postfix expression.

***************************************************************************/

#include<iostream>

#include<cstdlib>

#include<cmath>

using namespace std;

#define size 80

class EVAL

{

/*declaration of stack data structure*/

private:

struct stack

{

   double s[size];

   int top;

}st;

public:

double post(char post[]);

void push(double);

double pop();

};

double EVAL::post(char exp[])

{

   char ch,*type;

   double result, val, op1, op2;

   int i;

   st.top = 0;

   i=0;

   ch = exp[i];

   while (ch !='$' )

   {

      if (ch >= '0' && ch <= '9')

      type="operand";

      else if ( ch = = '+' ch = = '‒'||

      ch = = '*' || ch = = '/ '  | |

      ch = = '˄')

      type="operator";

if(strcmp(type,"operand")==0)/*if the character is operand*/

{

val = ch ‒ 48;    The characters '0', '1', ... '9' will be converted to their values, so that they will perform arithmetic operation.

push( val);

}

else

if (strcmp(type, "operator")= =0)/*if it is operator*/

{

op2 = pop();

op1= pop(); //popping two operands to perform arithmetic operation

switch(ch)

{

   case '+': result = op1 + op2;

      break;

   case' ‒ ': result = op1 ‒ op2;

      break;

   case: '*' : result = op1 * op2;

      break;

   case '/' :  result = op1 / op2;

      break;

   case '˄' result = pow(op1,op2);

      break;

}/* switch */   Finally result will be pushed onto the stack.

push(result);

}

   i++;

   ch‒exp[i];

} /* while */

result = pop(); /*pop the result*/

return(result);

}

void EVAL::push(double val)

{

   if (st.top+1 >= size)

         cout<<"\nStack is Full\n";

   st.top++;

   st.s[st.top] = val;

}

double EVAL::pop()

double val;

if(st.top = = ‒1)

cout<<"\nStack is Empty\n";

val = st.s[st.top];

st.top‒ ‒;

return(val);

}

void main()

{

   char exp[size];

   int len;

   double Result;

   EVAL obj:

   clrscr();

   cout<<"Enter the postfix Expression\n";

   cin>>exp;

   len = strlen(exp);

   exp[len] '$'; /* Append $ at the end as a endmarker*/

   Result = obj. post(exp);

   cout<<"Tho Value of the expression is <<Result;

   getch();

   exit(0);

}

Output

Enter the postfix Expression

12+34*+

Tho Value of the expression is 15

 

Logic of evaluation of postfix expression [Refer the above program]

Let us take some example of postfix expression and try to evaluate it

123+*

Step 1:

Assume the array exp [ ] contains the input

The $ symbol is used as an end marker. Read from first element of the array if it is operand push it onto the stack.

Step 2: If the operator is read pop two operands

Step 3:

Again pop two operands and perform the operation.

Step 4:

At this point the stack is empty and the input is read as $. So here stop the evaluation procedure and return the result = 5.

Example : 1

Evaluate the following expression using stack 5 6 2+ * 8 4 / –.

Solution :

The result of evaluation is 38.

Example : 2

Write the procedure to convert the infix expression to postfix expression and steps involved in evaluating the postfix expression. Convert the expression A‒(B/C+(D%E*F)/F)*H to postfix form. Evaluate the given postfix expression 934*8 + 4 / ‒

Solution:

Procedure to convert infix to postfix  : Refer previous section.

Conversion of A‒(B/C+(D%E*F)/F)*H

Postfix Form is: A B C / DE F *% F / + H * ‒

The result of evaluation is 4