C++: Infix to Prefix

Learning Outcomes

Implement two stacks and use them to implement an infix to prefix expression convertor

NOTE: #include is NOT ALLOWED.

Stacks

A stack is an abstract data type which uses a sequential container and limits access to that container to one end. You may enter or remove from the container, but only at one end. Using the Linked List data structure from your last homework assignment, implement a Stack of type string.

The Stack should only have one data member: the Linked List. It should implement the following methods:

• Stack(): Empty constructor.
• void clear(): removes all of the elements from the stack
• int size() const: returns the number of elements in the stack
• bool isEmpty() const: returns true if the stack is empty, false otherwise
• string top() const: returns the top of the stack. It must throw an error if the stack is empty.
• string pop(): returns the top of the stack and removes it. It must throw an error if the stack is empty.
• void push(string): adds a value of type string to the stack.

Your linked list should support adding to the end of the list.

Infix to Prefix Conversion

Suppose you have an infix expression a+c^d/g-h. Using the math operation priority, we learned this is equal to a+(((c^d)/g)-h).

The prefix expression of the above infix one is: + a - / ^ c d g h

Your program must read a math expression in string and prints its prefix equivalent.

An example of program run:

Please enter the infix math Expression: a+c^d/g-h

The equivalent prefix math expression is : + a - / ^ c d g h

Do you want to add another expression [Y/N]: Y

Another example of the program in which program returns an error message.

Please enter the infix math Expression: a++c^d/g-h

Sorry! The expression is not valid.

Do you want to add another expression [Y/N]: Y

The user must use * to declare the multiplication, and ^ to declare power.

The only valid operators are: ^ * / + -

User may enter ( and ) as many as they want provided the expression is correct. For example, the following expression is valid:

(((((((a+b)))))))+((((c))))

And the output must be: + + a b c

Program must treat variables such as ab as one operand and not the multiplication of a and b. (ab!=a*b)

See following example:

Please enter the infix math Expression: aa+c^dsa/gl-h

The equivalent prefix math expression is : + aa - / ^ c dsa g h

The aa and dsa are two operands.

Rules for Implementation

Start at the beginning of the expression string and evaluate each character based on these rules.

• You need two stacks. One is used to store the operators. The second one is used to store the operands. Be cautious that the operand stack not only stores the single operands such as a, b, cd but also combined operands. For example, in expression

a+b*c the b and c are the operands of the * operator. Then * b c all together is an operand to the + operator (the other operand of this operator is a)

• Checking the priority is the key in this assignment. Whenever you want to insert a new operator you should check the top of the operator stack. If the top one has a higher or equal priority you need to calculate the prefix one and then insert the new operator (look at the example I wrote for you.)

After all characters have been evaluated, perform one last check:

• If the operator stack is empty and operand stack has more than one item the expression is not valid.
• The final expression in the operand stack is the answer.

The InfixToPrefix Class

Create a new class called InfixToPrefix.hpp containing the following fields.

• std::string mExpression;
• Stack operator;
• Stack operand;

It will also have the following constructors and methods.

• A constructor which passes the expression in one string
• string toPrefix(): A method which evaluates the stored expression and returns the prefix expression.

Write the Driver.

The program will begin with a single prompt: " Please enter the infix math Expression: "

The user will supply an expression. Next, the program will prints the prefix expression of the given expression. If the expression is not valid, report print that the expression is not a valid infix expression. Finally, the program will wait for a final keystroke (i.e. pause). Make sure that your program works for all of the sample expressions.

What to Hand In

• linkedlist.hpp - the header file containing the entire class declaration and external definitions of the linkedlist class.
• stack.hpp - the header file containing the entire class declaration and external definitions of the stack class.
• infixToPrefix.hpp - the header file containing the entire class declaration and external definitions of the infixToPrefix class.
• Your driver with Main.cpp
• All files updated from the last homework assignment that have been updated to fit this new linked list.
• Make sure your name, CSCI 3250, and Programming Assignment 5 appear in comments in all of your files.
• Note: NO CREDIT will be given to programming assignments that do not compile.
• Make sure you have compiled and tested your program before handing it in.