/* In CS2110 lecture, we developed function eval.
 * That function is nice and simple, but it is inefficient.
 * Every time a s.substring(...) is called, a new String
 * object is created and that substring is stored in it.
 * The time it takes to do that is proportional to the length
 * of the substring. So if the substring is 1,000 characters long,
 * it takes at least 1,000 steps.
 * 
 * The loop repetend has 5 places where substring(...) or trim() is
 * called. We can reduce that to one place with careful programming.
 * 
 * Function evalEf (Ef for efficient) shows how to write it with only
 * one substring(...) call and no trim() callse in the body of the loop,
 * so it is more efficient. But it is far more complex!!!
 * This is just to show you how to write it without more calls.
 */
public class Demo {
    
    
    
    /** s contains an expression like the following ones
     *      " 4  "
     *      "4-5"
     *      "   5 + 8 - 123    -1    +  681241"
     *      
     *      The operands are ints without a sign.
     *      The operators are + or -.
     *      There is at least one int.
     *      Blanks can appear anywhere, except within an int.
     *      Return the value of the expression.
     */
    public static int eval(String s) {
        s= s.trim();
        // read in integer, store its value in res,
        // delete integer from s.
        int k= findEnd(s);
        int res= Integer.parseInt(s.substring(0, k));
        s= s.substring(k);
        
        s= s.trim();

        // this is what I know
        // res contains the value of what processed,
        // s contains what has NOT been processed,
        // s has no surrounding blanks
        while (s.length() > 0) {
            // Put s[0] into char pm and remove it from s
            char pm= s.charAt(0);
            s= s.substring(1);
            s= s.trim();

            // Read in integer, store it in v, remove it from s
            k= findEnd(s);
            int v= Integer.parseInt(s.substring(0, k));
            s= s.substring(k);
            
            s= s.trim();

            if (pm == '+') res= res + v;
            else res= res - v;
        }
        return res;
    }
    
    /** s contains an expression like the following ones
     * 
     *      " 4  "
     *      "4-5"
     *      "   5 + 8 - 123    -1    +  681241"
     *      
     *      The operands are ints without a sign.
     *      The operators are + or -.
     *      There is at least one int.
     *      Blanks can appear anywhere, except within an int.
     *      Return the value of the expression.
     */
    public static int evalEf(String s) {
        int k= firstNonBlank(s, 0);
        int h= lastNonBlank(s); 
        //the string to evaluate is s[k..h], with no surrounding blanks
        
        // read in integer, store its value in res,
        // Change k to (index of last digit of integer) + 1.
        int beg= k;
        k= findEnd(s, k);
        int res= Integer.parseInt(s.substring(beg, k));
        
        k= firstNonBlank(s, k); // s[k] is first non-blank in s
        
        // invariant res contains the value of what processed: s[0..k-1]
        // s[k..h] remains to be processed and has no surrounding blanks
        while (k <= h) {
            // Put s[k] into char pm and remove it from s[k..]
            char pm= s.charAt(k);
            k= k+1;
            
            k= firstNonBlank(s, k); // s[k] is first non-blank in s

            // Read in integer, store it in v, remove it from s[k..]
            beg= k;
            k= findEnd(s, k);
            int v= Integer.parseInt(s.substring(beg, k));
            
            k= firstNonBlank(s, k); // Skip over begining blanks in s..
            
            if (pm == '+') res= res + v;
            else res= res - v;
        }
        return res;
    }
    
    /**= index of first nonblank in s[k..] (or s.length() if all blanks) */
    public static int firstNonBlank(String s, int k) {
        while (k < s.length()  &&  Character.isWhitespace(s.charAt(k))) {
            k= k+1;
        }
        return k;
    }
    
    /**= index of last nonblank in s.
     * Precondition: There is a nonblank in s */
    public static int lastNonBlank(String s) {
        int h= s.length() - 1;
        while (Character.isWhitespace(s.charAt(h))) {
            h= h-1;
        }
        return h;
    }



    /** s[0] begins an integer. Return the index of the
     *  character after that integer.
     */
    public static int findEnd(String s) {
        int k= 1;
        // s[0..k-1] is an integer --consists of digits
        while (k < s.length()  &&  
                Character.isDigit(s.charAt(k))) {
            k= k+1;
        }
        return k;
    }
    
    /** s[h] begins an integer. Return the index of the
     *  character after that integer. */
    public static int findEnd(String s, int h) {
        int k= h;
        // s[h..k-1] is an integer --consists of digits
        while (k < s.length()  &&  Character.isDigit(s.charAt(k))) {
            k= k+1;
        }
        return k;
    }

    // write the loop to mimic the structure of the data
}