PowerPoint Presentation
1
a + b
infix form
+ a b
prefix form
a b +
postfix form
2
Postponement
Reverse Polish Notation
1. Infix to postfix transformation
– Manual transformation
– Algorithmic transformation
2. Evaluating postfix expressions
3
Infix to Postfix
Manual Transformation
a + 5 * b
4
Infix to Postfix: Manual Transformation
a +
5 * b
5
a +
5 b *
Infix to Postfix: Manual Transformation
6
a +
5 b *
Infix to Postfix: Manual Transformation
7
a + 5 * b
a +
5 * b
a +
5 b *
a +
5 b *
Infix to Postfix: Manual Transformation
8
Infix to Postfix
Manual Transformation
a + b * c – d / e
9
a + b * c – d / e
a b c * + d e / –
Infix to Postfix: Manual Transformation
10
Postponement
Reverse Polish Notation
1. Infix to postfix transformation
– Manual transformation
– Algorithmic transformation
2. Evaluating postfix expressions
11
Infix to Postfix
Algorithmic Transformation
a + 5 * b
12
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a
13
push
+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a
14
+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a 5
15
push
*
+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a 5
16
*
+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a 5 b
17
*
+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a 5 b *
18
a + 5 * b
a 5 b *
pop
+
Infix to Postfix: Algorithmic Transformation (STACK)
19
a + 5 * b
a 5 b * +
Infix to Postfix: Algorithmic Transformation (STACK)
20
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
(
(a – 2 *(b + c) – d * e) * f
push
21
(a – 2 *(b + c) – d * e) * f
(
a
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
22
(a – 2 *(b + c) – d * e) * f
(
a
push
–
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
23
(a – 2 *(b + c) – d * e) * f
(
a 2
–
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
24
(a – 2 *(b + c) – d * e) * f
(
a 2
–
push
*
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
25
(a – 2 *(b + c) – d * e) * f
(
a 2
–
push
*
(
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
26
(a – 2 *(b + c) – d * e) * f
(
a 2 b
–
*
(
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
27
(a – 2 *(b + c) – d * e) * f
(
a 2 b
–
*
(
push
+
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
28
(a – 2 *(b + c) – d * e) * f
(
a 2 b c
–
*
(
+
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
29
(a – 2 *(b + c) – d * e) * f
(
a 2 b c +
–
*
(
+
pop
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
30
(a – 2 *(b + c) – d * e) * f
(
a 2 b c +
–
*
(
pop, pop
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
31
(a – 2 *(b + c) – d * e) * f
(
a 2 b c + *
–
*
pop
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
32
(a – 2 *(b + c) – d * e) * f
(
a 2 b c + * –
–
pop, pop
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
33
(a – 2 *(b + c) – d * e) * f
(
a 2 b c + * –
pop, pop, push
–
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
34
(a – 2 *(b + c) – d * e) * f
(
a 2 b c + * – d
–
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
35
(a – 2 *(b + c) – d * e) * f
(
a 2 b c + * – d
–
push
*
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
36
(a – 2 *(b + c) – d * e) * f
(
a 2 b c + * – d e
–
*
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
37
(a – 2 *(b + c) – d * e) * f
pop
(
a 2 b c + * – d e *
–
*
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
38
(a – 2 *(b + c) – d * e) * f
pop, pop
(
a 2 b c + * – d e * –
–
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
39
(a – 2 *(b + c) – d * e) * f
(
pop, pop, pop
a 2 b c + * – d e * –
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
40
(a – 2 *(b + c) – d * e) * f
push
*
a 2 b c + * – d e * –
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
41
(a – 2 *(b + c) – d * e) * f
*
a 2 b c + * – d e * – f
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
42
(a – 2 *(b + c) – d * e) * f
pop
*
a 2 b c + * – d e * – f *
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
43
(a – 2 *(b + c) – d * e) * f
a 2 b c + * – d e * – f *
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140
44
Postponement
Reverse Polish Notation
1. Infix to postfix transformation
– Manual transformation
– Algorithmic transformation
2. Evaluating postfix expressions
45
Evaluating Postfix Expressions
7 2 3 * – 4 +
46
7 2 3 * – 4 +
Evaluating Postfix Expressions (STACK)
7
push
47
7
push
7 2 3 * – 4 +
2
Evaluating Postfix Expressions (STACK)
48
7
push
7 2 3 * – 4 +
2
3
Evaluating Postfix Expressions (STACK)
49
pop
7 2 3 * – 4 +
3
*
7
2
Evaluating Postfix Expressions (STACK)
50
pop, pop
7 2 3 * – 4 +
3
*
7
2
Evaluating Postfix Expressions (STACK)
51
7 2 3 * – 4 +
6
=
3
*
7
2
Evaluating Postfix Expressions (STACK)
52
7 2 3 * – 4 +
6
push
7
Evaluating Postfix Expressions (STACK)
53
7 2 3 * – 4 +
6
7
Evaluating Postfix Expressions (STACK)
54
7 2 3 * – 4 +
6
7
Evaluating Postfix Expressions (STACK)
55
7 2 3 * – 4 +
pop
7
6
–
Evaluating Postfix Expressions (STACK)
56
7 2 3 * – 4 +
pop, pop
6
–
7
Evaluating Postfix Expressions (STACK)
57
7 2 3 * – 4 +
6
–
7
1
=
Evaluating Postfix Expressions (STACK)
58
7 2 3 * – 4 +
1
push
Evaluating Postfix Expressions (STACK)
59
7 2 3 * – 4 +
1
Evaluating Postfix Expressions (STACK)
60
7 2 3 * – 4 +
1
push
4
Evaluating Postfix Expressions (STACK)
61
7 2 3 * – 4 +
4
1
Evaluating Postfix Expressions (STACK)
62
7 2 3 * – 4 +
pop
1
4
+
Evaluating Postfix Expressions (STACK)
63
7 2 3 * – 4 +
pop, pop
4
+
1
Evaluating Postfix Expressions (STACK)
64
7 2 3 * – 4 +
4
+
1
5
=
Evaluating Postfix Expressions (STACK)
65
7 2 3 * – 4 +
5
push
Evaluating Postfix Expressions (STACK)
66
7 2 3 * – 4 +
5
Evaluating Postfix Expressions (STACK)
67
Backtracking
Eight Queens Problem
A Brief History
“The n-queens problem is an old one that has been around for more than a century. Originally known as the 8-Queens problem, it has been studied by many famous mathematicians over the years, including the great German mathematician Karl Friedrich Gauss (1777-1855). The problem was generalized to n by n boards in 1850 by Franz Nauck. Since the 1960’s, with rapid developments in computer science, this problem has been used as an example of backtracking algorithms, etc.”
68
Applications to Mathematics and other Areas
“The queens problem is really a puzzle but, surprisingly, there are some practical applications such as
parallel memory storage schemes,
VLSI testing,
traffic control, and
deadlock prevention.
The problem is also illustrative of more practical problems whose solutions are permutations, of which there are many.
Furthermore, the solution technique, backtracking is very important, and is best learnt on simple examples such as the queens problem.”
69
Figure 4-16
70
1, 1
Q
1
4
3
2
1
2
3
4
71
1, 1
Q
Q
1
4
3
2
1
2
3
4
2, 3
72
1, 1
Q
?
?
?
?
Q
1
4
3
2
1
2
3
4
2, 3
73
1, 1
Q
1
4
3
2
1
2
3
4
74
Q
Q
1
4
3
2
1
2
3
4
1, 1
2, 4
75
Q
Q
Q
1
4
3
2
1
2
3
4
1, 1
2, 4
3, 2
76
Q
Q
Q
?
?
?
?
1
4
3
2
1
2
3
4
1, 1
2, 4
3, 2
77
Q
?
?
Q
1
4
3
2
1
2
3
4
1, 1
2, 4
78
Q
1
4
3
2
1
2
3
4
1, 1
79
1
4
3
2
1
2
3
4
80
Q
1
4
3
2
1
2
3
4
1, 2
81
Q
Q
1
4
3
2
1
2
3
4
1, 2
2, 4
82
Q
Q
Q
1
4
3
2
1
2
3
4
1, 2
2, 4
3, 1
83
Q
Q
Q
Q
1
4
3
2
1
2
3
4
4, 3
1, 2
2, 4
3, 1
Data Structures: A Pseudocode Approach with C
84
Figure 4-18
/docProps/thumbnail.jpeg