CSC518 - Application of Stacks
There are many applications that require the use of stacks to facilitate the computerized
problem solving process such as the following:
1. Invocation of nested functions or recursive functions.
2. Conversion from infix to postfix notation
3. Evaluation of postfix expression
4. Checking balance parentheses for open ‘(‘ and close ‘)’.
5. Checking matching parentheses ‘{‘,’[‘, ‘(‘ and ‘}’,’]’,’)’.
6. Evaluation of complex arithmetic problems.
Arithmetic Applications
Every arithmetic operation contains two major components: operator (represents an
instruction) and operand(represents data).
Arithmetic operators:
Symbol Name
$ Power
* Multiplication
/ Division
+ Addition
- Subtraction
Precedence Rules
( ) parentheses Highest
$ Power
*, / Multiplication and Division
+,- Addition and subtraction Lowest
Types of Arithmetic Expressions
Infix, Postfix and Prefix notations are three different but equivalent ways of writing
expressions. It is easiest to demonstrate the differences by looking at examples of
operators that take two operands.
Prepared by : Zulaile Mabni
Infix notation: X + Y
Operators are written in-between their operands. This is the usual way we write
expressions. An expression such as A * ( B + C ) / D is usually taken to mean
something like: "First add B and C together, then multiply the result by A, then
divide by D to give the final answer."
Infix notation needs extra information to make the order of evaluation of the
operators clear: rules built into the language about operator precedence and
associativity, and brackets ( ) to allow users to override these rules. For example,
the usual rules for associativity say that we perform operations from left to right,
so the multiplication by A is assumed to come before the division by D. Similarly,
the usual rules for precedence say that we perform multiplication and division
before we perform addition and subtraction.
Postfix notation (also known as "Reverse Polish notation"): X Y +
Operators are written after their operands. The infix expression given above is
equivalent to:
ABC+*D/
The order of evaluation of operators is always left-to-right, and brackets cannot
be used to change this order. Because the "+" is to the left of the "*" in the
example above, the addition must be performed before the multiplication.
Operators act on values immediately to the left of them. For example, the "+"
above uses the "B" and "C". We can add (totally unnecessary) brackets to make
this explicit:
( (A (B C +) *) D /)
Thus, the "*" uses the two values immediately preceding: "A", and the result of
the addition. Similarly, the "/" uses the result of the multiplication and the "D".
Prefix notation (also known as "Polish notation"): + X Y
Operators are written before their operands. The expressions given above are
equivalent to:
/*A+BCD
As for Postfix, operators are evaluated left-to-right and brackets are superfluous.
Operators act on the two nearest values on the right. I have again added (totally
unnecessary) brackets to make this clear:
(/ (* A (+ B C) ) D)
Although Prefix "operators are evaluated left-to-right", they use values to their
right, and if these values themselves involve computations then this changes the
Prepared by : Zulaile Mabni
order that the operators have to be evaluated in. In the example above, although
the division is the first operator on the left, it acts on the result of the
multiplication, and so the multiplication has to happen before the division (and
similarly the addition has to happen before the multiplication).
Because Postfix operators use values to their left, any values involving
computations will already have been calculated as we go left-to-right, and so the
order of evaluation of the operators is not disrupted in the same way as in Prefix
expressions.
In all three versions, the operands occur in the same order, and just the operators have
to be moved to keep the meaning correct. (This is particularly important for asymmetric
operators like subtraction and division: A - B does not mean the same as B - A; the
former is equivalent to A B - or - A B, the latter to B A - or - B A).
Examples:
Infix Postfix Prefix Notes
multiply A and B,
A*B+C/D AB*CD/+ +*AB/CD divide C by D,
add the results
add B and C,
A * (B + C) / D ABC+*D/ /*A+BCD multiply by A,
divide by D
divide C by D,
A * (B + C / D) ABCD/+* *A+B/CD add B,
multiply by A
Converting between these notations
The most straightforward method is to start by inserting all the implicit brackets that
show the order of evaluation e.g.:
Infix Postfix Prefix
( (A * B) + (C / D) ) ( (A B *) (C D /) +) (+ (* A B) (/ C D) )
((A * (B + C) ) / D) ( (A (B C +) *) D /) (/ (* A (+ B C) ) D)
(A * (B + (C / D) ) ) (A (B (C D /) +) *) (* A (+ B (/ C D) ) )
You can convert directly between these bracketed forms simply by moving the operator
within the brackets e.g. (X + Y) or (X Y +) or (+ X Y). Repeat this for all the operators in
an expression, and finally remove any superfluous brackets.
Prepared by : Zulaile Mabni
Evaluation of Postfix Expressions using a Stack
Evaluating an expression using a stack is only allowed for postfix expressions.
An infix or a prefix expression must be converted into its postfix form before it can be
evaluated.
Algorithm to evaluate a postfix expression:
1. Create an empty stack
2. while not end of expression
get an item
if the item is a(n) operand
push onto stack
if the item is a(n) operator
pop operand2
pop operand1
evaluate expression
push result back on stack
3. when end of expression, the only item left on stack is the value of the expression,
pop the item.
Example:
Evaluate the following postfix expression:
42–15$+
5
2 1 1 1
Stack 4 4 2 2 2 2 3
postfix 4 2 - 1 5 $ +
Answer : 3
Prepared by : Zulaile Mabni
Conversion from infix to postfix notation
Example:
Infix expression : A + ( B – C / D ) * E
Infix Stack Postfix
A Empty A
+ + A
( +( A
B +( AB
- +(- AB
C +(- ABC
/ +(-/ ABC
D +(-/ ABCD
) +(- ABCD/
+( ABCD/-
+ ABCD/-
* +* ABCD/-
E +* ABCD/-E
ABCD/-E*+
References :
Collin, Williams, Data Structures and The Java Collections Framework, 2nd Edition,
McGrawHill , 2005.
[Link]
Prepared by : Zulaile Mabni