Writing String evaluation function

Question

I'm trying to write a String evaluation function i.e.

evaluate("4 + 1") ; // returns 5 
evaluate("4 + 1 + 3") ; // returns 8 
evaluate("4 + 1 * 3") ; // returns 7 (not 15) 

The operators are + - / and *

My initial though was to use regular expressions to collect operators and digits as these can be matched. And than after finding that info, somehow figure out a way to prioritize /* ove -+ operators.

Here is how I started :

static String regex = "([\\+\\*-/])+";
static String digitRegex = "(\\d)+";

public static void main(String[] args) {
    System.out.println(getOperators("4 + 1 * 3"));
}

public static List<String> getOperators(String input) {
    Pattern p = Pattern.compile(regex);
    Matcher matcher = p.matcher(input);

    List<String> operatorList = new ArrayList<String>();

    int count = 0;
    while (matcher.find()){
        if (matcher.group(count) != null && matcher.group(count).trim().length() > 0) {
        operatorList.add(matcher.group(count));
        count++;
        }
    }

    return operatorList;
}

Now I can write another method to extract the digits using the same logic.

public static List<Integer> getDigits(String input) {
        Pattern p = Pattern.compile(digitRegex);
        Matcher matcher = p.matcher(input);

        List<Integer> digitList = new ArrayList<Integer>();

        int count = 0;
        while (matcher.find()) {
            if (matcher.group(count) != null && matcher.group(count).trim().length() > 0) {
                digitList.add(Integer.valueOf(matcher.group(count)));
                count++;
            }
        }

        return digitList;
    }

Now is the part where I'm stuck. #1 This above method fails on the third example :

evaluate("4 + 1 * 3") ; // returns 7 (not 15) 

And this #2 Even if I try previous examples, I can't figure it out how to put them in the correct order.

Am I on the right track at all, does anyone have some useful advice please share?

Answer 1

I wrote here something... let's say that quick & dirty is an understatement...
By all means, you SHOULDN'T use it "as is". It needs "fixing" - the reading of the numbers/arithmetic-operations should be done using StringTokenizer - but I'll leave the technicalities to you ;)

public class NewClass {

    public static int evaluate(String str){
        if("".equals(str)){
            return 0;
        }
        else if(str.length() == 1){
            return Integer.valueOf(str);
        }
        else{
            String _a = String.valueOf(str.charAt(0));
            String _b = String.valueOf(str.charAt(1));
            if("+".equals(_b) || "-".equals(_b) ){
                if("+".equals(_b)){
                    return Integer.valueOf(_a) + evaluate(str.substring(2));
                }
                else{// "-"
                    return Integer.valueOf(_a) - evaluate(str.substring(2));
                }
            }
            else{// "*" or "/"
                boolean isMulti = ("*".equals(_b));
                String  _c = String.valueOf(str.charAt(2));                
                Integer tmp = 0;
                if(isMulti){
                    tmp = Integer.valueOf(_a) * Integer.valueOf(_c);
                }
                else{
                    tmp = Integer.valueOf(_a) / Integer.valueOf(_c);
                }
                String new_str = String.valueOf(tmp) + str.substring(3);                
                return evaluate(new_str);
            }
        }
    }

    public static void main(String[] args){        
        String e = "4+1*3";
        int t = evaluate(e);
        System.out.println(e + " = "+t);
    }

}

Answer 2

You want an operator precedence parser. This is a very common table-based parser designed to do exactly what you want. Basically, you compare the operator being scanned with the one on top of a stack, and choose to reduce the stack (that is, do the math and push the result back on the stack), or push the operator.

As an added bonus, OPPs are easy and fun to write. You can add support for parenthesis etc with little additional effort.

edit - I just read that wiki article. It's terrible.

Find other examples of this type of parser.

Edit 2 -

This one shows a sample in c. Note the table.

This one is pretty good.

And remember, you're supporting a small number of operators, so don't get intimidated. besides, it's all the same once you implement a table.