Evaluate Polynomial String without using regex and API

Question

Given a polynomial with a single variable x, and the value of x as input, compute its value. Examples:

eval("-2x^3+10x-4x^2","3")=-60

eval("x^3+x^2+x","6")=258

Description of issue: In this code I break the string into a substring whenever a +/- is encountered and pass the substring to a function which evaluates single term like "-2x^3". So my code for input = "-2x^3+10x-4x^2" calculates till "-2x^3+10x" only and skips "-4x^2" part.

Can anyone please tell me whats wrong here?

public class EvalPolyX2 {

    static String testcase1 = "-2x^3+10x-4x^2";
    static String testcase2 = "3";

    public static void main(String args[]){
        EvalPolyX2 testInstance = new EvalPolyX2();
        int result = testInstance.eval(testcase1,testcase2);
        System.out.println("Result : "+result);
    }

    public int eval(String str,String valx){

        int sum = 0;        
        String subStr = "";
        if(str.charAt(0) == '-')
        {
            int len = str.length();
            for (int i = 0; i < len; i++)
            {
                if(str.charAt(i) == '-' || str.charAt(i) == '+')
                {                   
                    subStr = str.substring(0, i);
                    System.out.println("subStr="+subStr);
                    sum += evalSubPoly(subStr, valx);
                    str = str.substring(i);
                    len = str.length();
                    i = 0;
                }               
            }
        }
        else if(str.charAt(0) != '-')
        {
            str = '+' + str;
            int len = str.length();
            for (int i = 0; i < len; i++)
            {
                if(str.charAt(i) == '-' || str.charAt(i) == '+')
                {
                    subStr = str.substring(0, i);
                    System.out.println("subStr="+subStr);
                    sum += evalSubPoly(subStr, valx);
                    str = str.substring(i);
                    len = str.length();
                    i=0;
                }
            }
        }
        return sum;
    }

    public int evalSubPoly(String poly,String valx){
        int len = poly.length();
        String num = "";
        String power = "";
        int exp = 0, coeff = 0;

        for(int i = 0; i < len; i++)
        {
            if(poly.charAt(i) == 'x')
            {
                num = poly.substring(0, i);
                coeff = Integer.parseInt(num);                              
            }
            if(poly.charAt(i) == '^')
            {
                power = poly.substring(i+1, len);
                exp = Integer.parseInt(power);
            }                       
        }

        if(power.equals(""))
            exp = 1;
        System.out.println("coeff="+coeff);

        int sum = 1;
        int x = Integer.parseInt(valx);

        for (int i = 0; i < exp; i++)
        {
            sum = sum*x;
        }
        System.out.println("sum="+sum);
        sum = sum*coeff;

        return sum;
    }
}

Answer 1

What's wrong with using regex? You can split the polynomial into monomials, evaluate each, and add all of the results.

private static final Pattern monomial = Pattern
        .compile("([+-])?(\\d+)?x(?:\\^(\\d+))?");

public static int eval(String str, String valx) {
    Matcher m = monomial.matcher(str);
    int x = Integer.parseInt(valx);

    int total = 0;
    while (m.find()) {
        String mul = m.group(2);
        int value = (mul == null) ? 1 : Integer.parseInt(m.group(2));

        String pow = m.group(3);
        value *= (pow == null) ? x : (int) Math.pow(x,
                Integer.parseInt(pow));

        if ("-".equals(m.group(1)))
            value = -value;

        total += value;
    }

    return total;
}

---

System.out.println(eval("-2x^3+10x-4x^2", "3"));
System.out.println(eval("x^3+x^2+x", "6"));

-60
258

Answer 2

This code replacement should help

  if(str.charAt(i) == '-' || str.charAt(i) == '+' || i == (len - 1))
  {   
    if(i == len - 1)
    {
     i++;
    }
    ...

Though there could be better ways, but I only wanted to show a way out here. The reason is you are looking for + or - as the delimiter. But the last part of the expression will not end with either of these but just probably EOL