The greatest mistake you can make in life is to be continually fearing you will make one

Monday, 8 February 2010

Evaluating a Postfix Expression

Introduction:
  • Postfix expressions are parenthesis free notation and precedence is already defined so evaluation is done very easily.
  • Example of Postfix expression are
  1. AB+C*
  2. 234*+5- 
Algorithm for Postfix evaluation:
  1. Read the tokens from the postfix string one at a time from left to right
  2. Initialize an empty stack
  3. If the token is an operand, push the operand in to the stack
  4. If the token is an operator,then there will be at least 2 operands in the stack.Pop the top 2 elements from the stack and apply the operator to the poped out 2 elements.The result of this operation is push back in to the stack.
  5. After all the characters are read,only one element is present in the stack that is the result  
Example for Postfix Evaluation:

Example1:
Postfix expression-->234*+5- 
Solution: 
  1. Initially the stack is empty.
  2. Read the token 2. 2 is an operand.Push 2 in to the stack. now stack->2
  3. Read the token 3.3 is an operand. Push 3 in to the stack. now stack->32
  4. Read the token 4.4 is an operand. Push 4 in to the stack. now stack->432 
  5. Read the token *.* is an operator. pop the top 2 elements 4,3 from the stack and 4*3=12.then push 12 in to the stack. now stack->12 2 
  6. Read the token +.+is an operator.pop the 2 elements 12,2 from the stack and 12+2=12.then push 12 in to the stack. now stack->14
  7. Read the token 5.5 is an operand.Push 5 in to the stack. now stack->5 14
  8. Read the token -.- is an operator.pop the 2 elements 14,5 from the stack and 14-5=9.then push 9 in to the stack. now stack->9
  9. result=9  
The value for 234*+5- is 9 

Exercise for Postfix Evaluation: 
  1. 234+56**+
  2. 623+-382/+* 

6 comments:

  1. 1. 234+56**+is 212
    2. 623+-382/+*is 6

    ReplyDelete
  2. The Correct answer is
    1. 234+56**+is 212
    2. 623+-382/+*is 7

    ReplyDelete
  3. 623 + – 382 / + * 2 $ 3 + what is the answer?

    ReplyDelete
    Replies
    1. 623 + – 382 / + * 2 $ 3 + =52

      Delete
  4. Wats the approach numbers with more than one digit?

    ReplyDelete
  5. 234*+5- please explain why not take 5-14 then result as -9..according to the value stored in stack.. in the top example.

    ReplyDelete