Skip to content

Instantly share code, notes, and snippets.

@keshavsaharia
Created June 19, 2014 21:28
Show Gist options
  • Save keshavsaharia/8cddba0103b677170da9 to your computer and use it in GitHub Desktop.
Save keshavsaharia/8cddba0103b677170da9 to your computer and use it in GitHub Desktop.
Shunting Yard
package PhotoEditor;
import java.util.ArrayList;
public class Calculator {
public int calculate( String expression ) {
// Split it apart
String[] parts = splitApart(expression);
// Make two lists, one for numbers and another for operators
ArrayList<Integer> numbers = new ArrayList<Integer> ();
ArrayList <String> operators = new ArrayList<String> ();
// Am I expecting a number or an operator?
boolean isNumber = true;
for (String s : parts) {
// If we're expecting a number
if (isNumber) {
// Parse out the integer value of the string
int i = Integer.parseInt(s);
// Add it to the numbers list
numbers.add(i);
// Indicate that we are now looking for an operator
isNumber = false;
}
// If we're expecting an operator
else {
// If I have no operators
if (operators.size() == 0) {
operators.add(s);
}
// I have stuff on the list
else {
// While the last operator has greater or equal precedence to this one
while (operators.size() > 0 && // while there is an operator to check
precedence( operators.get(operators.size() - 1) ) >= precedence(s)) {
int newNumber =
simplify( operators.get(operators.size() - 1), // first input - last operator
numbers.get(numbers.size() - 2), // second input - last number
numbers.get(numbers.size() - 1) // third input - second to last number
);
// Remove stuff from the list
operators.remove(operators.size() - 1);
numbers.remove(numbers.size() - 1);
numbers.remove(numbers.size() - 1);
// Then add on the new number
numbers.add(newNumber);
}
// When you're done simplifying, add the operator on
operators.add(s);
}
// Say I am now expecting a number
isNumber = true;
}
//System.out.println(numbers);
//System.out.println(operators);
}
// While I have an operator to simplify
while (operators.size() > 0) {
int newNumber =
simplify( operators.get(operators.size() - 1), // first input - last operator
numbers.get(numbers.size() - 2), // second input - last number
numbers.get(numbers.size() - 1) // third input - second to last number
);
// Remove stuff from the list
operators.remove(operators.size() - 1);
numbers.remove(numbers.size() - 1);
numbers.remove(numbers.size() - 1);
// Then add on the new number
numbers.add(newNumber);
}
return numbers.get(0);
}
public String[] splitApart( String input ) {
return input.split(" ");
}
public int precedence( String operator ) {
if ( operator.equals("+") ) {
return 1;
}
if ( operator.equals("-") ) {
return 1;
}
if ( operator.equals("*") ) {
return 2;
}
if ( operator.equals("/") ) {
return 2;
}
return 0;
}
public int simplify(String op, int a, int b) {
if (op.equals("+")) {
return a + b;
}
if (op.equals("-")) {
return a - b;
}
if (op.equals("*")) {
return a * b;
}
if (op.equals("/")) {
return a / b;
}
return 0;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment