# CS 2110 Lecture Notes - Lecture 13: Reverse Polish Notation, Tree Traversal, Infix Notation

29 views4 pages
Published on 14 Jun 2017
School
Course
Professor
Lecture 13 - More Trees!
oFrom last time we saw how to construct a syntax tree for some basic mathematical
expressions
2 * 3 - (1 + 2 * 4)
Tree!
oLeft off on Tree Traversals
Preorder Traversal
Rule
Visit root
Visit left subtree, in preorder
Visit right subtree, in preorder
Ex
*
+
2
3
+
1
4
So we go * + 2 3 + 1 4
That’s preorder
We did the root, *, then processed the left subtree in
preorder.
It makes sense!
Trust me
Postorder Traversal
Process elements left to right, bottom to top
Rule
Visit left subtree, in postorder
Visit right subtree, in postorder
Visit the root
Inorder Traversal
Rule
Visit left subtree, in Inorder
Process root
Visit right subtree, in Inorder
Problem: Requires parentheses
Let’s look at notations
Postfix notation: n!
Infix notation: (5+3)*4
oLet’s look at some dope applications of all this nonsense
PUT IN DOPE APPLICATIONS HERE
Interface Expr
Static class Int implements Expr
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

## Document Summary

Lecture 13 - more trees: from last time we saw how to construct a syntax tree for some basic mathematical expressions. Tree: left off on tree traversals. So we go * + 2 3 + 1 4. We did the root, *, then processed the left subtree in preorder. Process elements left to right, bottom to top. Infix notation: (5+3)*4: let"s look at some dope applications of all this nonsense. Basically rules for how your trees can be constructed. Legal grammar: the small cat that sat in the hat ate the big rat on the mat slowly, then got sick. Illegal grammar: cat sat the small hat in the ate big rat the on slowly mat the got, then sick. Wtf does this even mean you tell me. Grammar: a set of rules for generating sentences of a language. Words goats, astrophysics, bunnies, like, see are called tokens or terminals. Example: sentence and sentence is a valid sentence.