Java Expression Parser & Calculator Shunting Yard Algorithm

binaryjc picture binaryjc · Dec 10, 2012 · Viewed 10k times · Source

So the task is to create our own parser for a expression calculator. For Example:

Input: 3+2*1-6/3 Output: 3

Input: 3++2 Output: Invalid Expression

Input: -5+2 Output: -3

Input: 5--2 Output: 7

The code here solves a part of the problem except that it has a fixed input and negative values cannot be solved, And I'm not quite sure yet if it really does solve the expression with operator precedence. but I already modified it to get an input expression from the user. and I've been wondering for hours how to implement the solving for negative values. help anyone?

NO JAVASCRIPT ENGINE PLEASE.

here's the current code

    import java.util.*; 

public class ExpressionParser   
{  
    // Associativity constants for operators  
    private static final int LEFT_ASSOC  = 0;  
    private static final int RIGHT_ASSOC = 1;  

    // Operators  
    private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();  
    static   
    {  
        // Map<"token", []{precendence, associativity}>  
        OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });  
        OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });  
        OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });  
        OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });          
    }  

    // Test if token is an operator  
    private static boolean isOperator(String token)   
    {  
        return OPERATORS.containsKey(token);  
    }  

    // Test associativity of operator token  
    private static boolean isAssociative(String token, int type)   
    {  
        if (!isOperator(token))   
        {  
            throw new IllegalArgumentException("Invalid token: " + token);  
        }  

        if (OPERATORS.get(token)[1] == type) {  
            return true;  
        }  
        return false;  
    }  

    // Compare precedence of operators.      
    private static final int cmpPrecedence(String token1, String token2)   
    {  
        if (!isOperator(token1) || !isOperator(token2))   
        {  
            throw new IllegalArgumentException("Invalid tokens: " + token1  
                    + " " + token2);  
        }  
        return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];  
    }  

    // Convert infix expression format into reverse Polish notation  
    public static String[] expToRPN(String[] inputTokens)   
    {  
        ArrayList<String> out = new ArrayList<String>();  
        Stack<String> stack = new Stack<String>();  

        // For each token  
        for (String token : inputTokens)   
        {  
            // If token is an operator  
            if (isOperator(token))   
            {    
                // While stack not empty AND stack top element   
                // is an operator  
                while (!stack.empty() && isOperator(stack.peek()))   
                {                      
                    if ((isAssociative(token, LEFT_ASSOC)         && 
                         cmpPrecedence(token, stack.peek()) <= 0) ||   
                        (isAssociative(token, RIGHT_ASSOC)        &&   
                         cmpPrecedence(token, stack.peek()) < 0))   
                    {  
                        out.add(stack.pop());     
                        continue;  
                    }  
                    break;  
                }
                // Push the new operator on the stack  
                stack.push(token);  
            }   
            // If token is a left bracket '('  
            else if (token.equals("("))   
            {  
                stack.push(token);  //   
            }   
            // If token is a right bracket ')'  
            else if (token.equals(")"))   
            {                  
                while (!stack.empty() && !stack.peek().equals("("))   
                {  
                    out.add(stack.pop());   
                }  
                stack.pop();   
            }   
            // If token is a number  
            else   
            {  
            //  if(!isOperator(stack.peek())){
            //      out.add(String.valueOf(token*10));
            //      }
                out.add(token);   
            }  
        }  
        while (!stack.empty())  
        {  
            out.add(stack.pop());   
        }  
        String[] output = new String[out.size()];  
        return out.toArray(output);  
    }  

    public static double RPNtoDouble(String[] tokens)  
    {          
        Stack<String> stack = new Stack<String>();  

        // For each token   
        for (String token : tokens) //for each   
        {  
            // If the token is a value push it onto the stack  
            if (!isOperator(token))   
            {  
                stack.push(token);                  
            }  
            else  
            {          
                // Token is an operator: pop top two entries  
                Double d2 = Double.valueOf( stack.pop() );  
                Double d1 = Double.valueOf( stack.pop() );  

                //Get the result  
                Double result = token.compareTo("*") == 0 ? d1 * d2 :   
                                token.compareTo("/") == 0 ? d1 / d2 :  
                                token.compareTo("+") == 0 ? d1 + d2 :  
                                                            d1 - d2;                 
              // Push result onto stack  
                stack.push( String.valueOf( result ));                                                  
            }                          
        }          

        return Double.valueOf(stack.pop());  
    }  

    public static void main(String[] args) throws Exception{  
        Scanner in = new Scanner(System.in);
        String reg = "((?<=[<=|>=|==|\\+|\\*|\\-|<|>|/|=])|(?=[<=|>=|==|\\+|\\*|\\-|<|>|/|=]))";
    while(true){
        try{
        System.out.println("Enter Your Expression");  
        //String[] input = "( 1 + 2 ) * ( 3 / 4 ) - ( 5 + 6 )".split(" ");
        String[] input =  in.nextLine() .split(reg);  
        String[] output = expToRPN(input);  

        // Build output RPN string minus the commas  
         System.out.print("Stack: ");
         for (String token : output) {  
                System.out.print("[ ");System.out.print(token + " "); System.out.print("]");
        }  
         System.out.println(" ");   
        // Feed the RPN string to RPNtoDouble to give result  
        Double result = RPNtoDouble( output );
        System.out.println("Answer= " + result);                
        }catch (NumberFormatException | EmptyStackException nfe){ 
            System.out.println("INVALID EXPRESSION"); }         
        }
    }
}  

UPDATED CODE: Added: unaryToexp() function. what I wanted to do was that everytime a " - " occurs, the code treats it as a binary by changing it to " _ " as another operator and this operator solves multiplies thing by -1 (what I wanted first was to add [-1] and [*] to the rpn stack). still got problems here.

compiler says:

Enter Your Expression
-5+3
Stack: [  ][ 5 ][ - ][ 3 ][ + ]
Exception in thread "main" java.lang.NumberFormatException: empty String
        at sun.misc.FloatingDecimal.readJavaFormatString(FloatingDecimal.java:10 11)
        at java.lang.Double.valueOf(Double.java:504)
        at ExpressionParser.RPNtoDouble(ExpressionParser.java:160)
        at ExpressionParser.main(ExpressionParser.java:194)* 

I think it has something to do with the Double d1 = Double.valueOf( stack.pop() ); cause it still pops another two values, where I only need one for a solving a unary operator. any help?

public class ExpressionParser   
{  
    // Associativity constants for operators  
    private static final int LEFT_ASSOC  = 0;  
    private static final int RIGHT_ASSOC = 1;  

    // Operators  
    private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();  
    static   
    {  
       // Map<"token", []{precendence, associativity}>      
        OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });  
        OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });  
        OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });  
        OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
        OPERATORS.put("_", new int[] { 5, RIGHT_ASSOC }); 
    }  

    // Test if token is an operator  
    private static boolean isOperator(String token)   
    {
        return OPERATORS.containsKey(token);  
    }  

    // Test associativity of operator token  
    private static boolean isAssociative(String token, int type)   
    {  
        if (!isOperator(token))   
        {  
            throw new IllegalArgumentException("Invalid token: " + token);  
        }  

        if (OPERATORS.get(token)[1] == type) {  
            return true;  
        }

        return false;  
    }  

    // Compare precedence of operators.      
    private static final int cmpPrecedence(String token1, String token2)   
    {  
        if (!isOperator(token1) || !isOperator(token2))   
        {  
            throw new IllegalArgumentException("Invalid tokens: " + token1  
                    + " " + token2);  
        }  
        return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];  
    }  


    // CONVERT UNARY OPERATORS
    public static String[] unaryToexp(String[] inputTokens)
    {
        ArrayList<String> out = new ArrayList<String>();  
        Stack<String> stack = new Stack<String>(); 
                //if token is an unary minus
        for (String token : inputTokens)   
        {
                    if( ((token == "-") && (isOperator(stack.peek()) || stack.empty()  ))){  // 
                        token = "_";
                    }
                    else if (token == "-"){
                        token = "-";
                    }
            out.add(token);
             while (!stack.empty())  
                {  
                    out.add(stack.pop());
                }       
        }

        String[] output = new String[out.size()];  
        return out.toArray(output);  
    }

    // Convert infix expression format into reverse Polish notation  
    public static String[] expToRPN(String[] inputTokens)   
    {  
        ArrayList<String> out = new ArrayList<String>();  
        Stack<String> stack = new Stack<String>();  

        // For each token  
        for (String token : inputTokens)   
        { 
            // If token is an operator  
            if (isOperator(token))   
            {  
                // While stack not empty AND stack top element   
                // is an operator 

                while (!stack.empty() && isOperator(stack.peek()))
                {                      
                    if ((isAssociative(token, LEFT_ASSOC)         && 
                         cmpPrecedence(token, stack.peek()) <= 0) ||   
                        (isAssociative(token, RIGHT_ASSOC)        &&   
                         cmpPrecedence(token, stack.peek()) < 0))       

                    {  
                        out.add(stack.pop());     
                        continue; 
                    }
                    break;  
                }

                // Push the new operator on the stack 
                stack.push(token);  
            }
            // If token is a left bracket '('  
            else if (token.equals("("))   
            {  
                stack.push(token);  //   
            }   
            // If token is a right bracket ')'  
            else if (token.equals(")"))   
            {                  
                while (!stack.empty() && !stack.peek().equals("("))   
                {  
                    out.add(stack.pop());   
                }  
                stack.pop();   
            }   
            // If token is a number  
            else   
            {  
                out.add(token);   
            }  
        }  
        while (!stack.empty())  
        {  
            out.add(stack.pop());   
        }  
        String[] output = new String[out.size()];  
        return out.toArray(output);  
    }  

   public static double RPNtoDouble(String[] tokens)  
{          
    Stack<String> stack = new Stack<String>();  

    // For each token   
    for (String token : tokens)   
    {  
        // If the token is a value push it onto the stack  
        if (!isOperator(token))   
        {  
            stack.push(token);                  
        }  
        else  
        {  
            // Token is an operator: pop top two entries  
            Double d2 = Double.valueOf( stack.pop() );  
            Double d1 = Double.valueOf( stack.pop() );  

            //Get the result  
            Double result = token.compareTo("_") == 0 ? d2 * -1 :   
                            token.compareTo("*") == 0 ? d1 * d2 :   
                            token.compareTo("/") == 0 ? d1 / d2 :  
                            token.compareTo("+") == 0 ? d1 + d2 :  
                                                        d1 - d2;    

            // Push result onto stack  
            stack.push( String.valueOf( result ));                                                  
        }                          
    }          
    return Double.valueOf(stack.pop());  
}  

    public static void main(String[] args) throws Exception{  
        Scanner in = new Scanner(System.in);
        String reg = "((?<=[<=|>=|==|\\+|\\*|\\-|\\_|<|>|/|=])|(?=[<=|>=|==|\\+|\\*|\\-|<|>|/|=]))";
    while(true){
        //try{
        System.out.println("Enter Your Expression");  
        //String[] input = "( 1 + 2 ) * ( 3 / 4 ) - ( 5 + 6 )".split(" ");
        String[] input =  in.nextLine() .split(reg); 
        String[] unary = unaryToexp(input); //.split(reg);
        String[] output = expToRPN(unary);  

        // Build output RPN string minus the commas  
         System.out.print("Stack: ");
         for (String token : output) {  
                System.out.print("[ ");System.out.print(token); System.out.print(" ]");
        }  
         System.out.println(" ");   
        // Feed the RPN string to RPNtoDouble to give result  
        Double result = RPNtoDouble( output );
        System.out.println("Answer= " + result);                
        //}catch (){ 
            //System.out.println("INVALID EXPRESSION"); }           
        }
    }   
} 

Answer

Hazem Elraffiee picture Hazem Elraffiee · Dec 10, 2012

Here you are:

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

public static String eval(String matlab_expression){
    if(matlab_expression == null){
        return "NULL";
    }
    String js_parsable_expression = matlab_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 e1){
        return null; // Invalid Expression
    }
}