Assignment Info.md

Infix to Postfix and Postfix Eval of BigIntegers

Due Thursday, May 24th by 11:59:59pm

Basic documentation is required, but no javadoc is necessary -- UNLESS YOU DID NOT SUCCESSFULLY UTILIZE JAVADOC ON YOUR LAST ASSIGNMENT For this assignment you will convert infix expressions to postfix expressions and then evaluate those postfix expressions. You will be given a table of symbols (A - Z) and their associated values to be used in evaluating expressions. The value for each symbol is to be considered a BigInteger. Negative values are also possible. Following this table you will be given a series of strings which will contain INFIX expressions which may be fully or partially parenthesized, but will be valid. The infix expressions will be given one per line and the series of expressions will be terminated by a line containing only a #. You may assume the following about the INFIX expressions:

• the expressions will contain only the characters: A through Z, +, -, *, /, ^, (, ). NOTE: ^ represents the exponent operator, which is not supported in Java. You will need to make a call to BigInteger.pow( ) when applying this operator to operands to evaluate the postfix expression you create. Note that the parameter to BigInteger.pow( ) is an int. If you encounter a BigInteger exponent that is larger than Integer.MAX_VALUE, throw an exception, handle it and write the error to output. Program execution should then continue on to the next expression
• the expressions will be correctly formed and all symbols used in the expressions will be defined.
• the expressions will have no spaces between symbols and operators.
• the values associated with symbols in the expressions will be positive or negative BigIntegers. Although the symbol values may be negative, the expressions will contain no unary negative operators.

The official name for the input file for this program is infix.txt (hard-code this into your program)-- all output is to the monitor. Here is a sample file you can use for testing -- it is by no means exhaustive -- make sure you add things to this file that properly test all categories of valid expressions -- the file is guaranteed to be well-formed and contain valid data and expressions throughout for the purposes of this assignment. It is permissible for you to collaborate with classmates on the postfix file you use for testing.

After printing out the INFIX expression, your program should convert the expression to POSTFIX form, using the algorithm discussed in class. Here are the lecture notes and code discussed in class After the conversion, the POSTFIX form of the expression should be printed out to the monitor. Finally, the POSTFIX expression should be evaluated (also using the algorithm discussed in class) and the final value of the expression should be printed out to the monitor. Here is sample output matching the infix.txt file shown above. The evaluation process will require a symbol table to be used to lookup the value associated with the expression symbols. This process should be repeated for each of the expressions. You may write your own Stack class or use the Java API! If you write your own, use the linked list version we did on the board in class.

Sample input file:

A -8
C 10
D 5
#
(A + C)*D
A+C * D
#

Sample output for the above input file:

Infix Expression: (A+C)*D
Postfix Equivalent: AC+D*
Expression value after postfix evaluation: 10

Infix Expression: A+C*D
Postfix Equivalent: ACD*+
Expression value after postfix evaluation: 42

To turn in:

Turn in a zip file named with your last name, followed by the first initial of your first name, followed by hw4 hw4 (e.g. armstrongehw4.zip ). Include all source and the robust input file you built and used to test your program. Name the file that contains the mane method and drives the program: InfixPostfixTester. Note that the InfixPostfixTester class should not do any conversions or calculations. You can use it to read in the data from the input file, but no work should be done on the data by the InfixPostfixTester class.

InfixPostfixTester.java

public class InfixPostfixTester {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//Like you said, this should not do any conversions.
		StackTester.main(args);
	}

}

input-file.txt

A -8
C 10
D 5
#
A+C*D

InToPost.java

import java.io.IOException;

//taken from below as the converter supplied failed. It gave back infix expressions.
// http://www.java-forums.org/java-lang/7557-how-convert-infix-arithmetic-expressions-postfix.html

public class InToPost {
  private Stack theStack;
 
  private String input;
 
  private String output = "";
 
  public InToPost(String in) {
    input = in;
    int stackSize = input.length();
    theStack = new Stack(stackSize);
  }
  
  //Had to add support for '^'
  public String doTrans() {
    for (int j = 0; j < input.length(); j++) {
      char ch = input.charAt(j);
      switch (ch) {
      case '+': 
      case '-':
        gotOper(ch, 1); 
        break; //   (precedence 1)
      case '*': // it's * or /
      case '/':
        gotOper(ch, 2); // go pop operators
        break; //   (precedence 2)
      case '^':
    	gotOper(ch, 2);
    	break;
      case '(': // it's a left paren
        theStack.push(ch); // push it
        break;
      case ')': // it's a right paren
        gotParen(ch); // go pop operators
        break;
      default: // must be an operand
        output = output + ch; // write it to output
        break;
      }
    }
    while (!theStack.isEmpty()) {
      output = output + theStack.pop();
 
    }
    //System.out.println(output);
    return output; // return postfix
  }
 
  public void gotOper(char opThis, int prec1) {
    while (!theStack.isEmpty()) {
      char opTop = theStack.pop();
      if (opTop == '(') {
        theStack.push(opTop);
        break;
      }// it's an operator
      else {// precedence of new op
        int prec2;
        if (opTop == '+' || opTop == '-')
          prec2 = 1;
        else
          prec2 = 2;        if (prec2 < prec1) // if prec of new op less
        { //    than prec of old
          theStack.push(opTop); // save newly-popped op
          break;
        } else
          // prec of new not less
          output = output + opTop; // than prec of old
      }
    }
    theStack.push(opThis);
  }
 
  public void gotParen(char ch){ 
    while (!theStack.isEmpty()) {
      char chx = theStack.pop();
      if (chx == '(') 
        break; 
      else
        output = output + chx; 
    }
  }
 
  public static void main(String[] args) throws IOException {
    String input = "1+2*4/5-7+3/6";
    String output;
    InToPost theTrans = new InToPost(input);
    output = theTrans.doTrans(); 
    System.out.println("Postfix is " + output + '\n');
 
  }
  class Stack {
    private int maxSize;
    private char[] stackArray;
    private int top;
    public Stack(int max) {
      maxSize = max;
      stackArray = new char[maxSize];
      top = -1;
    }
    public void push(char j) {
      stackArray[++top] = j;
    }
    public char pop() {
      return stackArray[top--];
    }
    public char peek() {
      return stackArray[top];
    }
    public boolean isEmpty() {
      return (top == -1);
    }
  }
 
}

LinkedStack.java

public class LinkedStack<E> {
	private class Node<F> {
		F data;
		Node<F> next;
		
		public Node(F data, Node<F> next) {
			this.data = data;
			this.next = next;
		}
	}
	
	private Node<E> head;
	
	public LinkedStack() {
		head = null;
	}
	
	public void push(E data) {
		Node<E> newNode = new Node<E>(data, head);
		head = newNode;
	}
	
	public E peek() {
		return head == null ? null : head.data;
	}
	
	public E pop() {
		E ret = head.data;
		head = head.next;
		
		return ret;
	}
	
	public void nuke() {
		head = null;
	}
	
	public boolean isEmpty() {
		return head == null;
	}
}

Output.txt

sam@fluttershy:~/Code/PostfixEval$ cd bin; java StackTester ../test1.txt ; cd ..

 Processing symbol table


 Storing symbol [A]

Index should be 0

 Storing symbol [C]

Index should be 2

 Storing symbol [D]

Index should be 3

 Processing infix expressions

Infix expression: A+C*D
A
A+
A+C
A+C*
A+C*D
Postfix expression: A+C*D

StackTester.java

import java.io.*;
import java.math.BigInteger;
import java.util.LinkedList;

public class StackTester
{
	public static void main(String[] args)
	{
		String fileName = args.length > 0 ? args[0] :"/home/sam/Code/PostfixEval/test1.txt";
		
		//**************************************************
		try
		{
			FileInputStream fstream = new FileInputStream(fileName);
			DataInputStream in = new DataInputStream(fstream);
			BufferedReader br = new BufferedReader( new InputStreamReader(in));
			
			String strLine;
			
			//BigInteger[] symbols = new BigInteger[26];
			LinkedList<BigInteger> symbols = new LinkedList<BigInteger>();
			
			for(int derp = 0; derp < 26; derp++) {
				symbols.add(derp, null);
			}
			
			boolean symTable = true; //reading symbol table
			boolean infixData = false; // reading infix expressions
			
			System.out.println("Processing symbol table");
			
			while((strLine = br.readLine()) != null)
			{
				strLine = strLine.trim(); // trim any leading or trailing spaces
				if(strLine.length() == 0)
				{
				 	continue; //skips empty lines
				}
				if(strLine.startsWith("#")) //Using a hash to separate the symbols definition and the expressions
				{
					if(!infixData)
					{
						System.out.println("\n Processing infix expressions\n");
						symTable = false;
						infixData = true;
					}
					continue; //so continue to the next string
				}
				
				if(symTable) // processes symbol table data
				{
					String delims = " ";//splits on 1 or more spaces
					String[] tokens = strLine.split(delims);
					
					System.out.println("Storing symbol [" + tokens[0] + "] - " + tokens[1]);
					
					int index = tokens[0].charAt(0) - 'A'; //"hashing" function
					
					//System.out.printf("Index should be %d\n", index);
					
					BigInteger derp = new BigInteger(tokens[1]);
					
					symbols.add(index, derp);
				}
				
				//Process the expressions as they come
				if(infixData) // process infix expressions
				{
					System.out.printf("Infix expression: %s\n", strLine);
					
					String postfixExpression = "";
					InToPost converter = new InToPost(strLine);
					postfixExpression = converter.doTrans();
					
					System.out.printf("Postfix expression: %s\nNow parsing it\n", postfixExpression);
					
					//Okay, so, now we've got the expression in the thing. Now to evaluate it.
					
					LinkedStack<BigInteger> stack = new LinkedStack<BigInteger>();
					boolean divByZero = false;
					
					for(char c : postfixExpression.toCharArray()) {
						if(isOperand(c)) {
							stack.push(symbols.get(c-'A'));
						} else if(isOperator(c)) {
							BigInteger right = stack.pop();
							BigInteger left = stack.pop();
							
							if(right == null || left == null) {
								break;
							}
							
							if(c == '+') {        //Do adding
								stack.push(left.add(right));
							} else if(c == '-') { //Do Subtraction
								stack.push(left.subtract(right));
							} else if(c == '*') { //multiply
								stack.push(left.multiply(right));
							} else if(c == '/') { //divide
								if (right.intValue() == 0) {
									//System.out.println("Will not divide by zero.");
									divByZero = true;
									break;
								}
								stack.push(left.divide(right));
							} else if(c == '^') {
								stack.push(left.pow(right.intValue()));
							}
						}
					}
					
					System.out.printf("Got this: %s\n\n", divByZero ? "Divide by zero error, nice try" : stack.pop());
				}
			}
		}
		catch(Exception e)
		{
			System.err.println("Error: " + e.getMessage());
			e.printStackTrace();
		}
	}
	
	private static boolean isOperand (char cIn) {
		return (cIn >= 'A' && cIn <= 'Z');
	}

	private static boolean isOperator (char cIn) {
		return cIn == '^' || cIn == '*' || cIn == '/' || cIn == '+' || cIn == '-';
	}
}

test1.txt

A -8
B 50
C 10
D 5
E 50000
F 0
#
A+C*D
(A+C)*D
C^E
E/F
((A+C*D)-F+(B-C))
C^E^E