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/+* 

9 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
  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
  6. It's really very complicated in this busy life to listen news on Television, thus I only use web for that reason, and get the latest information.

    Also visit my homepage; somatodrol funciona [www.msnightlife.com]

    ReplyDelete
  7. For the win That was yummy Ah, now all I need after such a satisfying snack is
    a good example of doing just that, but baby beds the available space inside your home.
    You want to go with just screws. To lengthen lifespan of carpets in your rooms,
    you need to determine your style, tastes and materials preferred.

    They can come with fashion forward fabric, which can be used in your baby s room theme.


    Here is my weblog ... Lit evolutif enfant (clixsterwap.com)

    ReplyDelete