Stacks: Arithmetic Expressions

Arithmetic Expressionsang

 

• There are three types of expressions :

1. Infix Expression

2. Postfix Expression

3. Prefix Expression

One of the application of stack is conversion of expression. First of all, let us see these expressions with the help of examples.

1. Infix Expression :

In this type of expressions the arrangement of operands and operator is as follows.

Postfix expression = Operand1 operand operator

For example

1. (a+b)

2. (a+b) * (c ‒ d)

3. (a+b/e) * (d+f)

Parenthesis can be used in these expressions infix expression are the most natural way of representing the expressions.

2. Postfix Expression :

In this type of expressions the arrangement of operands and operator is as follows

Infix Expression = operand1 operator operand2

For example

1. ab+

2. ab + cd ‒ *

3. ab + e/df + *

In postfix expression there is no parenthesis used. All the corresponding operands come first and then operator can be placed.

3. Prefix Expression :

In prefix expression the arrangement of operands and operators is as follows.

Prefix expression = Operator operand1 operand2

For example

1. + ab

2. *+ ab ‒ cd

3. */ +abe+df

In prefix expression, there is no parenthesis used. All the corresponding operators come first and then operands are arranged.

 

Conversion from Infix to Postfix Expression

• The most important thing in the conversion procedure is to know the priorities of the operators being used in it. This helps in determining the order of evaluation of operands.

• There are certain rules which has to be followed while coverting infix expression to postfix form :

1. The expression is to be read from left to right.

2. Read one character at a time from infix expression.

3. Make use of stack to store the operators.

4. There should not be any parenthesis in the postfix form.

Let us see an algorithm for it.

 

Algorithm for conversion of infix to postfix form:

1. Read the expression from left to right.

2. If the input symbol read is '(' then push it onto the stack.

3. If the input symbol read is an operand then place it in postfix expression.

4. If the input symbol read is an operator then

a) Check if the precedence of the operator which is in the stack has greater precedence than the precedence of the operator read, if so then remove that symbol from stack and place it in the postfix expression. Repeat step 4

(a) till you get the operator in the stack has greater precedence than the operator being read.

b) Otherwise push the operator being read onto the stack.

5. If the input symbol read is a closing parenthesis ')' then pop all the operators from the stack, place them in postfix expression till the opening parenthesis is not popped. The '(' should not be place in the postfix expression.

6. Finally print the postfix expression.

Let us see the procedure with some examples.

Example : A*B + C $

Example :

When closing parenthesis comes pop everything and print except '('.

So finally the converted expression is

AB+CD ‒ *

C++ Program

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

Program for conversion of Infix expression to Postfix form.

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

#include<iostream>

using namespace std;

class EXP

{

private:

char post[40];

int top,st[20];

public:

EXP();

void postfix(char inf[40]);

void push(int);

char pop();

};

EXP::EXP()

{

   top = 0;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Postfix function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void EXP: postfix(char inf[40])

{

int i,j=0;

for(i=0;inf[i]!='\0';i++)

{

   switch(inf[i])

   {

      case '+': while (st[top] >= 1)

           post[j++] = pop();

           push(1);

           break;

      case '‒' : while(st[top] >= 1)

           post[j++] = pop();

           push(2);

           break;

      case '*': while(st[top] >= 3)

           postlj++] = pop();

           push(3);

           break;

      case '/' : while(st[top] >= 3)

           post[j++]= pop();

           push(4);

           break;

      case '˄' :

           while(st[top] >= 4)

              postlj++] = pop();

           push(5);

           break;

      case '(' : push(0);

           break;

      case ')': while(st[top] = 0)

                post[j++] = pop();

           top‒‒;

           break;

      default: post [j++] = inf[i];

}

}

while(top>0)

post[i++] = pop();

cout<<"\n\tPostfix expression is =>\n\n\t\t "<<post;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

Push function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void EXP::push(int ele)

{

   top++;

   st[top] = ele;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

pop Function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

char EXP::pop()

{

   int el;

   char e;

   el = st[top];

   top‒‒;

   switch(el)

   {

      case 1: e = '+';

           break;

      case 2: e = '‒';

           break;

      case 3: e =  '*',

           break;

      case 4: e = '/ ';

           break;

      case 5: e='˄';

           break;

   }

return(e);

}

void main(void)

{

   EXP obj;

   char inf[40];

   clrscr();

   cout<<"\n\tEnter the infix expression :: \n";

   cin>>inf;

   cout<<"The infox expression entered by you is..."<<inf;

   obj.postfix(inf);

   getch();

}

Output

Enter the infix expression ::

(a+b)*(c‒d)

The infox expression entered by you is...(a+b)*(c‒d)

Postfix expression is =>

ab+cd‒*

 

Example: 1

Write an algorithm to convert an infix to postfix expression Trace the algorithm to convert the infix expression "(a+b)*c/d+e/f" to a postifx expression. Explain the need for infix and postfix expressions.

Solution :

Need for infix and postfix expressions :

The infix expressions are used in mathematical expressions and postfix expressions are used in compilers for checking the syntax of an expression. The postfix expressions are also used in evaluating the expressions.

Example: 2

Convert the following infix expression to the postfix expression. Show stack traces.

i) A/B$C+D*E/F‒G+H

ii) (A+B)*D+E/(F+G*D)+C.

Solution: i)

ii)

 

Example: 3

Simulate the conversion of infix to postfix expression using stack for the following expression : 3 ‒ (4/2) + (1*5) + 6.

Solution:

The equivalent postfix expression is 342/‒15*+6+

Review Questions

1. With examples explain how a stack can be used to convert an infix expression to a postfix expression.

2. Explain the applications of stack in detail.

3. Explain the process of conversion from infix expression to postfix using stack.