Evaluating an arithmetic expression without delimiters

Question

I want to create a method that evaluates an arithmetic expression like for example ((2+100)*5)*7 containing no spaces between operands and operators If there are spaces I would use the split method giving it the " " as delimiter.

Can anyone help me find the algorithm to solve this kind of problem?

Answer 1

Variant 1:

You can use the javascript engine to evaluate the expression.

private static final ScriptEngine engine = new ScriptEngineManager().getEngineByName("JavaScript");

public static String eval(String expression){
    if(expression == null){
        return "NULL";
    }
    String js_parsable_expression = expression
            .replaceAll("\\((\\-?\\d+)\\)\\^(\\-?\\d+)", "(Math.pow($1,$2))")
            .replaceAll("(\\d+)\\^(\\-?\\d+)", "Math.pow($1,$2)");
    try{
        return engine.eval(js_parsable_expression).toString();
    }catch(javax.script.ScriptException ex){
        return "NULL";
    }
}

Note that you have to convert all ^ to Math.pow for powers.

Variant 2

You can use the Shunting-yard alghoritm

Ex:

Input: 3+4

• Add 3 to the output queue (whenever a number is read it is added to the output)
• Push + (or its ID) onto the operator stack
• Add 4 to the output queue
• After reading the expression pop the operators off the stack and add them to the output.
• In this case there is only one, "+".

Output: 3 4 +

My implementation of the algorithm (sorry for the bad naming):

private static final TreeMap<Character, Integer> operatorsOrder= new TreeMap<Character, Integer>();
static
{
    operatorsOrder.put('(', 0);
    operatorsOrder.put(')', 0);  
    operatorsOrder.put('+', 1);
    operatorsOrder.put('-', 1);
    operatorsOrder.put('*', 2);
    operatorsOrder.put('/', 2);
    operatorsOrder.put('%', 2);
    operatorsOrder.put('s', 3);
    operatorsOrder.put('l', 3);
}

private void evalButtonActionPerformed(java.awt.event.ActionEvent evt)                                           
{ 
    final Stack<Character> operatori  = new Stack<Character>();
    final Stack<Double> valori = new Stack<Double>();

    String expresie = exprTf.getText();
    expresie = expresie.replaceAll("sqrt", "s");
    expresie = expresie.replaceAll("ln", "l");

    final StringBuilder builder = new StringBuilder();
    final char[] expresieChar = expresie.toCharArray();

    for(int i = 0; i<expresieChar.length; i++)
    {
        char ch = expresieChar[i];
        if (!operatorsOrder.containsKey(ch))
        {
            if(Character.isDigit(ch))
            {
                while (Character.isDigit(ch) || ch == '.')
                {
                    builder.append(ch);
                    if(++i <expresieChar.length)
                        ch = expresieChar[i];
                    else
                        break;
                }
                --i;
                valori.push(Double.parseDouble(builder.toString()));
                builder.delete(0, builder.capacity());
            }
            continue;
        }

        while (true)
        {
            if (operatori.isEmpty() || ch == '(' || (operatorsOrder.get(ch) > operatorsOrder.get(operatori.peek())))
            {
                operatori.push(ch);
                break;
            }

            final char op = operatori.pop();

            if (op == '(')
            {
                if(ch == ')')
                    break;
            }
            else if(op == 's' || op == 'l')
            {
                final double val1 = valori.pop();
                valori.push(eval(op, val1, 0));
            }
            else
            {
                final double val2 = valori.pop();
                final double val1 = valori.pop();
                valori.push(eval(op, val1, val2));
            }
        }
    }

    while (!operatori.isEmpty())
    {
        final char op = operatori.pop();
        if(op == 's' || op == 'l')
        {
            final double val1 = valori.pop();
            valori.push(eval(op, val1, 0));
        }
        else
        {
            final double val2 = valori.pop();
            final double val1 = valori.pop();
            valori.push(eval(op, val1, val2));
        }
    }
    resultLabel.setText(String.valueOf(valori.pop()));
    if(!operatori.isEmpty())
        System.out.println("There are operators left.");
    if(!valori.isEmpty())
        System.out.println("There are operands left.");
    }
}                                      

public static double eval(char op, double val1, double val2)
{
    switch (op)
    {
        case '+':
            return val1 + val2;
        case '-':
            return val1 - val2;
        case '/':
            return val1 / val2;
        case '*':
            return val1 * val2;
        case '%':
            return val1 % val2;
        case 's':
            return Math.sqrt(val1);
        case 'l':
            return Math.log(val1);
        default:
            throw new RuntimeException("Operator is invalid.");
    }
}

To solve the no delimiter problem, I transform the string expression to a character array and iterate over it. At each step I:

• check if it is a valid operator
• if it is, add it to the stack
• if it is not, check if it is a valid digit
• if it is, check if it has more digits and build a string for that number
• if it is not, build the number

Answer 2

You can use Javascript to evaluate the whole expression:

ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("JavaScript");
String exp = "((2+100)*5)*7";
System.out.println(engine.eval(exp));

Answer 3

A nice way to do this would be using some parser generator to create a parser of the input text. In java, there are several nice parsers. I would recommend using ANTLR, as the example you have provided is available in some of its basic tutorials. Some more details on that are on another question: Parsing an arithmetic expression and building a tree from it in Java

As pointed out, the accepted answer has a dead link. There are some variants of Five minute introduction to ANTLR 3 available