Bài giảng cấu trúc dữ liệu và giải thuật thuật toán 2 ngăn xếp của dijkstra TS đào nam anh
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (593.53 KB, 43 trang )
•
•
•
Value: push onto the value stack.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
DATA
STRUCTURE
AND
ALGORITHM
applying
that operator
to those values onto
the operand
stack.
•
Dijkstra’s Stack
Left parenthesis: ignore.
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Thuật toán 2 ngăn xếp của Dijkstra
operator
value stack
Dr. Dao Nam
Anh stack
Data Structure and Algorithm
1
Resource - Reference
•
•
•
Value: push onto the value stack.
Slides of
Robert
Sedgewick,
and
Operator:
push
onto the
operator stack.
Kevin Wayne,
editparenthesis:
by Dao Nam
Anh. Major
Reference:
Right
pop operator
and two
values; push the result of
applying that operator to those values onto the operand stack.
•
Robert Sedgewick, and Kevin Wayne, “Algorithms”
• Left parenthesis:
ignore.
Princeton University,
2011, Addison Wesley
•
Algorithm in C (Parts 1-5 Bundle)- Third Edition by
Robert Sedgewick, Addison-Wesley
value stack
operator stack
Data Structure and Algorithm
2
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
(
1
+
operator stack
value stack
infix expression
(fully parenthesized)
(
(
2
operand
+
3
)
*
(
4
*
5
operator
Data Structure
and Algorithm
)
)
)
3
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
4
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
5
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
1
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
6
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
1
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
7
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
8
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
9
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
10
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
11
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
2
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
12
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
2
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
13
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
2
+
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
14
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
2
+
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
15
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
3
2
+
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
16
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
3
2
+
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
17
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
3
1
1
+
(
(
2
+
2
+
operator stack
value stack
(
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
18
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
3
1
1
+
(
(
2
+
2
=
5
+
operator stack
value stack
(
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
19
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
5
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
20
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
5
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
21
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
5
*
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
22
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
5
*
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
23
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
5
*
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
24
Thuật toán 2 ngăn xếp của Dijkstra
•
•
•
Value: push onto the value stack.
•
Left parenthesis: ignore.
Operator: push onto the operator stack.
Right parenthesis: pop operator and two values; push the result of
applying that operator to those values onto the operand stack.
4
5
*
1
+
operator stack
value stack
(
1
+
(
(
2
+
3
)
*
(
4
*
5
Data Structure and Algorithm
)
)
)
25
