/* related posts with thumb nails */

Process of evaluating postfix expression:

Postfix expression uses operator after the operands and it does not include parenthesis. You need not know the priorities of the operators while evaluating it

Ex: Infix Expression: “(2+3) * 4 + 5 * 2”

Postfix expression: “2 3 + 4 * 5 2 * +”

Result after evaluation: “30”

Process of evaluating “postfix expression”:

Initially stack must be empty and the postfix expression is scanned from left to right one at a time.

1. If a number is encountered it is pushed onto the stack

2. If an operator is encountered, pop two operands from the stack and compute the result by using operator on the two operands. Push the result onto the stack.

3. Repeat the same process till the end of the equation

4. Finally, pop the result from stack and print it.

Consider the Postfix expression “2 3 + 4 * 5 2 * +”. The evaluation of the expression is tabulated below.

Symbol

Computation

Stack Contents

2

2

3

2, 3

+

2 + 3

5

4

5, 4

*

5 * 4

20

5

20, 5

2

20, 5, 2

*

5 * 2

20, 10

+

20 + 10

30

Program to evaluate postfix expression:

import java.io.*;

import java.util.*;

class Stack

{

private int a[]=new int[20];

int top;

Stack()

{

top=0;

}

public void push(int v)

{

if(top<20)

a[top++]=v;

else

System.out.println("Overflow");

}

public int pop()

{

if(top>0)

return a[--top];

else

{

System.out.println("Underflow");

return -1;

}

}

public boolean isEmpty()

{

return top==0;

}

}

class Postfix

{

public static void main(String as[]) throws Exception

{

int a,b,c=0;

String str,s;

Stack s1=new Stack();

int i;

InputStreamReader isr=new InputStreamReader(System.in);

BufferedReader br=new BufferedReader(isr);

System.out.print("Enter Postfix expression:");

str=br.readLine();

StringTokenizer st=new StringTokenizer(str,",");

while(st.hasMoreTokens())

{

s=st.nextToken();

if(("+-*/").indexOf(s)>=0)

{

b=s1.pop();

a=s1.pop();

switch(s.charAt(0))

{

case '+':c=a+b;

break;

case '-':c=a-b;

break;

case '*':c=a*b;

break;

case '/':c=a/b;

break;

}

s1.push(c);

}

else

s1.push(Integer.parseInt(s));

}

System.out.println("Result="+s1.pop());

}

}

/* Output */

/* you may give postfix of (2*3)+(4/2) Note: Separate operands and operators with commas*/

Enter Postfix expression:2,3,*,4,2,/,+

Result=8

Related Topics:

0 comments:

Post a Comment