In this project you will implement the Stack ADT to work with the BRIDGES classes and implement an application to evaluate infix expressions. This project consists of 3 parts.

1. You will write a MyStack class that implementsthe StackInterface usinga linked list. Your MyStack class is required to use a private inner class implementation for the node of the linked list called Node. In addition to implementing the methods defined in StackInterface, your MyStack class must override the toString method defined in the Object class. toString should return the String representation of the current state of MyStack. For example, if we created a new MyStack object and pushed

256, 1, 9, 20, and 2018

onto the stack, the toString method should return:

TOP: 2018 | 20 | 9 | 1 | 256 |

Create another class called InfixExpressionEvaluator. This class consists of:

public static doubleevaluateInfix(String infix, int[] values)

which takes in an infix expression and an array of numeric values. Implement this infix expression evaluatorusing the MyStack class that you wrote for part 1. The pseudocode for this is on Blackboard.Implementation details for the InfixExpressionEvaluator class:

• Input. Several differentinfix expressions will be used to test your program.The input expressions are in symbolic form (using the letters a through f, for instance, a+b*c-9, without the double quotes)
• Input.The characters, a through f will represent symbols with values provided for each symbol. The values array provides values for any variable names in the infix expression. Index 0 provides the value for a, 1 for b, etc.
• If the parentheses of a given expression are unbalanced, the program is expected to throw an IllegalStateException
• Output. The result of the expression.
• You will adapt theimplementation from part 1 to use the BRIDGES SLelement class, instead of the MyNode class. This class is named MyBridgesStack.Along with all methods defined in StackInterface, MyBridgesStack must implement a public void method named visualize. The visualize method produces a BRIDGES URL and should be used to generate BRIDGES visualizations.
• Output. Write a main method that will exercise the stack operations and produce standard output to the console. These stack operations can be arbitrary, as long as multiple calls push and pop are made. Use the BRIDGES visualizer to display the contents of the full stack, before any elements are popped off.