Program

This program will give you practice with writing and using a Stack ADT. You will develop a program that computes mathematical expressions by converting the expression from infix notation to postfix notation, respecting the order of operations (PEMDAS), and then solving it. You will use two Stacks to do this. One Stack will be used to convert the infix expression to a postfix expression, and one Stack will be used to solve the postfix expression. You must write your own Stack class(es). Examples of this were shown in lecture. See the Example Output for an example of how this program should perform.

Warning!

Do not make any changes to the provided Main.java file. Also, do not change the name of the class or method signatures of the provided class PostfixCalculator. You can add more methods and functionality to this class, but you cannot change the name of anything that is already provided (or Main won’t compile).

Stack(s)

You will need to write at least 1 Stack class, if not 2. It is fine if you write 2 separate Stack classes. You could also write a single Stack class that uses Generics and supports multiple types. You may create your Stack class(es) as array-based or linked-based, the choice is yours. Once you have your Stack class(es), you will use them in the methods below. One method will require a Stack of Strings and the other method will require a Stack of doubles. Examples of writing a Stack class were shown in lecture (both array-based and linked-based).

You cannot use any provided classes from the Java Collections Framework, including Stack, Queue, List, Vector, Deque, etc. The reason for this is so you get practice writing your own Stack class. In fact, you cannot import and use any classes provided in java.util, except for StringTokenizer. You should use a StringTokenizer for both methods below to make it easier to parse out negative numbers.

infix2postfix()

This method will use a Stack of Strings to convert an infix expression into a postfix expression. Please search the internet for many examples (like this lecture) which explain what postfix expressions are and how to convert an infix expression to a postfix expression. Your book also talks about postfix expressions. We have provided an algorithm that you can follow in the comments of the starter code of your assignment repo. Basically, you separate all the tokens between the spaces of an infix expression (usually with a StringTokenizer) and then you visit each token and decide if it should be appended directly to a postfix expression or put into a stack to retrieved later depending on the type of token it is - operator, operand, open parenthesis, or close parenthesis. The algorithm needs to respect the order of operations (PEMDAS), so when you come across an operator, you need to check its precedence against the existing operators in the Stack before pushing the new one.

solve()

This method will use a Stack of doubles to solve a postfix expression. We have provided an algorithm that you can follow in the comments of the starter code of your assignment repo. Basically, you separate all the tokens between the spaces of a postfix expression (usually with a StringTokenizer) and then you visit each token, if it is an operator then you pop off the top two numbers from the Stack and compute them appropriately depending on the operator, whereas if the token is a number you push it onto your Stack. Your book also talks about a postfix expression evaluator in detail (Java Foundations, Chapter 12.4 of the 5th edition).

Testing

If you compile and run your program with the provided starter code without any changes, it will print out 0.0 as the answer. Once you get the program working, the answer to the default postfix expression input ("2 2 5 4 * * +") will be printed out: 42.0. However, you can also test your program by passing in an infix expression as an argument. You can do this in the command shell as shown in the Example Output. You can also do this from your IDE in your Debug/Run configuration options. You can also quickly covert infix expressions to postfix expressions using an online calculator. And finally, you can type infix expressions into Google and it will solve them for you.

This assignment has been answered 3 times in private sessions.