use C$++$ to solve: Implement a generic stack container. Implement a program that converts

infix expression to postfix expression and implement a program that evaluates postfix

expression using the stack container you developed.

Project Description:

A stack is a type of data container$/$data structure that implements the LAST$-$IN$-$FIRST$-$OUT

$($LIFO$)$ strategy for inserting and recovering data. This is a very useful strategy, related to many

types of natural programming tasks.

Remember that in the generic programming paradigm, every data structure is supposed to

provide encapsulation of the data collection, enabling the programmer to interact with the entire

data structure in a meaningful way as a container of data. By freeing the programmer from

having to know its implementation details and only exporting the interface of its efficient

operations, a generic Stack provides separation of data access$/$manipulation from internal data

representation. Programs that access the generic Stack only through the interface can be re$-$

used with any other Stack implementation, which results in modular programs with clear

functionality and that are more manageable

Goals:

$1.$ Implement a generic Stack.

$2.$ Write a program that parses Infix arithmetic expressions to Postfix arithmetic

expressions using a Stack.

$3.$ Write a program that evaluates Postfix arithmetic expressions using a Stack. Task $2$: Convert Infix Arithmetic Expressions into PostFix Arithmetic Expressions and

evaluate them $($whenever possible$)$

For the sake of this exercise, an arithmetic expression is a sequence of space$-$separated

strings. Each string can represent an operand, an operator, or parentheses.

Examples of operands: $"34","5","$a$",$ and $"$b$1"($alphanumeric$)$

Operators: one of the characters $"+","-","*",$ or $"/".$ As usual, $"/"$ and $"*"$ are regarded as having

higher precedence than $"+"$ or $"-$

$"$

Parentheses: $"("$ or $")"$

An Infix arithmetic expression is the most common form of arithmetic expression used.

Examples:

$(5+3)*12-7$ is an infix arithmetic expression that evaluates to $89$

$5+3*127$ is an infix arithmetic expression that evaluates to $34$

For the sake of comparison, postfix arithmetic expressions $($also known as reverse Polish

notation$)$ equivalent to the above examples are:

$53+12*7$

$5312*+7$

Two characteristics of the Postfix notation are $(1)$ any operator, such as $"+"$ or $"/"$ is applied to

the two prior operand values, and $(2)$ it does not require ever the use of parentheses.

More examples:

a $+$ b$1*$ c $+($ dd $*$ e $+$ f $)*$ G in Infix notation becomes a b$1$ c $*+$ dd e $*$ f $+$ G $*+$ in Postfix

notation.

To implement Infix to Postfix conversion with a stack, one parses the expression as sequence of

space$-$separated strings. When an operand $($i$.$e$.,$ an alphanumeric string$)$ is read in the input, it

is immediately output. Operators $($i$.$e$.,"-","*")$ may have to be saved by placement in the

operator$\_$stack. We also stack left parentheses. Start with an initially empty operator$\_$stack.

Follow these $4$ rules for processing operators$/$parentheses:

$1.$ If input symbol is $"(",$ push it into stack.

$2.$ If input operator is $"+","-","*",$ or $"/",$ repeatedly print the top of the stack to the output

and pop the stack until the stack is either $($i$)$ empty; $($ii$)$ a $"("$ is at the top of the stack; or

$($iii$)$ a lower$-$precedence operator is at the top of the stack. Then push the input operator

into the stack.

$3.$ If input operator is $")"$ and the last input processed was an operator, report an error.

Otherwise, repeatedly print the top of the stack to the output and pop the stack until a $"("$

is at the top of the stack. Then pop the stack discarding the parenthesis. If the stack is

emptied without a $"("$ being found, report error.

$4.$ If end of input is reached and the last input processed was an operator or $"("$ report error.

Otherwise print the top of the stack to the output and pop the stack until the stack is

empty. If an $"("$ is found in the stack during this process, report error.

Evaluating Postfix Arithmetic Expressions

After converting a given expression in Infix notation to Postfix notation, you will evaluate the

resulting arithmetic expression IF all the operands are numeric $($int$,$ float, etc.$)$ values.

Otherwise, if the resulting Postfix expression contains characters, your output should be equal

to the input.

Example inputs:

$53+12*7$

$5312*+7$

$35*$ c $10/$ Example outputs: $89$

$34$

$35*$ c $10/$

To achieve this, you will have an operand$\_$stack, initially empty. Assume that the expression

contains only numeric operands $($no variable names$).$ Operands are pushed into the stack as

they are ready from the input. When an operator is read from the input, remove the two values

on the top of the stack, apply the operator to them, and push the result onto the stack.