Postfix Java assignment (part 2, infixToPostfix class) | Data Structures and Algorithm Analysis Lab

More Data Structures and Algorithm Analysis videos:
https://youtube.com/playlist?list=PLZPy7sbFuWViIs2tnMRzkr6-1Pr2I3o3o
(Infix to Postfix videos in playlist)


Notes for Data Structures and Algorithm Analysis:
https://docs.google.com/document/d/1YU8wUtH0_bOHlAM1MqOAbxnZhQQBJ0yHYA-lNPafgkM/edit?usp=sharing



Lab Instructions:
Grab an expression from the user and evaluate it. The expression can contain +-/*( )

The expression will not contain any spaces. All the numbers will be single digit (between 0 and 9). No error checking is necessary.

Example:

Give me an expression: 2*(6-3)

What will be displayed on the screen

Postfix expression: 263-*

Answer: 6

Do not use any of the built-in stack functions. Convert to postfix and evaluate.

Here is a Q&A link to some of your possible questions. Please email me any further questions and I will update the google document with some helpful hints.
-----
https://docs.google.com/document/d/1xuTg9j5V76kd0KOpFQj6_-8FVUFefjXvT30Dznc_eLk/edit?usp=sharing
-----
Postfix Assignment

Can I use any of the predefined classes in the library for stacks and queues?
A: No, you have to write your own code for stacks and queues and nodes
Do I take the input from a file or from the keyboard
A: You would take the input from the keyboard
What will the input look like
A: You will take an infix expression. All the numbers will have a single digit. The only operators that you will be using are +,-, /, *
How many stacks and queues should I use?
A: For the conversion from infix to postfix you need one stack and one queue. The stack will be used to store the operators. The queue will be used to store what would usually be displayed on the screen which is the postfix expression. Both the stack and the queue will be storing chars.

For the evaluation, another stack will be used. This stack will be storing integers. As the evaluation is being done, it is possible for the numbers to go beyond a single digit and so char datatype would no longer make any sense
What should be the output of this program
A: this program should output the postfix expression on one line and the result of the evaluation on another line.
How many classes should I have?
A: You will have 5 classes. Node, Stack, Queue, Postfix and Driver. For your Node, Stack and Queue classes, you will not have any static methods or variables. For your Postfix and Driver classes you will not have any instance methods or variables.

Why is everything in the Postfix class static?
A: Since there will be only one expression and it doesn’t need to interact with any other expression, we don’t need to create any objects of type Postfix.

There will be a static method that takes an infix argument and converts it to postfix.
A static method that checks the precedence of the operators
A static method that evaluates the postfix expression

How does the precedence method in the Postfix class work?
A: It takes a character as an argument which will be an operator. The operators will be assigned a number based on their precedence. Here is a possible sample
= 1
( 2
+,- 3
*,/ 4
The method can return the precedence of the operator that is being passed into it.


What conditions do I need to consider for converting infix to postfix
A: There are 4 conditions: open parentheses, close parentheses, numbers and operators


What does the main method in the Driver class look like
A:
Grab an infix expression from the user,
call the convert method in the Postfix class and grab its return value which is a postfix expression.
Display postfix expression
Call the evaluate method in the Postfix class with the converted postfix expression as its argument.and return the result
Display the result

How do I turn in my assignment
A: Everything should be in a single file. There should be only one public class (Driver)

Can I create more classes than what has been stated?
A: By all means. You can create more classes
Can I use the generics feature which works like templates in Java to avoid having to create 2 node classes since the only difference is one has a value of type int and the other is of type char
A: Yes, you can.

1. Does the pop function have to return the whole node that is popped from the stack or just the value that the node holds?

A: It is up to you. Either way is fine.

2. Since the evaluation process only deals with one operator at a time, pushing the evaluated value from the expression of the two operands and operator, is the precedence of the operator still relevant? And if it is still relevant, how do we take the precedence into consideration when evaluating the two operands at hand? There is no operator in the stack to compare the current operator to.

A: When you get to evaluation, at this point your expression is in postfix format which means that you no longer have to worry about the precedence. That is the advantage of converting your expression to postfix format....