Stack Class: https://github.com/PaulConradSBVC/CS265_SP2018/tree/master/Stacks

With the following pseudocode, write a C++ program using our stack class we created (I will not accept submissions using any Standard Template Library data structures) to convert any infix expression to reverse polish notation (note: you are not required to have your program evaluate the reverse polish notation express as I want your program to be able to accept variable names in the expression as well).

I have also provided a Java Jar file for you to run from the command line. Making sure you have at least the Java 8 JRE on your computer, type the following from the command line: java -jar JavaApplication9.jar where you have the JavaApplication9.jar file located on your computer.

Jar File Sample:

https://sbccd.instructure.com/courses/7227/files/415742/download?verifier=HBEUaJlY9LZfjEZaMDuYGkujhIaqXt1C7VjYDGXg&wrap=1

Pseudocode:

https://sbccd.instructure.com/courses/7227/files/419707/download?verifier=UyxzNdm9JL9MVqabbJ9WZ18sSRPwLFBQflSMBRoo&wrap=1

Refer to the following screenshot of some sample runs:

To be submitted:

Your C++ Program with all necessary source files stored in a zip file (50% reduction in score if I cannot compile your program - I will test against gnu gcc/g++)

Update: Re-posted pseudocode for better reading.

One thing to consider, is check the program when you run it to make sure it works okay with malformed infix expressions (hint: using the isEmpty() function can be a great friend for this!).

Function: convertToPostfix

Input parameter: infix as string

Output return value: postfix as string

1. Create an empty string to hold string our function will build, this is the post fix string.

2. Set a unary flag to true.

3. Create an empty stack of string.

4. Create an object of type CStringTokenizer to tokenize the infix string with the delimiters "()^+-

/%* ", and set flag for including delimiter to true.

5. while our CStringTokenizer object has more tokens:

A.

Create a token string holding the next token with any trailing whitespaces trimmed.

B.

if (token is equal to "") // do nothing

C.

else if:

i.

if (token is equal to "(":

a. Push(token) onto the stack.

ii.

else if (token is equal ")":

a. Create a string holding the operator character.

b. while (!(operator = pop()) is equal to "("):

1. post fix string += " " + operator.

iii.

else if (token is equal to "*" or token is equal to "^" or

token is equal to "+" or token is equal to "-" or token is equal to "%" or token is

equal to "/"):

a. if (unary==true):

1. token = "u" + token;

// a unary op always goes on

// the stack without popping any other op

2. Push(token) onto the stack

iv.

else:

a. Create an integer variable holding the operatorPrecedence(token)

b. While (!stack.isEmpty() and !stack.peek() is equal to "(")

and operatorPrecedence(stack.peek()) >= p):

1. Create a string holding the operator with the return value of stack.pop();

2. post fix string += " " + op;

c. Push(token) onto stack.

v.

unary = true; // if an operator is after this one, it has to be unary

D.

else // Else for if statement in 5B

postfix += " |" + token + "|";

unary = false; // any operator after an operand is binary

6. While (!stack.isEmpty()) {

A. Create a string holding the operator with the return value of stack.pop();

B. post fix string += " " + op;

7. return postfix;

Function: operatorPrecedence

Input parameter: operator of type string

Output return value: integer holding precedence level

1. if (operator is equal to "u-" or operator is equal to "u+"): return 3 //highest level operator

2.

else if (operator is equal to "^"): return 2

3.

else if (operator is equal to "*" or operator is equal to"/"

or operator is equal to "%"): return 1

4.

else if (operator is equal to "-" or operator is equal to "+"):

return 0;

5.

else {

return 0;

Main function test driver:

1. Prompt: " Enter an infix expression to convert: "

2. Read in a string input from keyboard (highly recommend using getline function).

3. Create string holding result of convertToPostfix(input).

4. Output the result to the terminal screen.

Paul-Conrads-Mac-Pro:dist paulconrads java -jar JavaApplication9.jar Enter an infix expression to convert: -36 postfix: 3 u-6 + Paul-Conrads-Mac-Pro:dist paulconrad$ java -jar JavaApplication9.jar Enter an infix expression to convert: -3 + (-abc) LX: postfix: 3 u- abc u-+ Paul-Conrads-Mac-Pro:dist paulconrad$ java -jar JavaApplication9.jar Enter an infix expression to convert: (x y + z)3 LX: postfix: xy+z+3/