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?

This is an [operator precedence](http://en.wikipedia.org/wiki/Order_of_operations) problem. In a recursive descent parser, you just descend from lower precedence operators to higher precedences, and use the parenthetical operator to jump back to the top. — Mike Samuel, Jul 02 '12 at 22:48
I hope this helps: http://en.wikipedia.org/wiki/Recursive_descent_parser — sarnold, Jul 02 '12 at 22:48
the expression `evaluate("4 + 1 * 3") ;` SHOULD return 7. if you wanted it to return 15 you should have written `evaluate("(4 + 1) * 3") ; ` — Nir Alfasi, Jul 02 '12 at 22:49
Sounds like you need a good compiler class and to learn how to implement a grammar. I have a more complete example of this in C++. https://bitbucket.org/linuxuser27/math-eengine — linuxuser27, Jul 02 '12 at 22:49
in addition, as an option, you maybe prefer [Reverse polish notaion](http://www.calculator.org/rpn.aspx) — Pavel K., Jul 02 '12 at 22:52
Recursive descent is a good parser but requires the the expression syntax to be translated to a grammar in Backus-Naur form. This isn't easy for the untrained. — Tony Ennis, Jul 02 '12 at 22:54
@alfasin: I don't think he's suggesting it should return 15 - he's just copied his test case verbatim from his first code example, and in that context it seems that the comment describes **intended** behaviour, not **observed** behaviour. I can see how the last example gives the opposite impression though. — Mac, Jul 02 '12 at 22:54
If this isn't homework check http://stackoverflow.com/questions/3422673/java-evaluate-string-to-math-expression — james_bond, Jul 02 '12 at 23:08

score 2 · Accepted Answer · answered Jul 02 '12 at 23:42

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);
    }

}

Tony Ennis · Answer 2 · 2012-07-02T23:14:02.983

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.

Writing String evaluation function

2 Answers2

Linked