Ticker

6/recent/ticker-posts

Evaluate postfix expression using stack with example

 

Expression is combination of  operand and operator. Three type of expression that are these

Prefix expression.(+ab).

Infix expression(a+b).

Postfix expression.(ab+).

To evaluate expression if expression in infix form than convert into postfix form and than postfix expression is solved using stack.

Steps to evaluate postfix expression using stack 

P is an postfix expression to solve this postfix expression stack is used to hold operands and  RESULT hold the result of arithmetic expression. 

Step 1.  Add right parenthesis ")" at the end of P.

Step 2. Scan postfix expression P from left to right and repeat step 3 and 4 until the ")" is encountered.

Step 3. If an operand is encountered put it on STACK.

Step 4. If an operator "op"  is encountered then 

Remove the top two element from the stack  and evaluate  A op B and place the result on the stack.

Step 5. Set  RESULT equal to the top element on STACK.

Step 6. Exit.

Example

Evaluate postfix expression P using stack 

P: 3, 2, 1,+,*,13,3 ,/,-

Solution

First add right parentheses at the end of the P.

3,2,1,+,*,12,3,/,- ,)

element of P scanned left to right and store in stack if operand 

Symbol scanned                      STACK 

3                                                  3

2                                                  3,2

1                                                   3,2,1

+                                                   3,3

*                                                  9

12                                                9,12

3                                                  9,12,3

/                                                   9,4

-                                                    5

)                                             


So  Result=5  after solving postfix expression using stack .

First 3,2,1, is operand simply push on STACK.

Operand "+" encountered  remove top two element of stack and evaluate and again store result in stack.

2+1=3  

Operand "*" encountered  remove top two element of stack and evaluate and again store result in stack.

3*3=9.

12,3 is operand simply push on stack.

Operand "/" encountered  remove top two element of stack and evaluate and again store result in stack.

12/3=4

Operand "-" encountered  remove top two element of stack and evaluate and again store result in stack.

9-4=5

sentinel element ")" encountered then exit.


Post a Comment

0 Comments