Hi Everyone
My code is an implementation of the shunting yard algorithm - Shunting-yard algorithm - Wikipedia, the free encyclopedia to convert infix expressions to postfix. I then try and solve the equations and print out the answer.
I have also created my own stack class and arrayList class.
I do not see why the array I declare is not outputting correctly. I have got a file which will have equations such as:
49+62*61-36
4/64
(53+26)
0*72
21-85+75-85
90*76-50+67
46*89-15
34/83-38
20/76/14+92-15
5*10/3-1
in it. Having tried to read the file and pass it to my methods I am unable to obtain the answer just the last thing that was read in? any help will be much appreciated.
The code:
myStack 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; } } }
myArraylist
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]; }*/ }
the test class where the shunting yard and RPN calculations should take place
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)); } } }