Java Calculator problems

[Pj Hughes]

Hi

I have managed to get a calculator program written although it is not working properly at the moment. For this purpose I have written my own stack and array classes.

I have made a file with only one equation in it:
49+62*61-36

and the program output should be - the second line should be in RPN format:
49+62*61-36
[49+62*61-36]
3795

But I am currently getting:
49+62*61-36
[36]
36.0

I don't see why it is only keeping the last token? all code is shown below. Any help will be much appreciated.

My arraylist class

import java.util.Arrays;

public class myArrayList<Item> {

	private Object[] myStore;
	private int actSize = 0;

	public myArrayList() {
		myStore = new Object[100];
	}

	public Object get(int index) {
		if (index < actSize) {
			return myStore[index];
		} else {
			throw new ArrayIndexOutOfBoundsException();
		}
	}

	public void add(Object obj) {
		if (myStore.length - actSize <= 0) {
			increaseListSize();
		}
		myStore[actSize++] = obj;
	}

	public Object remove(int index) {
		if (index < actSize) {
			Object obj = myStore[index];
			myStore[index] = null;
			int tmp = index;
			while (tmp < actSize) {
				myStore[tmp] = myStore[tmp + 1];
				myStore[tmp + 1] = null;
				tmp++;
			}
			actSize--;
			return obj;
		} else {
			throw new ArrayIndexOutOfBoundsException();
		}

	}

	public int size() {
		return actSize;
	}

	private void increaseListSize() {
		myStore = Arrays.copyOf(myStore, myStore.length * 2);
	}

	@SuppressWarnings("unchecked")
	public <T> T[] toArray(T[] a) {
		if (a.length < size())
			// Make a new array of a's runtime type, but my contents:
			return (T[]) Arrays.copyOf(myStore, size(), a.getClass());
		System.arraycopy(myStore, 0, a, 0, size());
		if (a.length > size())
			a[size()] = null;
		return a;
	}

	// Positional Access Operations

	/*@SuppressWarnings("unchecked")
	E elementData(int index) {
		return (E) myStore[index];
	}*/

}

my stack class

import java.util.Iterator;
import java.util.NoSuchElementException;

public class myStack<Item> implements Iterable<Item> {
	private int N; // size of the stack
	private Node first; // top of stack

	private class Node {
		private Item item;
		private Node next;
	}

	/**
	 * Create an empty stack.
	 */
	public myStack() {
		first = null;
		N = 0;
		assert check();
	}

	public boolean isEmpty() {
		return first == null;
	}

	public int size() {
		return N;
	}

	public void push(Item item) {
		Node oldfirst = first;
		first = new Node();
		first.item = item;
		first.next = oldfirst;
		N++;
		assert check();
	}

	public Item pop() {
		if (isEmpty())
			throw new NoSuchElementException("Stack underflow");
		Item item = first.item; // save item to return
		first = first.next; // delete first node
		N--;
		assert check();
		return item; // return the saved item
	}

	public Item peek() {
		if (isEmpty())
			throw new NoSuchElementException("Stack underflow");
		return first.item;
	}

	public String toString() {
		StringBuilder s = new StringBuilder();
		for (Item item : this)
			s.append(item + " ");
		return s.toString();
	}

	// check internal invariants
	private boolean check() {
		if (N == 0) {
			if (first != null)
				return false;
		} else if (N == 1) {
			if (first == null)
				return false;
			if (first.next != null)
				return false;
		} else {
			if (first.next == null)
				return false;
		}

		// check internal consistency of instance variable N
		int numberOfNodes = 0;
		for (Node x = first; x != null; x = x.next) {
			numberOfNodes++;
		}
		if (numberOfNodes != N)
			return false;

		return true;
	}

	public Object[] toArray(String[] elementData) {
		return (Object[]) elementData.clone();
	}

	public Iterator<Item> iterator() {
		return new ListIterator();
	}

	// did not implement remove as it was not needed
	private class ListIterator implements Iterator<Item> {
		private Node current = first;

		public boolean hasNext() {
			return current != null;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

		public Item next() {
			if (!hasNext())
				throw new NoSuchElementException();
			Item item = current.item;
			current = current.next;
			return item;
		}
	}
}

the class where the calculations happen.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class TestClass {

	private static final int LEFT_ASSOC = 0;
	private static final int RIGHT_ASSOC = 1;
	static String OPERATORS1 = "+-*/()";

	// Operators
	private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
	static {
		// Map<"token", []{precedence, associativity}>
		OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
		OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
		OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
		OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
		OPERATORS.put("(", new int[] {1, RIGHT_ASSOC});
		OPERATORS.put(")", new int[] {1, LEFT_ASSOC});
	}

	private static boolean isOperator(String token) {
		return OPERATORS.containsKey(token);
	}

	// Test associativity of operator token
	private static boolean isAssociative(String token, int type) {
		if (!isOperator(token)) {
			throw new IllegalArgumentException("Invalid token: " + token);
		}

		if (OPERATORS.get(token)[1] == type) {
			return true;
		}
		return false;
	}

	// Compare precedence of operators.
	private static final int cmpPrecedence(String token1, String token2) {
		if (!isOperator(token1) || !isOperator(token2)) {
			throw new IllegalArgumentException("Invalid tokens: " + token1
					+ " " + token2);
		}
		return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
	}

	public static String[] infixToRPN(String[] inputTokens) {
		myArrayList<String> out = new myArrayList<String>();
		myStack<String> stack = new myStack<String>();
		// For each token
		for (String token : inputTokens) {
			StringTokenizer tokens = new StringTokenizer(token,OPERATORS1,true);
			while (tokens.hasMoreTokens()) {
				token = tokens.nextToken();

			}
			// If token is an operator
			if (isOperator(token)) {
				// While stack not empty AND stack top element
				// is an operator
				while (!stack.isEmpty() && isOperator(stack.peek())) {
					if ((isAssociative(token, LEFT_ASSOC) && cmpPrecedence(
							token, stack.peek()) <= 0)
							|| (isAssociative(token, RIGHT_ASSOC) && cmpPrecedence(
									token, stack.peek()) < 0)) {
						out.add(stack.pop());
						continue;
					}
					break;
				}
				// Push the new operator on the stack
				stack.push(token);
			}
			// If token is a left bracket '('
			else if (token.equals("(")) {
				stack.push(token); 
			}
			// If token is a right bracket ')'
			else if (token.equals(")")) {
				while (!stack.isEmpty() && !stack.peek().equals("(")) {
					out.add(stack.pop());
				}
				stack.pop();
			}
			// If token is a number
			else {
				out.add(token);
			}
		}
		while (!stack.isEmpty()) {
			out.add(stack.pop());
		}
		String[] output = new String[out.size()];
		return out.toArray(output);
	}

	public static double RPNtoDouble(String[] tokens) {
		myStack<String> stack = new myStack<String>();

		// For each token

		for (String token : tokens) {
			//System.out.println( "Working this token: " + token );
			// If the token is a value push it onto the stack
			if (!isOperator(token)) {
				stack.push(token);
			} else {
				// Token is an operator: pop top two entries
				Double d2 = Double.valueOf(stack.pop());
				Double d1 = Double.valueOf(stack.pop());

				// Get the result
				Double result = token.compareTo("+") == 0 ? d1 + d2 : token
						.compareTo("-") == 0 ? d1 - d2
								: token.compareTo("*") == 0 ? d1 * d2 : d1 / d2;

				// Push result onto stack
				stack.push(String.valueOf(result));
			}
		}

		return Double.valueOf(stack.pop());
	}

	static public void main(String[] args) throws IOException {
		File file = new File("testEquations.txt");
		String[] lines = new String[1];

		try {
			FileReader reader = new FileReader(file);
			@SuppressWarnings("resource")
			BufferedReader buffReader = new BufferedReader(reader);
			int x = 0;
			String s;
			while ((s = buffReader.readLine()) != null) {
				lines[x] = s;
				x++;
			}
		} catch (IOException e) {
			System.exit(0);
		}
		// test printing string array
		for (String s : lines) {
			System.out.println("" + s);
			String[] output =infixToRPN(lines);
			System.out.println(Arrays.toString(output));
			System.out.println(RPNtoDouble(output));
		}


	}

}

[Campbell Ritchie]

What algorithm are you using to determine how to change to RPN (I presume that means Reverse Polish Notation, which I usually call postfix)? How do you turn 1 + 2 × 3 into 1 2 3 × +?

[Pj Hughes]

Campbell Ritchie wrote:What algorithm are you using to determine how to change to RPN (I presume that means Reverse Polish Notation, which I usually call postfix)? How do you turn 1 + 2 × 3 into 1 2 3 × +?

Hi

yes it is postfix I want the expression in.

I am using the shunting yard algorithm.

[Pj Hughes]

Hi

I have managed to get it working for the file with one equation in it.

I am now getting the following error when trying to read in more than one line?

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
at uk.ac.shef.dcs.com262.coa10pjh.TestClass.main(TestClass.java:146)


Is there a way to make it do it line by line?

THE CHANGE MADE WAS TO MOVE THE END BRACKET OF THE WHILE STATEMENT TO LINE 101

UPDATED VERSION JUST IN CASE

package uk.ac.shef.dcs.com262.coa10pjh;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class TestClass {

	private static final int LEFT_ASSOC = 0;
	private static final int RIGHT_ASSOC = 1;
	static String OPERATORS1 = "+-*/()";

	// Operators
	private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
	static {
		// Map<"token", []{precedence, associativity}>
		OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
		OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
		OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
		OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
		OPERATORS.put("(", new int[] {1, RIGHT_ASSOC});
		OPERATORS.put(")", new int[] {1, LEFT_ASSOC});
	}

	private static boolean isOperator(String token) {
		return OPERATORS.containsKey(token);
	}

	// Test associativity of operator token
	private static boolean isAssociative(String token, int type) {
		if (!isOperator(token)) {
			throw new IllegalArgumentException("Invalid token: " + token);
		}

		if (OPERATORS.get(token)[1] == type) {
			return true;
		}
		return false;
	}

	// Compare precedence of operators.
	private static final int cmpPrecedence(String token1, String token2) {
		if (!isOperator(token1) || !isOperator(token2)) {
			throw new IllegalArgumentException("Invalid tokens: " + token1
					+ " " + token2);
		}
		return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
	}

	public static String[] infixToRPN(String[] inputTokens) {
		myArrayList<String> out = new myArrayList<String>();
		myStack<String> stack = new myStack<String>();
		// For each token
		for (String token : inputTokens) {
			StringTokenizer tokens = new StringTokenizer(token,OPERATORS1,true);
			while (tokens.hasMoreTokens()) {
				token = tokens.nextToken();


				// If token is an operator
				if (isOperator(token)) {
					// While stack not empty AND stack top element
					// is an operator
					while (!stack.isEmpty() && isOperator(stack.peek())) {
						if ((isAssociative(token, LEFT_ASSOC) && cmpPrecedence(
								token, stack.peek()) <= 0)
								|| (isAssociative(token, RIGHT_ASSOC) && cmpPrecedence(
										token, stack.peek()) < 0)) {
							out.add(stack.pop());
							continue;
						}
						break;
					}
					// Push the new operator on the stack
					stack.push(token);
				}
				// If token is a left bracket '('
				else if (token.equals("(")) {
					stack.push(token); 
				}
				// If token is a right bracket ')'
				else if (token.equals(")")) {
					while (!stack.isEmpty() && !stack.peek().equals("(")) {
						out.add(stack.pop());
					}
					stack.pop();
				}
				// If token is a number
				else {
					out.add(token);
				}

				while (!stack.isEmpty()) {
					out.add(stack.pop());
				}
			}
		}
		String[] output = new String[out.size()];
		return out.toArray(output);
	}

	public static double RPNtoDouble(String[] tokens) {
		myStack<String> stack = new myStack<String>();

		// For each token

		for (String token : tokens) {
			//System.out.println( "Working this token: " + token );
			// If the token is a value push it onto the stack
			if (!isOperator(token)) {
				stack.push(token);
			} else {
				// Token is an operator: pop top two entries
				Double d2 = Double.valueOf(stack.pop());
				Double d1 = Double.valueOf(stack.pop());

				// Get the result
				Double result = token.compareTo("+") == 0 ? d1 + d2 : token
						.compareTo("-") == 0 ? d1 - d2
								: token.compareTo("*") == 0 ? d1 * d2 : d1 / d2;

				// Push result onto stack
				stack.push(String.valueOf(result));
			}
		}

		return Double.valueOf(stack.pop());
	}

	static public void main(String[] args) throws IOException {
		File file = new File("testEquations.txt");
		String[] lines = new String[1];

		try {
			FileReader reader = new FileReader(file);
			@SuppressWarnings("resource")
			BufferedReader buffReader = new BufferedReader(reader);
			int x = 0;
			String s;
			while ((s = buffReader.readLine()) != null) {
				lines[x] = s;
				x++;
			}
		} catch (IOException e) {
			System.exit(0);
		}
		// test printing string array
		for (String s : lines) {
			System.out.println("" + s);
			String[] output =infixToRPN(lines);
			System.out.println(RPNtoDouble(output));

		}


	}

}

[Pj Hughes]

Managed to get the brackets issue resolved by removing them from the hashmap declaration.

[Pj Hughes]

I have also managed to fix the Array out of bounds issue. I forgot to resize the array after increasing the file size.

I am now getting the same answer for each equation? can somebody point out my error? any advice will be much appreciated.

the output is:
49+62*61-36
15.666666666666668
4/64
15.666666666666668
(53+26)
15.666666666666668
0*72
15.666666666666668
21-85+75-85
15.666666666666668
90*76-50+67
15.666666666666668
46*89-15
15.666666666666668
34/83-38
15.666666666666668
20/76/14+92-15
15.666666666666668
5*10/3-1
15.666666666666668

instead of:

49+62*61-36
3795
4/64
0.0625
(53+26)
79
0*72
0
21-85+75-85
-74
90*76-50+67
6857
46*89-15
4079
34/83-38
-37.5903614458
20/76/14+92-15
77.0187969925
5*10/3-1
15.666666666666668