## Chapter 7Stacks

7.4 More Complex Stack Applications

<1>

infix notation ===> 2 + 3
(polish)prefix notation ===> + 2 3
(polish)postfix notation ===> 2 3 +

ex. 7 + ( 3*5 ) -4
prefix
-+7 * 3 5 4
postfix
7 3 5 * + 4 -

prefix and postfix notation requires no parenthese

• postfix is easier than prefix in terms os expresion evaluation

ex.

```(( 3x + 5) - 8 z) - 9y /5

(((3*x) + 5) - (8*z)) - ((9*y)/5))

prefix    - - + * 3 x 5 * 8 z / *9 y 5

postfix   3 x *5 + 8 z * - 9 y * 5 / -
```

<2> postfix notation:

3 x * 5 + 8 z * - 9 y * 5 / -

1. some assumptions

1. numbers separating by space
2. no negative number

2. one stack : number stack

```    there  is no need for operation stack
because
each operation is used when it is read
```

eq. //ref. 7-10 on p.334

<3> Infix to postfix :

how to translate infix expression to postfix expression

ie.

((( A + 7 ) * ( B / C )) - ( 2 * D ))

===> A 7 + B C / * 2 D * -

1. fully parenthesized in fix expression

Idea :

move the operation to the location of crresponding
and remore all parenthesis.

eq.

===> 3 x * 5 + 8 z * - 9 y * 5 / -

how : use stack to store " ( " and operator

ex. ((( A + 7 ) * ( B / C ) ) - ( 2 * D ))

eac " ) " triggers on pop action on stack

2. not fully parenthesized infix expression

2 * ( A - B ) + 3 + C

1. Strategy : used the precedence of operator
ex. convent
3 * x + ( y - 7 ) - z

2. precedence
1. ( ) first
2. * / first + - later
3. from left to right for * / or + -

3. homework :
1. A + 7 * ( B - C ) - 2 * D

2. 3 / A + ( B + 12 ) - C