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

29 views4 pages

Published on 14 Jun 2017

School

Department

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

## 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.