DATA STRUCTURE AND ALGORITHM Dijkstra’s Stack

• Value: push onto the value stack. • 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. • 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 stack

value stack

Dr. Dao Nam Anh

1

Data Structure and Algorithm

Resource - Reference

• Value: push onto the value stack. Slides of Robert Sedgewick, and Kevin Wayne, • Operator: push onto the operator stack. edit by Dao Nam Anh. Major Reference: • Right parenthesis: 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

operator stack

value stack

2

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • Value: push onto the value stack. • Operator: push onto the operator stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. applying that operator to those values onto the operand stack. • Left parenthesis: ignore. • Left parenthesis: ignore.

operator stack operator stack

value stack value stack

infix expression (fully parenthesized)

( ( 1 1 + + ( ( ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

operand

3

operator Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

operator stack

value stack

4

( ( 1 1 + + ( ( ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

operator stack

value stack

5

( 1 1 + + ( ( ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

1

operator stack

value stack

6

( 1 + + ( ( ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

1

operator stack

value stack

7

( 1 + + ( ( ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

1 +

operator stack

value stack

8

( 1 + ( ( ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

1 +

operator stack

value stack

9

( 1 + ( ( ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

1 +

operator stack

value stack

10

( 1 + ( ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

1 +

operator stack

value stack

11

( 1 + ( ( 2 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

2

1 +

operator stack

value stack

12

( 1 + ( ( 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

2

1 +

operator stack

value stack

13

( 1 + ( ( 2 + + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

2 +

1 +

operator stack

value stack

14

( 1 + ( ( 2 + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

2 +

1 +

operator stack

value stack

15

( 1 + ( ( 2 + 3 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

3

2 +

1 +

operator stack

value stack

16

( 1 + ( ( 2 + 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

3

2 +

1 +

operator stack

value stack

17

( 1 + ( ( 2 + 3 ) ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

3 + 2

1 +

operator stack

value stack

18

( 1 + ( ( 2 + 3 ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

3 + 2 = 5

1 +

operator stack

value stack

19

( 1 + ( ( 2 + 3 ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5

1 +

operator stack

value stack

20

( 1 + ( ( 2 + 3 ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5

1 +

operator stack

value stack

21

( 1 + ( ( 2 + 3 ) * * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5 *

1 +

operator stack

value stack

22

( 1 + ( ( 2 + 3 ) * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5 *

1 +

operator stack

value stack

23

( 1 + ( ( 2 + 3 ) * ( ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5 *

1 +

operator stack

value stack

24

( 1 + ( ( 2 + 3 ) * ( 4 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

4

5 *

1 +

operator stack

value stack

25

( 1 + ( ( 2 + 3 ) * ( 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

4

5 *

1 +

operator stack

value stack

26

( 1 + ( ( 2 + 3 ) * ( 4 * * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

4 *

5 *

1 +

operator stack

value stack

27

( 1 + ( ( 2 + 3 ) * ( 4 * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

4 *

5 *

1 +

operator stack

value stack

28

( 1 + ( ( 2 + 3 ) * ( 4 * 5 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5

4 *

5 *

1 +

operator stack

value stack

29

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5

4 *

5 *

1 +

operator stack

value stack

30

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5 * 4

5 *

1 +

operator stack

value stack

31

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

5 * 4 = 20

5 *

1 +

operator stack

value stack

32

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

20

5 *

1 +

operator stack

value stack

33

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

20

5 *

1 +

operator stack

value stack

34

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

20 * 5

1 +

operator stack

value stack

35

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

20 * 5 = 100

1 +

operator stack

value stack

36

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

100

1 +

operator stack

value stack

37

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

100

1 +

operator stack

value stack

38

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

100 + 1

operator stack

value stack

39

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

100 + 1 = 101

operator stack

value stack

40

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

101

operator stack

value stack

41

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

101

operator stack

value stack

42

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

Data Structure and Algorithm

Thuật toán 2 ngăn xếp của Dijkstra

• Value: push onto the value stack. • 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. • Left parenthesis: ignore.

result

101

operator stack

value stack

43

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

Data Structure and Algorithm