Page 160 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES
P. 160
Unit 9: Stacks
If ch is an operator i.e.* , /, +, -, or ( Notes
{
If stack is empty push ch onto stack;
Else check the item op at the top of the stack;
while (more items in the stack &&
priority(ch) <= priority (op) )
{
pop op and append it to the output, provided it is not an open parenthesis
op = top element of stack
}
push ch onto stack
}
If ch is right parenthesis ‘)’
Pop items from stack until left parenthesis reached
Pop left parenthesis and discard both left and right parenthesis
}/* now no more characters in the infix expression*/
Pop remaining items in the stack to the output.
Example:
Using a stack to convert an Infix expression into its corresponding postfix form
Consider the following expressions with the infix notation. We want to transform these into
postfix expressions using a stack. We also trace the state of the operator stack as each character of
the infix expression is processed.
The contents of the operator stack at the indicated points in the infix expressions (points A, B and
C) are shown below for each case.
1.
Resulting Postfix Expression: M P Q * +
LOVELY PROFESSIONAL UNIVERSITY 153
