Algorithm 19: Procedure to convert from Infix to Postfix Notation using Stack
Let INF be the infix expression and POSTF be the postfix expression
Astack type data structure called STACK s used for the conversion. PUSH and POP operations can be done on STACK
Exponent operator ^has highest priority, followed by *and /, followed by + and -
(
POSTFIX INF, POSTF) [Theprocedure converts infx expresson INFtopostix expressionPOSTFI
Step 1: Enclose the whole INF expression within a pair of brackets as (INF )
Step 2: Scan INF from left to right. Repeat steps 2 to 8 for each character in INF till the STACK is empty
Step 3: Let SYMBOL be the next scanned character
Step 4: If SYMBOL is an Operand
Add SYMBOL to POSTF
Step 5: Else If SYMBOL s an Opening Bracket i.e. Y'
a PUSH SYMBOL to STACK
Step 6: Else If SYMBOL S an Operator ® [Where ®sany operator like ^ ,-]
a Repeatedly POP from STACK and add to POSTF each stack-top operator which has the same or higher priority
than
b PUSH& to STACK,when stack-top operator has lower priority than &
Step 7: Else If SYMBOL S a Closing Bracket ')'
a Repeatedly POP from the STACK and add to POSTF each operator (on the top of the STACK) untlan Opening
Bracket isencoutered
b Remove the Opening Bracket ('from the STACK without adding it to POSTF
Step 8: End If
Step 9: End procedure
P2-15-42
440
K
Calculate the value of the expression.
Algorithm 20: Procedure to Calculate a Postfix expression using Stack
Let POSTF be the postfix expression to evaluate
stack type data structure called
A STACK s used forthe conversion. PUSH and POP operations can be done on STACK
POSTFDX EVAL (POSTF ) {The procedure calculates the value of a postfix expression POSTE
Step 1: Scan POSTF from left to right, one character at a time, and storethe scanned character in SYMBOL
Step 2: If SYMBOL s an operand
a. PUSH SYMBOL to STACK
Step 3: Else If SYMBOL S an operator {Where O can be *,t -}
a. POP operand from STACK and store in x
b. POP next operand from STACK and store in y
C Calculate y®x and PUSH the result back to the STACK (Note that the operation is yOX and not x®y}
Step 4: End If
Srep 5: Scan next SYMBOL from POSTF. If not end of expression, then goto Step 2
Step 6: The STACK contains the final result
Exar
