pertemuan struktur data * pohon ekspresi *
DESCRIPTION
Pertemuan Struktur Data * Pohon Ekspresi *. STMIK JAKARTA STI&K. Disusun oleh : Aqwam Rosadi K. Kompetensi. Mahasiswa mampu membuat dan mengimplementasikan pohon ekspresi Mahasiswa mampu mengimplementasi pembuatan ekspresi dari pohon ekspresi. Expression Tree - 1. - PowerPoint PPT PresentationTRANSCRIPT
Pertemuan Pertemuan Struktur DataStruktur Data **Pohon Ekspresi *Pohon Ekspresi *
Pertemuan Pertemuan Struktur DataStruktur Data **Pohon Ekspresi *Pohon Ekspresi *
STMIK JAKARTA STI&KSTMIK JAKARTA STI&K
Disusun oleh :Disusun oleh :Aqwam Rosadi Aqwam Rosadi
KK
2
Kompetensi
• Mahasiswa mampu membuat dan mengimplementasikan pohon ekspresi
• Mahasiswa mampu mengimplementasi pembuatan ekspresi dari pohon ekspresi
Expression Tree - 1 • Sebuah expression tree adalah sebuah binary tree dengan
sifat :
– Setiap leaf adalah sebuah operandoperand.
– Root dan internal nodes adalah operatorsoperators.
– Subtrees adalah subexpressions, dengan root adalah sebuah operator.
Expression Tree - 2
• Dalam expression tree, 3 cara traversals
akan membentuk 3 format ekspresi yang
berbeda yaitu : infixinfix, postfixpostfix, and prefixprefix.
– Inorder traversal menghasilkan infix infix
expressionexpression
– Postorder traversal menghasilkan postfix postfix
expressionexpression
– Preorder traversal menghasilkan prefix prefix
expressionexpression
Contoh Expression Tree
• A+BC-DE ((A+(BC))-(DE))
+
A
D E
-
B C
Contoh Expression Tree
• A*B+C (A*(B+C))
• A -B+CDE ((A (-B))+((CD)E))
*
A +
B C
A
E
+
-
B C D
Infix Traversal
• Saat mencetak infix expression tree, kita harus
menambahkan kurung buka kurung buka pada awal setiap
ekspresi dan kurung tutupkurung tutup pada akhir ekspresi.
– Dikarenakan root dari tree dan setiap
subtree dari tree menyatakan
subexpressionsubexpression, maka kita mencetak kurung
buka saat memulai sebuah tree atau subtree
dan kurung tutup saat semua anak dari
tree/subtree sudah diproses.
Algorithm infixinfix (val tree <tree pointer>) if (tree not empty) if (tree→token is an operand) print (tree → token) else print (open parenthesis) infixinfix (tree →left) print (tree →token) infixinfix (tree →right) print (close parenthesis) end if end if return end infix
Infix TraversalInfix Traversal
Postfix Traversal
• Menggunakan postorder traversal seperti pada tree.
• Tidak membutuhkan kurung
Algorithm postfixpostfix (val tree <tree pointer>)
if (tree not empty)
postfixpostfix (tree →left)
postfixpostfix (tree →right)
print (tree →token)
end if
return
end postfix
Prefix Traversal
• Menggunakan preorder traversal seperti pada tree.
• Tidak membutuhkan kurung
Algorithm prefixprefix (val tree <tree pointer>)
if (tree not empty)
print (tree →token)
prefixprefix (tree →left)
prefix prefix (tree →right)
end if
return
end prefix
Infix or postfix or prefix ?
• Bentuk infix 3+5*4. Berapa hasilnya ?
• Bentuk prefix *+3 5 4. Berapa hasilnya ?
• Bentuk 35+4*. Berapa hasilnya ?
Konversi bentuk infix, prefix, postfix
• Ada 6 konversi yang dapat dikerjakan :– infix -> prefix, – infix -> postfix, – prefix -> infix, – prefix -> postfix, – postfix -> prefix, – postfix -> infix.
• Untuk 2 yang pertama menggunakan stack, sedangkan 4 yang terakhir menggunakan Expression Trees.
Membuat Pohon Ekspresi dari Ekspresi
Postfix• Menggunakan stack untuk
menyimpan operand• Tree yang dibuat :
– Node yang berisi nama variabel menjadi daun
– Node yang berisi operator memiliki paling sedikit 2 anak yang dapat berupa operator lain atau node daun
Membuat Pohon Ekspresi dari
Ekspresi Postfix
• A B C D * - + E /
B
B
Stack
A
A
StackA
B
C
StackA
D
Stack
C
B
A
C
D*
Stack
B
A
C D
*
Membuat Pohon Ekspresi dari
Ekspresi Postfix
• A B C D * - + E /
Stack
E
-
B
C D
-
*
Stack
+
A
B
C D
-
*
+
Stack
E
A
B
C D
-
*
+
Stack
/
/
E
A
B
C D
-
*
+
Membuat Pohon Ekspresi dari Ekspresi
PostfixIlustrasi Lain
5 3 - 4 * 9 +
Token
5 push(new ExpressionTree(5,null,null));
Langkah
Stack (top at right)
5
Token
3 push(new ExpressionTree(3,null,null));
Langkah
Stack (top at right)
5 3
Token
- op2 = pop
op1 = pop
push(new ExpressionTree(-,op1,op2));
Langkah
Stack (top at right)
5
-
3
Token
4 push(new ExpressionTree(4,null,null));
Langkah
Stack (top at right)
5
-
3
4
Token
* op2 = pop
op1 = pop
push(new ExpressionTree(*,op1,op2));
Langkah
Stack (top at right)
5
-
3
4
*
Token
9 push(new ExpressionTree(9,null,null));
Langkah
Stack (top at right)
5
-
3
4
* 9
Token
+ op2 = pop
op1 = pop
push(new ExpressionTree(+,op1,op2));
Langkah
Stack (top at right)
5
-
3
4
* 9
+End of the expression has been reached, and the full expression tree is the only tree left on the stack
Praktikum
• Membuat pohon ekspresi dari ekspresi postfix
• Operasi traversal pada pohon ekspresi
• Berupa algoritma & rancangan program
“Watch your habits, for they become your character. Develop your character, for it becomes
your destiny”(Perhatikan kebiasaanmu, karena
itu akan menjadi karaktermu. Bentuklah karaktermu, karena itu
akan menentukan masa depanmu)