## Week 9: Optional Exercises

### 1. Prefix to Postfix

Write a procedure that reads an expression in prefix notation and
writes the equivalent expression in postfix notation. Do not use an
intermediate expression tree.

### 2. Postfix to Infix

Write a procedure that reads an expression in postfix notation and
writes the equivalent expression in infix notation. Do not use an
intermediate expression tree.

### 3. Infix Parser

Write a function that reads an expression in infix notation and
returns an expression tree.

### 4. Tree Variables

Extend our expression tree type so that expressions can include
*variables*, which consist of a single lowercase letter. Enhance
the parser so that variables are parsed.

### 5. Variable Evaluation

Extending the previous exercise, extend evalExpression so that it
can evaluate expressions containing a single variable, given the
variable’s name and value:

function evalExpression(e: pexp; varName: string; varValue: integer): integer;

###
6. String Parser

Alter the infix expression tree parser (from exercise 3 above) to
read from a string rather than from standard input. As it reads, it
should advance a variable containing the current position in the
string:

function parseInfix(s: string; var index: integer): pexp;

###
7. Full Integers

Extend the parser from the previous exercise to handle multi-digit
integers.

### 8. Search Tree and Heap

Is it ever possible that a binary tree of height >= 2 is both a
valid binary search tree and also a valid binary heap? Why or why
not?