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

29 views4 pages
Published on 14 Jun 2017
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
Please
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
Prefix notation: add(a, b)
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.

Already have an account? Log in

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.

Get OneClass Grade+

Unlimited access to all notes and study guides.

YearlyMost Popular
75% OFF
$9.98/m
Monthly
$39.98/m
Single doc
$39.98

or

You will be charged $119.76 upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.