import java.util.*; /** Demo for the development of function evaluate */ public class D { /** Interpret a string as a formula and evaluate it. * * Formulas consist of a series of numbers separated by the * operators '+' or '-'. Formulas may contain space characters * between the numbers and the operators. * * Precondition: s is a valid formula and contain at least one number * * Examples: evaluate("3") returns 3 * evaluate("3 + 4") returns 7 * evaluate("100 - 25+50") returns 125 * evaluate("9") returns 9 * evaluate(" 7 + 7 + 7 ") returns 21 */ public static int evaluate(String s) { // TODO You can use Integer.parseInt to convert a string // (like "12345") to the corresponding integer (12345). s= s.replaceAll(" ", ""); int k= isolateInt(s, 0); int val= Integer.parseInt(s.substring(0, k)); // invariant: s[0..k-1] is an expression AND val is its value. // Either k = s.length OR s[k] is + or - while (k != s.length()) { int t= isolateInt(s, k+1); int val1= Integer.parseInt(s.substring(k+1, t)); val= s.charAt(k) == '+' ? val + val1 : val - val1; k= t; } return val; } /** Precondition: s[k] is a digit. * Return the largest t such that s[k..t-1] is an integer. */ private static int isolateInt(String s, int k) { int t= k+1; // invariant s[k..t-1] is an integer while (t != s.length() && Character.isDigit(s.charAt(t))) { t= t+1; } return t; } // ===================================================================== /* Our solution, above, takes a total of almost 30 lines, 8 of which are comments --specification, loop invariants, etc. It consists of two methods, with method bodies of about 15 and 6 lines. Each is easily understandable because of the way they are written and the loop invariants, etc. We show below three submissions, which are NOT readable. Major problem: Their loops do not reflect the structure of input String s. One has about 70 lines of code in ONE method body One has about 73 lines of code in ONE method body One has "only" about 50 lines in the method body and two other shorter methods, but the other methods are not specified and it is difficult to figure out what they do. */ // One way how not to write evaluate. Far too long public static int evaluate1(String s) { int i = 0; int sum = 0; String y = ""; String temp =s.replaceAll(" ",""); int count = temp.length()-1; System.out.println(temp); if ((temp.indexOf('-')==-1)&&(temp.indexOf('+')==-1)) return Integer.parseInt(temp); while (count > 0) { System.out.println("first x"); String x = Character.toString(temp.charAt(count)); System.out.println(x); System.out.println(y); if (x.equals("+")); { y = y + x; String hold = ""; for (int z = y.length()-1;z>=0;z--) { hold+=y.charAt(z); } System.out.println(hold); sum = sum + Integer.parseInt(hold); y = ""; } if (x.equals("-")) { y = y + x; String hold = ""; for (int z = y.length()-1;z>-1;z--) { hold+=y.charAt(z); } sum = sum - Integer.parseInt(hold); y = ""; } else { y = y + x; String hold = ""; for (int z = y.length()-1;z>=0;z--) { hold+=y.charAt(z); } sum = sum + Integer.parseInt(hold); } count--; i--; } System.out.println(y); return sum; } // =========================================================== public static int evaluate2(String s) { //Remove empty spaces s = s.replace(" ", ""); //Declare variables that will be used throughout loop String temp = ""; int sum = 0; int a = 0; boolean bool = true; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '+') { a = Integer.parseInt(temp); if (bool) { sum += a; temp = ""; a = 0; } else { sum -= a; temp = ""; a = 0; } bool = true; } else if (s.charAt(i) == '-') { a = Integer.parseInt(temp); if (bool) { sum += a; temp = ""; a = 0; } else { sum -= a; temp = ""; a = 0; } bool = false; } else { temp += s.charAt(i); } } a = Integer.parseInt(temp); if (bool) { sum += a; temp = ""; a = 0; } else { sum -= a; temp = ""; a = 0; } return sum; } // ======================================================== public static int evaluate3(String s) { int val=0; String st = s.trim(); if (st.indexOf('+')==-1 && st.indexOf('-')==-1){ val=getVal(st); return val; } //know both pl and min != -1 int pl = st.indexOf('+'); int min = st.indexOf('-'); boolean lastAdded = true; if ((pl < min || min == -1) && pl != -1){ val=getVal(st.substring(0, pl)); st = st.substring(pl); } else if (min != -1){ val=getVal(st.substring(0,min)); st= st.substring(min); lastAdded = false; } while (st.indexOf('+')!=-1 || st.indexOf('-')!=-1){ int plus = st.indexOf('+'); int minus = st.indexOf('-'); if (plus!=-1 && ((plus < minus) || minus==-1 )){ int c = getVal(st.substring(1, getNext(st))); //plus needs to be the next plus or minus, not plus val+=c; st = st.substring(plus); lastAdded = true; } else if (minus != -1){ int c = getVal(st.substring(1, getNext(st))); val-=c; st = st.substring(minus); lastAdded = false; } } if (st.length()>0 && lastAdded){ val += getVal(st); } else if (st.length() > 0 && !lastAdded){ val -= getVal(st); } return val; } private static int getVal(String s){ s=s.trim(); int a = Integer.parseInt(s); return a; } private static int getNext(String s){ String sNew=s.substring(1); int a=sNew.indexOf('+'); int b=sNew.indexOf('-'); if (a==-1 && b==-1){ return sNew.length()+1; } else if (a