Write a program that parses infix expressions (described below) into appropriate Tokens (operator or operand), stored in some linear container (ArrayList ?), passes the infix expression to a function that returns the expression to postfix form, then passes it to a function which evaluates the postfix expression, returns an integer. We'll be doing only integer arithmetic. No float types. Also, though the inputs are positive, the intermediate results might not be. The operators you will encounter are +, -, *, /, % (modulus). You must also be prepared to handle parenthesis. All will be done through an ant file.

Your code

I expect to see, at a minimum, 2 methods:

infix2postfix evalPostfix

I've written Token classes. You do need to fill in the Operator.getPrec() method, assign appropriate (relative) precedences to the operators.

The 2 types, Operand and Operator share a base class, Token, so that you can store an entire expression, in a generic ArrayList which holds Tokens. We need to get used to generics. Sample.java, in the directory, shows the creation and storage of various Tokens in a generic collection.

opType is an example of how we did "enums" pre- Java 1.5. Note that you can make these types smarter by assigning precedence right there. You're welcome to make this modification.

You need to use my Token classes.

Input

Your program will read a file called input.infix that contains a number of expressions, one per line. Each line has, at most, 80 characters. Tokens will be separated by white space. Operands will be strictly non-negative integers. Operators are: { + - * / % } for addition, subtraction, multiplication, division, and modulus, respectively.

Here is a sample input:

13 + 23 - 42 * 2 3 * ( 5 - 2 ) % 5

Output

Your program will output, for each input expression, on one line:

postfix expression = result , where result is the value of expression.

There will be one expression per line (same as the input). Single-space only, please.

So, given the input, above, the output should be:

13 23 + 42 2 * - = -48 3 5 2 - * 5 % = 4

Ant

You will include a build.xml that has, at a minimum, the following targets:

compile - compiles all of your .java files. run - runs your program, assuming that the input file is in the current directory. Depends on the compile target. Note, the code will need to be compiled from your source. I will delete all class files before we start, so... The run target will make sure all of your source files are run through javac. doc - runs javadoc on all of your source files, creating files in ./docs Note, since you're supplying build.xml, the names for the rest of the code doesn't matter. You can have 1 class, or 18 (though, that is probably overkill). The filenames don't matter to me (that is, they should be good names, but I don't need to know them ahead of time).

Algorithms

Infix to Postfix

Append a right paren ')' to the end of the input expression. Push a left paren '(' onto the stack. Start at the first token. For each token: If it is a left paren, push it onto the stack. If it is a right paren, pop operators from the stack and append to the postfix expression, until a left paren is encountered on the stack. Remove and discard the left paren. If it is an operand, append it to the postfix expression. If it is an operator, then pop operators from the stack and append to the postfix expression while the operators have equal or higher precedence than the current token. Push current token (operator) onto the stack. Remember, we're not treating the parentheses as operators, they're being handled separately. Continue until you've reached the end of the expression. If the input expression was valid, then evey pop() should've been fine, and the stack should be empty. Evaluating Postfix Expressions

Start at the first token. For each token: If it is an operand, push it on the stack. Else if it is an operator, then y pop top value x pop top value result x (oper) y push result onto stack fi Continue until you've reached the end of the expression. There should be exactly one element in the stack; the result of the expression.

Include

build.xml - your ant configuration file all source files. .class files will be deleted before so must be built from source. Whatever other Java files

Operand.java: public class Operand extends Token {

protected int val;

public boolean isOperator() { return false; } public boolean isOperand() { return true; }

public int getVal() { return val; }

public Operand( int v ) { val = v; }

}

Operator.java: public class Operator extends Token {

protected opType val;

public boolean isOperator() { return true; } public boolean isOperand() { return false; }

// helper method, returns (assigns) precedence for operators protected int getPrec() { // TODO: use a switch, whatever, assign ordinals to operators return 0; }

// handy for comparing 2 operators public static int compare( Operator a, Operator b ) { if( a.getPrec() == b.getPrec() ) return 0; else if( a.getPrec() < b.getPrec() ) return -1; else return 1; }

public opType getVal() { return val; }

public Operator( opType v ) { val = v; }

}

opType.java: import java.io.*;

public final class opType {

public static opType ADD = new opType( "Add" ); public static opType SUB = new opType( "Sub" ); public static opType MULT = new opType( "Mult" ); public static opType DIV = new opType( "Div" ); public static opType MOD = new opType( "Mod" ); public static opType LPAR = new opType( "LParen" ); public static opType RPAR = new opType( "RParen" );

protected String name;

private opType( String n ) { name = n; }

public String getName() // for debugging, maybe { return name; }

public static void main( String argv[] ) // testing { opType a = opType.ADD; opType b = opType.ADD; opType c = opType.MULT;

if( a != b ) System.out.println( "a and b should be the same (ADD)" );

if( a == c ) System.out.println( "a and c should not be the same (ADD vs. MULT)" );

if( b == c ) System.out.println( "b and c should not be the same (ADD vs. MULT)" );

System.out.println( "Done!" ); } }

Sample.java: import java.util.*; import java.io.*;

public class Sample { // nasty function, removes the first token static private List foo( List e ) { e.remove( 0 );

return e; }

static public void main( String[] argv ) { // Let's create a couple Operands and an Operator: Operand a = new Operand( 24 ); Operand b = new Operand( 13 ); Operator o = new Operator( opType.ADD );

Token t = new Operator( opType.MULT ); Token u = new Operand( 42 );

List list = new LinkedList(); list.add( new Operand( 2112 )); // this will be removed in foo list.add( a ); list.add( o ); list.add( b );

// just playing around here foo( list );

while( ! list.isEmpty() ) { t = list.remove( 0 ); if( t.isOperator() ) { Operator op = (Operator)t; System.out.println( "We have an operator: " + op.getVal().getName() ); if( op.getVal() == opType.ADD ) System.out.println( "We have addition!" ); } else System.out.println( "We have an operand: " + String.valueOf( ((Operand)t).getVal() )); } // while } }

Token.java: abstract class Token {

abstract boolean isOperator(); abstract boolean isOperand();

}