Get a math expression from the user in Infix notation (read in as a string), convert the expression into Postfix notation using a stack & queue, and then calculate the expression using a stack.

Translating an infix expression (preferred by humans) into its postfix equivalent (preferred by machines) is reasonably straightforward. This algorithm uses a stack to store lower precedence operators until it is time to add them to the postfix version; each expression is represented as a queue of tokens. Input: infix, the infix expression, a queue of tokens Output: postfix, the postfix expression, a queue of tokens Require: opstack, a stack of operator tokens -------------------------------------------------------------------- while infix isn't empty do token <- next element from infix if token is a left parenthesis then push token on opstack else if token is a right parenthesis then while top element of opstack is not equal left parenthesis do append top element of opstack to postfix remove left parenthesis from opstack else if token is an operator then while opstack isn't empty and priority(token) <= priority(opstack's top) do append top element of opstack to postfix push token on opstack else //token is an operand append token to postfix while opstack isn't empty do append top element of opstack to postfix

Stacks can be used for evaluating postfix expressions. The postfix expression 5 4 9 3 - * 2 / + can be evaluated as follows: push 5 on the stack

push 4 on the stack

push 9 on the stack

push 3 on the stack

pop top two values; subtract; push result on the stack

pop top two values; multiply; push result on the stack

push 2 on the stack pop top two values; divide; push result on the stack

pop top two values; add; push result on the stack The result (17 in this case) is what remains on top of the stack.

This is the driver. This file should have a main function and several other functions to organize or help the main function as described below: main o The main function will begin by printing out Infix to Postfix Converter. Then, using a loop the program allows the user to convert & calculate as many arithmetic expressions as they want. o The program first asks the user for the infix expression and reads it in as a string. The program should remove any spaces in the string. Note: you may assume that the user will only be entering in SINGLE DIGIT NUMBERS in their calculations. o Then, the program should print out the expression to the screen, printing one space between each character for easier reading. o Then, the function should implement the given algorithm that uses a stack to store lower precedence operators until it is time to add them to the postfix version and each expression is represented as a queue of tokens. The tokens are characters from the infix notation string. Make sure to call the isLowerPriority function in this algorithm to determine if the first character (operator) is lower priority then the second one. o Then, call the Queue display function to print out the postfix notation of the expression. o Then, pop all the characters from the postfix Queue and place them in a string. o Call the calculateExpression function, sending this postfix notation string to this function. Then, print the result of the expression, which was returned from this calculateExpression function. o Ask the user if they want to run the program again. If not, then print Goodbye! and end the program. calculateExpression this function accepts a string as a parameter and will return a double, which holds the result of the calculation. This function will create a Stack object. Then, it will parse through the string, one character at a time. o If the character is a digit, then convert the character to a double and then push it on the stack. o Otherwise, the character is an operator, so pop two nodes from the stack, saving their values in two different temporary variables. Then, if the character is a +, then get the addition of these two values. If the character is a - then get the subtraction of the first one from the second one. Do this for addition, subtraction, multiplication, and division. No other operator is supported in this program. Last, push this result on the stack. Once you parse through the entire string, you can return the final result from this function. isLowerPriority this function accepts two characters as parameters and returns true if the first character is an operator that is lower priority than the second character. The possible operators are (, ), +, -, *, /. Priority zero is lowest priority and priority 3 is highest priority in the list below. ( is priority 0

) is priority 3

* & / is priority 2

+ & - is priority 1