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))
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
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
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
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))) → ()
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)
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)
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
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
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))))))
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
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
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
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)
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)
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))))) → (+ / * * - * -)
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
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
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))))))
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))
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 +) *) *) *) *))
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 -) /)
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))
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))