CPSC 110 Lecture 20: CPSC Lecture 20.docx

3. 13 marks) Complete the body of a Scheme function named f to calculate 11x) = 1+1/2 x + 1/3.1.

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.

1. Complete the following problem using concepts of STACK.
2. If you are using JAVA, you must include the main method as well which should test your other methods and print the outputs according to the tasks.
3. If you are using PYTHON, make sure your code has the methods invoked and proper printing statements according to the tasks.
4. 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.