Homework 2: Dijkstra's Two-Stack Algorithm ASSIGNMENT: In 1960, Edsger W. Dijkstra came up with a very...

Transcribed Image Text:

Homework 2: Dijkstra's Two-Stack Algorithm ASSIGNMENT: In 1960, Edsger W. Dijkstra came up with a very simple algorithm to evaluate arithmetic expressions with the help of two stacks. The first stack is called the "value (operand) stack" and it is used to store numbers (operands). The second stack is the "operator stack", used to store arithmetical operations (operators). In order to use the algorithm, all individual expressions must be enclosed in parentheses. The algorithm works in the following way: 1. take an arithmetic expression, with properly balanced parentheses a. example: (( 5+ (3*8)) - (2* 7)) 2. read the expression character by character 3. if number, push it onto the value stack 4. if operator, push it onto the operator stack 5. ignore left parentheses 6. when right parentheses are encountered: a. pop an operator and two values (from their respective stacks) b. perform an operation with those values (e.g. 3 * 8) c. push the result onto the value stack In this homework assignment, your task will be to implement Dijkstra's Two-Stack Algorithm for simple arithmetic operations (addition, subtraction, multiplication, division, modulo), using one of the stack implementations we studied (you can use either the linked-list stack or the resizing-array stack; do not use the built-in Java stack). The figure below describes the two-stack algorithm once again (left), and offers a simple example (right). Goal. Evaluate infix expressions. (1 + ((2+3) * (4.5))) operand operator Context. An interpreter! value stack operator stack Two-stack algorithm. [E. W. Dijkstra] Value: push onto the value stack. Operator: push onto the operator stack. Left parenthesis: ignore. Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. mmmmm FEE 100 101 (1+((2+3)+(4+5))) +((2+3)*(4*5))) ((2+3)+(4+5))) +3)*(4+5))) 3)*(4.5))) >*(4-5))) (4.5))) (4-5))) *5))) 5))) ))) >> The assignment will be open on LMS until March 24th, 23:55. You are going to export your projects as archive files and submit them to LMS. Hint: In order to simplify your implementation of the algorithm, assume that each token (parenthesis, number or operator) is separated by a whitespace. Example: (2+3) invalid, but (2+3) valid Moreover, make sure that each expression is entered within parentheses and that the parentheses are perfectly balanced. example: (3+4)* 5 invalid, but ( ( 3+4)*5) valid It should be possible for the user to manually enter the expression they want into the program, via console input (using the Scanner input). You can use the two expressions given above (in the algorithm explanation and in the figure) to test whether your implementation is working correctly. Good luck. Homework 2: Dijkstra's Two-Stack Algorithm ASSIGNMENT: In 1960, Edsger W. Dijkstra came up with a very simple algorithm to evaluate arithmetic expressions with the help of two stacks. The first stack is called the "value (operand) stack" and it is used to store numbers (operands). The second stack is the "operator stack", used to store arithmetical operations (operators). In order to use the algorithm, all individual expressions must be enclosed in parentheses. The algorithm works in the following way: 1. take an arithmetic expression, with properly balanced parentheses a. example: (( 5+ (3*8)) - (2* 7)) 2. read the expression character by character 3. if number, push it onto the value stack 4. if operator, push it onto the operator stack 5. ignore left parentheses 6. when right parentheses are encountered: a. pop an operator and two values (from their respective stacks) b. perform an operation with those values (e.g. 3 * 8) c. push the result onto the value stack In this homework assignment, your task will be to implement Dijkstra's Two-Stack Algorithm for simple arithmetic operations (addition, subtraction, multiplication, division, modulo), using one of the stack implementations we studied (you can use either the linked-list stack or the resizing-array stack; do not use the built-in Java stack). The figure below describes the two-stack algorithm once again (left), and offers a simple example (right). Goal. Evaluate infix expressions. (1 + ((2+3) * (4.5))) operand operator Context. An interpreter! value stack operator stack Two-stack algorithm. [E. W. Dijkstra] Value: push onto the value stack. Operator: push onto the operator stack. Left parenthesis: ignore. Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. mmmmm FEE 100 101 (1+((2+3)+(4+5))) +((2+3)*(4*5))) ((2+3)+(4+5))) +3)*(4+5))) 3)*(4.5))) >*(4-5))) (4.5))) (4-5))) *5))) 5))) ))) >> Homework 2: Dijkstra's Two-Stack Algorithm ASSIGNMENT: In 1960, Edsger W. Dijkstra came up with a very simple algorithm to evaluate arithmetic expressions with the help of two stacks. The first stack is called the "value (operand) stack" and it is used to store numbers (operands). The second stack is the "operator stack", used to store arithmetical operations (operators). In order to use the algorithm, all individual expressions must be enclosed in parentheses. The algorithm works in the following way: 1. take an arithmetic expression, with properly balanced parentheses a. example: (( 5+ (3*8)) - (2* 7)) 2. read the expression character by character 3. if number, push it onto the value stack 4. if operator, push it onto the operator stack 5. ignore left parentheses 6. when right parentheses are encountered: a. pop an operator and two values (from their respective stacks) b. perform an operation with those values (e.g. 3 * 8) c. push the result onto the value stack In this homework assignment, your task will be to implement Dijkstra's Two-Stack Algorithm for simple arithmetic operations (addition, subtraction, multiplication, division, modulo), using one of the stack implementations we studied (you can use either the linked-list stack or the resizing-array stack; do not use the built-in Java stack). The figure below describes the two-stack algorithm once again (left), and offers a simple example (right). Goal. Evaluate infix expressions. (1 + ((2+3) * (4.5))) operand operator Context. An interpreter! value stack operator stack Two-stack algorithm. [E. W. Dijkstra] Value: push onto the value stack. Operator: push onto the operator stack. Left parenthesis: ignore. Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. mmmmm FEE 100 101 (1+((2+3)+(4+5))) +((2+3)*(4*5))) ((2+3)+(4+5))) +3)*(4+5))) 3)*(4.5))) >*(4-5))) (4.5))) (4-5))) *5))) 5))) ))) >> The assignment will be open on LMS until March 24th, 23:55. You are going to export your projects as archive files and submit them to LMS. Hint: In order to simplify your implementation of the algorithm, assume that each token (parenthesis, number or operator) is separated by a whitespace. Example: (2+3) invalid, but (2+3) valid Moreover, make sure that each expression is entered within parentheses and that the parentheses are perfectly balanced. example: (3+4)* 5 invalid, but ( ( 3+4)*5) valid It should be possible for the user to manually enter the expression they want into the program, via console input (using the Scanner input). You can use the two expressions given above (in the algorithm explanation and in the figure) to test whether your implementation is working correctly. Good luck. The assignment will be open on LMS until March 24th, 23:55. You are going to export your projects as archive files and submit them to LMS. Hint: In order to simplify your implementation of the algorithm, assume that each token (parenthesis, number or operator) is separated by a whitespace. Example: (2+3) invalid, but (2+3) valid Moreover, make sure that each expression is entered within parentheses and that the parentheses are perfectly balanced. example: (3+4)* 5 invalid, but ( ( 3+4)*5) valid It should be possible for the user to manually enter the expression they want into the program, via console input (using the Scanner input). You can use the two expressions given above (in the algorithm explanation and in the figure) to test whether your implementation is working correctly. Good luck.