STATS 7 Final: Lecture 10

Part (d) [1 MARK] Some number of iterations of selection sort have been performed on a list, resulting in this list: [1, 2, 4, 5, 3, 8, 7, 6, 9] What is the maximum number of passes that could have been performed so far?

Your program will take an arithmetic expression as a String input. For Example:

• “1+2*(3/4)”

• “1+2*[3*3+{4–5(6(7/8/9)+10)–11+(12*8)]+14”

• “1+2*[3*3+{4–5(6(7/8/9)+10)}–11+(12*8)/{13+13}]+14”

Program

Your program will determine whether the open brackets (the square brackets, curly braces and the parentheses) are closed in the correct order.

Outputs:

Output 1

1+2*(3/4)

This expression is correct.

Output 2

1+2*[3*3+{4–5(6(7/8/9)+10)–11+(12*8)]+14

This expression is NOT correct.

Error at character # 10. ‘{‘- not closed.

Output 3

1+2*[3*3+{4–5(6(7/8/9)+10)}–11+(12*8)/{13+13}]+14

This expression is correct.

Output 4

1+2]*[3*3+{4–5(6(7/8/9)+10)–11+(12*8)]+14

This expression is NOT correct.

Error at character # 4. ‘]‘- not opened.

Task 1

Solve the above problem using an array-based stack.

Task 2

Solve the above problem using a linked list-based stack.

I. [10 marks For each row in the table below, determine what would happen if you opened DrScheme and tried to evaluate the given code. If there is an error, brielly explain what is wrong (be more specific than saying "invalid Scheme expression"). If there is no error, give the value produced by DrScheme. The first two rows have been completed for you as examples. Answer Scheme Code (+ 12) (+ 1 2)) (7 + 12) Error. There is an extra) (+ 4 (* 1 (+ 4 2))) ( 1 ((reraircer 27 9) (sqr 5))) (/ 10 (-3 (-14))) (= 'apple 'banana) (and (< 3 4) 19 10)) (- 12 (string-length. "iya")) (reso rest (rest (rest (cors'a (cons 3 (cons 5 empty))))))) (cond [(> 3 8) "happy! [(-34) 'sad) [(even? 9) 'oops] ) (posn-X (first (rest (coris (make-posn 3 4) (cons (make-posr. 56) empty)))))