Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Thuật toán 2 ngăn xếp của Dijkstra - Đào Nam Anh

• 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. Data Structure and Algorithm 1 value stack operator stack DATA STRUCTURE AND ALGORITHM Dijkstra’s Stack CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Thuật toán 2 ngăn xếp của Dijkstra Dr. Dao Nam Anh • 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. Data Structure and Algorithm 2 value stack operator stack Resource - Reference Slides of Rober Sedgewick, and Kevin Wayne, edit by Dao Nam Anh. Major Refer nce: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • 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. Data Structure and Algorithm 3 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra operand operator infix expression (fully parenthesized) • 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. Data Structure and Algorithm 4 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) 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. Data Structure and Algorithm 5 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) 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. Data Structure and Algorithm 6 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 • 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. Data Structure and Algorithm 7 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 • 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. Data Structure and Algorithm 8 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + • 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. Data Structure and Algorithm 9 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + • 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. Data Structure and Algorithm 10 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + • 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. Data Structure and Algorithm 11 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + • 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. Data Structure and Algorithm 12 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + 2 • 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. Data Structure and Algorithm 13 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 2 1 + • 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. Data Structure and Algorithm 14 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 2 1 + + • 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. Data Structure and Algorithm 15 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 2 + 1 + • 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. Data Structure and Algorithm 16 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 2 + 1 + 3 • 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. Data Structure and Algorithm 17 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 2 + 3 1 + • 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. Data Structure and Algorithm 18 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 2+3 1 + • 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. Data Structure and Algorithm 19 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + 2+3 = 5 • 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. Data Structure and Algorithm 20 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + 5 • 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. Data Structure and Algorithm 21 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + 5 • 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. Data Structure and Algorithm 22 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + 5 * • 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. Data Structure and Algorithm 23 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 1 + 5 • 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. Data Structure and Algorithm 24 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 1 + 5 • 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. Data Structure and Algorithm 25 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 1 + 5 4 • 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. Data Structure and Algorithm 26 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 4 1 + 5 • 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. Data Structure and Algorithm 27 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 4 * 1 + 5 • 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. Data Structure and Algorithm 28 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 4 * 1 + 5 • 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. Data Structure and Algorithm 29 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 4 * 1 + 5 5 • 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. Data Structure and Algorithm 30 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 4 * 5 1 + 5 • 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. Data Structure and Algorithm 31 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 4*5 1 + 5 • 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. Data Structure and Algorithm 32 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 4*5 1 + 5 = 20 • 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. Data Structure and Algorithm 33 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 1 + 5 20 • 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. Data Structure and Algorithm 34 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 1 + 5 20 • 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. Data Structure and Algorithm 35 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 1 + 520 • 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. Data Structure and Algorithm 36 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra * 1 + 520 = 100 • 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. Data Structure and Algorithm 37 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + 100 • 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. Data Structure and Algorithm 38 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1 + 100 • 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. Data Structure and Algorithm 39 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1+100 • 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. Data Structure and Algorithm 40 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 1+100 = 101 • 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. Data Structure and Algorithm 41 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 101 • 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. Data Structure and Algorithm 42 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra 101 • 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. Data Structure and Algorithm 43 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Thuật toán 2 ngăn xếp của Dijkstra result 101