2

I found the code of Math Expression Parser from Dreamincode Forum.

My question is, on that code I think everything is going all right, but when I had a testcase '(2(3+5)' , that was valid, whereas this test case is completely wrong

but if I give the test case '(3+5)2)' it was detect as non valid input. Anyone knows why this is happening?

//enum for Operator "objects"
import java.util.*;

public enum Operator {

    ADD("+", 1)
    {
        double doCalc(double d1, double d2) {
            return d1+d2;
        }
    },
    SUBTRACT("-",1)
    {
        double doCalc(double d1, double d2) {
            return d1-d2;
        }
    },
    MULTIPLY("*", 2)
    {
        double doCalc(double d1, double d2) {
            return d1*d2;
        }
    },
    DIVIDE("/",2)
    {
        double doCalc(double d1, double d2) {
            return d1/d2;
        }
    },
    STARTBRACE("(", 0)
    {
        double doCalc(double d1, double d2) {
            return 0;
        }
    },
    ENDBRACE(")",0)
    {
        double doCalc(double d1, double d2) {
            return 0;
        }
    },
    EXP("^", 3)
    {
        double doCalc(double d1, double d2) {
            return Math.pow(d1,d2);
        }
    };

    private String operator;
    private int precedence;

    private Operator(String operator, int precedence) {
        this.operator = operator;
        this.precedence = precedence;
    }

    public int getPrecedenceLevel() {
        return precedence;
    }

    public String getSymbol() {
        return operator;
    }

    public static boolean isOperator(String s) {
        for(Operator op : Operator.values()) { //iterate through enum values
            if (op.getSymbol().equals(s))
                return true;
        }
        return false;
    }

    public static Operator getOperator(String s) 
        throws InvalidOperatorException {
            for(Operator op : Operator.values()) { //iterate through enum values
                if (op.getSymbol().equals(s))
                    return op;
            }
            throw new InvalidOperatorException(s + " Is not a valid operator!");
    }

    public boolean isStartBrace() {
        return (operator.equals("("));
    }
    //overriding calculation provided by each enum part
    abstract double doCalc(double d1, double d2);
}
//error to be thrown/caught in ProjectOne.java
class InvalidOperatorException extends Exception {
    public InvalidOperatorException() {
    }

    public InvalidOperatorException(String s) {
        super(s);
    }
}



//reading in a string at doing the parsing/arithmetic 
public static void main (String[] args) {
     String input = "";
     //get input
     System.out.print("Enter an infix exp<b></b>ression: ");
        BufferedReader in = new BufferedReader(
                                new InputStreamReader(System.in));
        try {                        
            input = in.readLine();
        }
        catch (IOException e)
        {
            System.out.println("Error getting input!");
        }

        doCalculate(input);
    }

    // Input: user entered string
    // Output: Display of answer
    public static void doCalculate(String equation) {
        //our stacks for storage/temp variables
        Stack<Operator> operatorStack;
        Stack<Double> operandStack;
        double valOne, valTwo, newVal;
        Operator temp;

        //initalize
        StringTokenizer tokenizer = new StringTokenizer(equation, " +-*/()^", true);
        String token = "";
        operandStack = new Stack();
        operatorStack = new Stack();
        try {
                while(tokenizer.hasMoreTokens()){ //run through the string
                    token = tokenizer.nextToken();
                    if (token.equals(" ")) { //handles spaces, goes back up top
                        continue;
                    }
                    else if (!Operator.isOperator(token)){ //number check
                        operandStack.push(Double.parseDouble(token));
                    }
                    else if (token.equals("(")) {
                        operatorStack.push(Operator.getOperator(token));
                    }
                    else if (token.equals(")")) { //process until matching paraentheses is found
                        while (!((temp = operatorStack.pop()).isStartBrace())) {
                            valTwo = operandStack.pop();
                            valOne = operandStack.pop();
                            newVal = temp.doCalc(valOne, valTwo);
                            operandStack.push(newVal);
                        }
                    }
                    else { //other operators
                        while (true) { //infinite loop, check for stack empty/top of stack '('/op precedence
                            if ((operatorStack.empty()) || (operatorStack.peek().isStartBrace()) || 
                                (operatorStack.peek().getPrecedenceLevel() < Operator.getOperator(token).getPrecedenceLevel())) {
                                    operatorStack.push(Operator.getOperator(token));
                                    break; //exit inner loop
                            }
                            temp = operatorStack.pop();
                            valTwo = operandStack.pop();
                            valOne = operandStack.pop();
                            //calculate and push
                            newVal = temp.doCalc(valOne, valTwo);
                            operandStack.push(newVal);
                        }
                    }
                }
            }
            catch (InvalidOperatorException e) {
                System.out.println("Invalid operator found!");
            }

            //calculate any remaining items (ex. equations with no outer paraentheses)
            while(!operatorStack.isEmpty()) {
                temp = operatorStack.pop();
                valTwo = operandStack.pop();
                valOne = operandStack.pop();
                newVal = temp.doCalc(valOne, valTwo);
                operandStack.push(newVal);
            }
            //print final answer
            System.out.println("Answer is: " + operandStack.pop()); 
        }
6
  • Two right parens but only one left? Commented Jan 3, 2014 at 20:56
  • Test your operand stack. Your second expression is found to be invalid because of the bad ). Your first expression appears valid but only because you get a result: "no more operators so the last value must be right". Commented Jan 3, 2014 at 21:05
  • you mean, (2(3+5) is valid input? but there are no operators between 2 and 3 Commented Jan 3, 2014 at 21:10
  • 3
    I hope you take this as an example of how not to write an expression parser. It's wrong on so many levels... Commented Jan 3, 2014 at 21:16
  • hmm.. could u mention the other wrong test case? mmm... Commented Jan 3, 2014 at 21:20

1 Answer 1

3

This calculator does not work with implicit multiplication. you can use:

2((2+2)+1)

And see that it gives the wrong answer as opposed to:

2*((2+2)+1)

The false-positive expression you've used does not pass with explicit multiplication.

A quick for-the-lazy fix to add implicit multiplication would be something of that sort:

public static void doCalculate(String equation) {
            // make it explicit:
            System.out.println("Got:" + equation);
            Pattern pattern = Pattern.compile("([0-9]+|[a-z\\)])(?=[0-9]+|[a-z\\(])");
            Matcher m = pattern.matcher(equation);
            System.out.println("Made it: "+ (equation = m.replaceAll("$1*")));
            //our stacks for storage/temp variables
            Stack<Operator> operatorStack;
            Stack<Double> operandStack;
            double valOne, valTwo, newVal;
            Operator temp;

This is an attempt to capture implicit multiplication using regex and make it explicit.

It fixes all cases we've come up with.

Sign up to request clarification or add additional context in comments.

8 Comments

aha, but how to fix the implicit multiplication? is it wrong input or ?
Fix the implicit multiplication? It probably wasn't supposed to work to begin with I suppose. Perhaps you can add it.
Added quick fix. This is not tested and should be avoided at all costs :) If you ever fix it better, please answer your own question with the fix.
hmm, i found the other string that must be a problem.. for instance : ((1+3)5 they're valid.. :/ hmmh.. can i used ur pattern again to solve this one?
owh, ok.. yesterday i found the tutorial of using pattern in Java. And the cases is closed :D , thanks
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.