Page 158 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES
P. 158
Unit 9: Stacks
3. (A B + ) C * : Convert multiplication Notes
4. A B + C * : Postfix form
Order of precedence for operators:
multiplication (*) and division (/)
addition (+) and subtraction (-)
The association is assumed to be left to right.
i.e. a + b + c = (a + b) + c = ab + c +
Evaluating a Postfix Expression
We can evaluate a postfix expression using a stack. Each operator in a postfix string corresponds
to the previous two operands. Each time we read an operand we push it onto a stack. When we
reach an operator its associated operands (the top two elements on the stack) are popped out
from the stack.
We then perform the indicated operation on them and push the result on top of the stack so that
it will be available for use as one of the operands for the next operator .
The following example shows how a postfix expression can be evaluated using a stack.
Example:
6 5 2 3 + 8 * + 3 + *
Figure 9.15: Evaluation of Postfix Expression using Stack
Source: http://www.eecs.ucf.edu/courses/cop3502h/spr2007/stacks.pdf
LOVELY PROFESSIONAL UNIVERSITY 151
