Lab - Infix Expression

Objectives

• Understand Infix to Prefix conversion

• Write out code to do Infix to Prefix conversion

• Talk about evaluating these expressions

Discussion

• Prefix, Infix, and Postfix are useful for several purposes. Primarily:

• Ease of parsing and converting prefix and postfix

• Ease of reading infix expressions and evaluating them

• Evaluating the expression is a matter of knowing which token you're dealing with.

• Refresher from lecture - Infix to Prefix/Postfix pseudocode:

expr = /*Some Infix Expression*/;
Stack S;
while (not done with expr) { // For each token in the infix expression
    t = nextToken(expr);
    if (t == ')') { // If a right parenthesis, then combine into subexpression
        rhs = S.pop();
        op  = S.pop();
        lhs = S.pop();
        s.push( lhs + rhs + op ); // Convert to Postfix form - do op + lhs + rhs for Prefix
    } else if (t != '(') { // Push everything except left parenthesis
        S.push(t)
    }
}
return S.pop();

• A visual example of this algorithm can be seen here.

Setup

We need to:

1. Create a directory called infix2prefix in your cs23001 folder

2. Create a file named infix2prefix.cpp in the infix2prefix directory

3. Copy the data3-1.txt file from the shared folder to your infix2prefix directory

Assignment

Create a program that reads in a file with infix expressions and prints out the prefix forms.

Your program should operate properly on any valid, fully parenthesized infix expression ended by a ';'. Each token of the expression will be separated by a space (' '). Example: ( ( A + B ) * C ) ;

Your code must make use of your Stack class from Project 3 Milestone 1 and your String class from Project 2 Milestone 4. You will also need to include vector.

You cannot hard-code the file to read expressions from. You must use command line arguments to open the file to read.

Requirements

The following should be true when you are done, NAMES MUST MATCH EXACTLY:

• In your cs23001 directory you have created a directory named infix2prefix.

• In the directory infix2prefix you have the following files:

• infix2prefix.cpp

• There are NO executables in the repository.

• Your program compiles, runs, and performs as specified.

• Your program follows the General Program Requirements.