Write a program for Postfix Evaluation using Stack ? For example if we have an expression 432*+5- then it should return 5.
Algorithm :
1) Scan the expression from left to right .
2) Initialize an empty Stack .
3) Repeat the below 4 and 5 till all the characters are scanned .
4) If scan character is an operand , push it into Stack .
5) If the scanned character is operator and if the operator is unary then pop one element form the stack . If the operator is binary then pop two element form the stack . After popping the elements , apply the operator to those popped elements and push the result back to the stack.
6) After the scanning of all the character only element will be left in the Stack.
7) Return the top of stack as result.
Visualization of above algorithm :
1) Initially we have only expression and an empty Stack .
2) Now we will push 4 ,3 and 2 into the Stack .
3) Since the next character is an operator and even it is binary operator hence we will pop two elements form the Stack (2 and 3 ) and apply operator on them 2*3 = 6 . Push the result( 6 ) back to stack.
4) Now next character is also an operator and it is binary operator so we will pop two elements form the Stack (6 and 4) and apply operator on them 6+4 = 10. Push the result back to Stack.
5) Push 5 into the stack .
6) Next character is a binary operator. Hence pop both the element form the Stack and apply operation on them . 10-5 =5 . Push the result back to Stack.
7 ) Return stack top element .
Implementation :
Time Complexity : O(n)
Space complexity : O(n).
Note : To keep the things simple we have just implemented using binary operator. Above program can be easily extend for u nary operator as well.
Please comment if you like the above comment or if you find any mistake.
Algorithm :
1) Scan the expression from left to right .
2) Initialize an empty Stack .
3) Repeat the below 4 and 5 till all the characters are scanned .
4) If scan character is an operand , push it into Stack .
5) If the scanned character is operator and if the operator is unary then pop one element form the stack . If the operator is binary then pop two element form the stack . After popping the elements , apply the operator to those popped elements and push the result back to the stack.
6) After the scanning of all the character only element will be left in the Stack.
7) Return the top of stack as result.
Visualization of above algorithm :
1) Initially we have only expression and an empty Stack .
2) Now we will push 4 ,3 and 2 into the Stack .
5) Push 5 into the stack .
7 ) Return stack top element .
Implementation :
public class PostfixEvaluation {
public static void main(String args[])
{
String
expression ="432*+5-";
int result=evaluatePostfixExp(expression);
System.out.println("Result:"+result);
}
private static int
evaluatePostfixExp(String expression) {
java.util.Stack<Integer>st
=
new
java.util.Stack<Integer>();
int i=0;
int len=
expression.length();
while(i<len)
{
char ch =
expression.charAt(i);
if(ch=='+' || ch=='-' || ch=='*' || ch=='/' )
{
int num2=st.pop();
int num1=st.pop();
switch(ch)
{
case '+':st.push(num1+num2);break;
case '-':st.push(num1-num2);break;
case '*':st.push(num1*num2);break;
case '/':st.push(num1/num2);break;
}
}
else
{
st.push(new Integer(Character.digit(ch,10))
);
}
i++;
}
return (Integer)st.pop();
}
}
Time Complexity : O(n)
Space complexity : O(n).
Note : To keep the things simple we have just implemented using binary operator. Above program can be easily extend for u nary operator as well.
Please comment if you like the above comment or if you find any mistake.
No comments:
Post a Comment