Hello Internet. 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?

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

Edited 4 Years Ago by binaryjc

The first problem I see here is that you use split() method from String class to obtain tokens. This is causing the bug you are having right now. If you look at your regex, you will see that the split() will consume the leading negative sign.

I would suggest you to parse the input string by yourself (using a grammar as your base knowledge). Implement a static method inside your class, take in a string, and return tokens as its result. The tokens should be defined by your grammar. Once you can get all your tokens properly, you then could move on to parse an expression.

This article has been dead for over six months. Start a new discussion instead.