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?