Recursively Structured Expressions

For these exercises, you should download the following files and put them all in the same folder. Then open startcode.scm in DrRacket.


Boolean expressions are defined by the grammar below:

  <exp> ::= True
          | False
          | <variable>
          | (NOT <exp>)
          | (AND <exp> <exp>)
          | (OR <exp> <exp>)
where <variable> is any symbol not in the set {True, False, AND, OR, NOT}. Examples of valid boolean expressions:

(define b1 'True)
(define b2 'False)
(define b3 'x)
(define b4 '(NOT False))
(define b5 '(AND True y))
(define b6 '(AND a b))
(define b7 '(OR a b))
(define b8 '(OR (OR x y) z))
(define b9 '(AND x (NOT y)))
(define b10 '(OR False (NOT (AND x y))))
(define b11 '(AND True (OR False (NOT True))))
(define b12 '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))
(define b13 '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))
(define b14 '(AND x (AND True True)))
(define b15 '(AND (OR False False) x))

  1. Write the function (count-bools exp), which takes a valid boolean expression and returns the total number of boolean constants True and False that appear in the expression.

    (count-bools 'True)  → 1
    (count-bools '(AND True y))  → 1
    (count-bools '(AND x y))  → 0
    (count-bools '(OR False (NOT (AND x y))))  → 1
    (count-bools '(AND True (OR False (NOT True))))  → 3
    (count-bools '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))  → 2
    (count-bools '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))  → 0
    
  2. Write the function (count-bvars exp), which takes a valid boolean expression and counts the total number of variables that appear in the expression. Hint: this function will be very similar to count-bools.

    (count-bvars 'True)  → 0
    (count-bvars '(AND True y))  → 1
    (count-bvars '(AND x y))  → 2
    (count-bvars '(OR False (NOT (AND x y))))  → 2
    (count-bvars '(AND True (OR False (NOT True))))  → 0
    (count-bvars '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))  → 3
    (count-bvars '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))  → 5
    
  3. Write the function (count-bops exp), which takes a valid boolean expression and counts the total number of boolean operators (AND, OR, NOT symbols) that appear in the expression.

    (count-bops 'True)  → 0
    (count-bops '(AND True y))  → 1
    (count-bops '(AND x y))  → 1
    (count-bops '(OR False (NOT (AND x y))))  → 3
    (count-bops '(AND True (OR False (NOT True))))  → 3
    (count-bops '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))  → 7
    (count-bops '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))  → 6
    
  4. Write the function (get-bools exp), which takes a valid boolean expression and returns a list of all of the boolean constants (True and False) that appear in the expression, in the order that they appear.

    (get-bools 'True)  → (True)
    (get-bools '(AND True y))  → (True)
    (get-bools '(AND x y))  → ()
    (get-bools '(OR False (NOT (AND x y))))  → (False)
    (get-bools '(AND True (OR False (NOT True))))  → (True False True)
    (get-bools '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))  → (True False)
    (get-bools '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))  → ()
    
  5. Write the function (get-bvars exp), which takes a valid boolean expression and returns a list of all of the variables that appear in the expression, in the order that they appear.

    (get-bvars 'True)  → ()
    (get-bvars '(AND True y))  → (y)
    (get-bvars '(AND x y))  → (x y)
    (get-bvars '(OR False (NOT (AND x y))))  → (x y)
    (get-bvars '(AND True (OR False (NOT True))))  → ()
    (get-bvars '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))  → (x y z)
    (get-bvars '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))  → (z y x z w)
    
  6. Write the function (get-bops exp), which takes a valid boolean expression and returns a list containing all of the boolean operators (AND, OR, NOT symbols) that appear in the expression, in the order that they appear.

    (get-bops 'True)  → ()
    (get-bops '(AND True y))  → (AND)
    (get-bops '(AND x y))  → (AND)
    (get-bops '(OR False (NOT (AND x y))))  → (OR NOT AND)
    (get-bops '(AND True (OR False (NOT True))))  → (AND OR NOT)
    (get-bops '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))  → (NOT AND OR NOT AND OR NOT)
    (get-bops '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))  → (AND AND OR AND NOT NOT)
    
  7. Write the function (bools-only? exp), which takes a valid boolean expression and returns true if the expression contains only True or False constants but no variables.

    (bools-only? 'False)  → #t
    (bools-only? '(NOT False))  → #t
    (bools-only? 'x)  → #f
    (bools-only? '(AND True y))  → #f
    (bools-only? '(AND True (OR False (NOT True))))  → #t
    (bools-only? '(AND (OR False False) x))  → #f
    (bools-only? '(OR False (NOT (AND x y))))  → #f
    (bools-only? '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))  → #f
    (bools-only? '(AND (OR (NOT True) False) (AND True False)))  → #t
    
  8. Write the function (bvars-only? exp), which takes a valid boolean expression and returns true if the expression contains only variables or operator symbols, with no True or False constants anywhere.

    (bvars-only? 'False)  → #f
    (bvars-only? '(NOT False))  → #f
    (bvars-only? 'x)  → #t
    (bvars-only? '(AND True y))  → #f
    (bvars-only? '(NOT y))  → #t
    (bvars-only? '(OR (OR x y) z))  → #t
    (bvars-only? '(OR (OR x y) True))  → #f
    (bvars-only? '(OR False (NOT (AND x y))))  → #f
    (bvars-only? '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))  → #t
    
  9. Write the function (show-bform exp), which takes a valid boolean expression and constructs an identical expression except with each constant True or False replaced by the symbol bool and each variable replaced by the symbol var.

    (show-bform 'True)  → bool
    (show-bform 'x)  → var
    (show-bform '(NOT y))  → (NOT var)
    (show-bform '(AND True y))  → (AND bool var)
    (show-bform '(OR False (NOT (AND x y))))  → (OR bool (NOT (AND var var)))
    (show-bform '(AND True (OR False (NOT True))))  → (AND bool (OR bool (NOT bool)))
    (show-bform '(AND x (AND True True)))  → (AND var (AND bool bool))
    

Infix expressions are defined by the grammar below:

  <exp> ::= <number>
          | <variable>
          | (<exp> <operator> <exp>)
where <operator> is any symbol in the set {+, -, *, /}. Examples of valid infix expressions:

(define in1 '42)
(define in2 'apple)
(define in3 '(2 + 3))
(define in4 '(x * 5))
(define in5 '(x * (2 - y)))
(define in6 '((a * a) + (b * b)))
(define in7 '(((9 / 5) * celsius) + 32))
(define in8 '((5 * (fahrenheit - 32)) / 9))
(define in9 '((3 * 4) / ((2 * 3) - 5)))
(define in10 '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))
(define in11 '(3 * 4))
(define in12 '(15 / 5))
(define in13 '(10 + (3 * 4)))
(define in14 '((3 * 4) + (15 / 5)))
(define in15 '(1 * (2 * (3 * (4 * ((((1 + 1) + 1) + 1) + 1))))))

  1. Write the function (count-inums exp), which takes a valid infix expression and returns the total number of numbers that appear in the expression.

    (count-inums '42)  → 1
    (count-inums 'apple)  → 0
    (count-inums '(2 + 3))  → 2
    (count-inums '(x * (2 - y)))  → 1
    (count-inums '((a * a) + (b * b)))  → 0
    (count-inums '(((9 / 5) * celsius) + 32))  → 3
    (count-inums '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))  → 2
    
  2. Write the function (count-ivars exp), which takes a valid infix expression and returns the total number of variables that appear in the expression.

    (count-ivars '42)  → 0
    (count-ivars 'apple)  → 1
    (count-ivars '(2 + 3))  → 0
    (count-ivars '(x * (2 - y)))  → 2
    (count-ivars '((a * a) + (b * b)))  → 4
    (count-ivars '(((9 / 5) * celsius) + 32))  → 1
    (count-ivars '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))  → 6
    
  3. Write the function (count-iops exp), which takes a valid infix expression and returns the total number of operator symbols that appear in the expression.

    (count-iops '42)  → 0
    (count-iops 'apple)  → 0
    (count-iops '(2 + 3))  → 1
    (count-iops '(x * (2 - y)))  → 2
    (count-iops '((a * a) + (b * b)))  → 3
    (count-iops '(((9 / 5) * celsius) + 32))  → 3
    (count-iops '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))  → 7
    
  4. Write the function (get-inums exp), which takes a valid infix expression and returns a list of all of the numbers that appear in the expression, in the order that they appear.

    (get-inums '42)  → (42)
    (get-inums 'apple)  → ()
    (get-inums '(x + 4))  → (4)
    (get-inums '((a * a) + (b * b)))  → ()
    (get-inums '(((9 / 5) * celsius) + 32))  → (9 5 32)
    (get-inums '((5 * (fahrenheit - 32)) / 9))  → (5 32 9)
    (get-inums '((3 * 4) / ((2 * 3) - 5)))  → (3 4 2 3 5)
    (get-inums '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))  → (2 2)
    
  5. Write the function (get-ivars exp), which takes a valid infix expression and returns a list of all of the variables that appear in the expression, in the order that they appear.

    (get-ivars '42)  → ()
    (get-ivars 'apple)  → (apple)
    (get-ivars '(x + 4))  → (x)
    (get-ivars '((a * a) + (b * b)))  → (a a b b)
    (get-ivars '(((9 / 5) * celsius) + 32))  → (celsius)
    (get-ivars '((5 * (fahrenheit - 32)) / 9))  → (fahrenheit)
    (get-ivars '((3 * 4) / ((2 * 3) - 5)))  → ()
    (get-ivars '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))  → (x y a a b c)
    
  6. Write the function (get-iops exp), which takes a valid infix expression and returns a list of all of the operator symbols that appear in the expression, in the order that they appear.

    (get-iops '42)  → ()
    (get-iops 'apple)  → ()
    (get-iops '(x + 4))  → (+)
    (get-iops '((a * a) + (b * b)))  → (* + *)
    (get-iops '(((9 / 5) * celsius) + 32))  → (/ * +)
    (get-iops '((5 * (fahrenheit - 32)) / 9))  → (* - /)
    (get-iops '((3 * 4) / ((2 * 3) - 5)))  → (* / * -)
    (get-iops '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))  → (+ / * * - * -)
    
  7. Write the function (inums-only? exp), which takes a valid infix expression and returns true if the expression contains only numbers or operator symbols, with no variables anywhere.

    (inums-only? '42)  → #t
    (inums-only? 'apple)  → #f
    (inums-only? '(2 + 3))  → #t
    (inums-only? '(x + 4))  → #f
    (inums-only? '(x * (2 - y)))  → #f
    (inums-only? '((a * a) + (b * b)))  → #f
    (inums-only? '((3 * 4) / ((2 * 3) - 5)))  → #t
    
  8. Write the function (ivars-only? exp), which takes a valid infix expression and returns true if the expression contains only variables or operator symbols, with no numbers anywhere.

    (ivars-only? '42)  → #f
    (ivars-only? 'apple)  → #t
    (ivars-only? '(x + 4))  → #f
    (ivars-only? '(x + y))  → #t
    (ivars-only? '(x * (2 - y)))  → #f
    (ivars-only? '((a * a) + (b * b)))  → #t
    (ivars-only? '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))  → #f
    
  9. Write the function (show-iform exp), which takes a valid infix expression and constructs an identical expression except with each number replaced by the symbol num and each variable replaced by the symbol var.

    (show-iform '42)  → num
    (show-iform 'apple)  → var
    (show-iform '(x + 4))  → (var + num)
    (show-iform '(x * (2 - y)))  → (var * (num - var))
    (show-iform '((a * a) + (b * b)))  → ((var * var) + (var * var))
    (show-iform '(((9 / 5) * celsius) + 32))  → (((num / num) * var) + num)
    (show-iform '((3 * 4) / ((2 * 3) - 5)))  → ((num * num) / ((num * num) - num))
    

Prefix expressions are defined by the grammar below. In a prefix expression, the operator symbol comes first, followed by the arguments.

  <exp> ::= <number>
          | <variable>
          | (<operator> <exp> <exp>)
Examples of valid prefix expressions:

(define pre1 '42)
(define pre2 'apple)
(define pre3 '(+ 2 3))
(define pre4 '(* x 5))
(define pre5 '(* x (- 2 y)))
(define pre6 '(+ (* a a) (* b b)))
(define pre7 '(+ (* (/ 9 5) celsius) 32))
(define pre8 '(/ (* 5 (- fahrenheit 32)) 9))
(define pre9 '(/ (* 3 4) (- (* 2 3) 5)))
(define pre10 '(* (+ 2 (/ x y)) (- (* a a) (* 2 (- b c)))))
(define pre11 '(* 3 4))
(define pre12 '(/ 15 5))
(define pre13 '(+ 10 (* 3 4)))
(define pre14 '(+ (* 3 4) (/ 15 5)))
(define pre15 '(* 1 (* 2 (* 3 (* 4 (+ (+ (+ (+ 1 1) 1) 1) 1))))))

  1. Write the function (infix-to-prefix exp), which takes a valid infix expression and converts it into an equivalent prefix expression.

    (infix-to-prefix '(2 + 3))  → (+ 2 3)
    (infix-to-prefix in5)  → (* x (- 2 y))
    (infix-to-prefix in6)  → (+ (* a a) (* b b))
    (infix-to-prefix in7)  → (+ (* (/ 9 5) celsius) 32)
    (infix-to-prefix in9)  → (/ (* 3 4) (- (* 2 3) 5))
    
  2. Write the function (prefix-to-infix exp), which takes a valid prefix expression and converts it into an equivalent infix expression.

    (prefix-to-infix '(+ 2 3))  → (2 + 3)
    (prefix-to-infix pre5)  → (x * (2 - y))
    (prefix-to-infix pre6)  → ((a * a) + (b * b))
    (prefix-to-infix pre7)  → (((9 / 5) * celsius) + 32)
    (prefix-to-infix pre9)  → ((3 * 4) / ((2 * 3) - 5))
    

Postfix expressions are defined by the grammar below. In a postfix expression, the arguments come first, followed by the operator symbol at the end.

  <exp> ::= <number>
          | <variable>
          | (<exp> <exp> <operator>)
Examples of valid postfix expressions:

(define post1 '42)
(define post2 'apple)
(define post3 '(2 3 +))
(define post4 '(x 5 *))
(define post5 '(x (2 y -) *))
(define post6 '((a a *) (b b *) +))
(define post7 '(((9 5 /) celsius *) 32 +))
(define post8 '((5 (fahrenheit 32 -) *) 9 /))
(define post9 '((3 4 *) ((2 3 *) 5 -) /))
(define post10 '((2 (x y /) +) ((a a *) (2 (b c -) *) -) *))
(define post11 '(3 4 *))
(define post12 '(15 5 /))
(define post13 '(10 (3 4 *) +))
(define post14 '((3 4 *) (15 5 /) +))
(define post15 '(1 (2 (3 (4 ((((1 1 +) 1 +) 1 +) 1 +) *) *) *) *))

  1. Write the function (infix-to-postfix exp), which takes a valid infix expression and converts it into an equivalent postfix expression.

    (infix-to-postfix '(2 + 3))  → (2 3 +)
    (infix-to-postfix in5)  → (x (2 y -) *)
    (infix-to-postfix in6)  → ((a a *) (b b *) +)
    (infix-to-postfix in7)  → (((9 5 /) celsius *) 32 +)
    (infix-to-postfix in9)  → ((3 4 *) ((2 3 *) 5 -) /)
    
  2. Write the function (postfix-to-infix exp), which converts a valid postfix expression into an equivalent infix expression.

    (postfix-to-infix '(2 3 +))  → (2 + 3)
    (postfix-to-infix post5)  → (x * (2 - y))
    (postfix-to-infix post6)  → ((a * a) + (b * b))
    (postfix-to-infix post7)  → (((9 / 5) * celsius) + 32)
    (postfix-to-infix post9)  → ((3 * 4) / ((2 * 3) - 5))
    
  3. Write the functions (prefix-to-postfix exp) and (postfix-to-prefix exp), which convert between prefix and postfix expressions. Hint: these are one-liners if you use the appropriate infix conversion functions as helpers.

    (prefix-to-postfix '(+ 2 3))   → (2 3 +)
    (postfix-to-prefix) '(2 3 +))  → (+ 2 3)
    
    (prefix-to-postfix pre5)   → (x (2 y -) *)
    (postfix-to-prefix post5)  → (* x (- 2 y))
    
    (prefix-to-postfix pre7)   → (((9 5 /) celsius *) 32 +)
    (postfix-to-prefix post7)  → (+ (* (/ 9 5) celsius) 32)
    
    (prefix-to-postfix pre9)   → ((3 4 *) ((2 3 *) 5 -) /)
    (postfix-to-prefix post9)  → (/ (* 3 4) (- (* 2 3) 5))