title: Java Expression Parser & Calculator Shunting Yard Algorithm
body: <p>So the task is to create our own parser for a expression calculator. For Example:</p>
  
  <p>Input: 3+2*1-6/3
  Output: 3</p>
  
  <p>Input: 3++2
  Output: Invalid Expression</p>
  
  <p>Input: -5+2
  Output: -3</p>
  
  <p>Input: 5--2
  Output: 7</p>
  
  <p>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?</p>
  
  <p>NO JAVASCRIPT ENGINE PLEASE.</p>
  
  <p>here's the current code</p>
  
  <pre><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&lt;String, int[]&gt; OPERATORS = new HashMap&lt;String, int[]&gt;();  
      static   
      {  
          // Map&lt;"token", []{precendence, associativity}&gt;  
          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&lt;String&gt; out = new ArrayList&lt;String&gt;();  
          Stack&lt;String&gt; stack = new Stack&lt;String&gt;();  
  
          // 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() &amp;&amp; isOperator(stack.peek()))   
                  {                      
                      if ((isAssociative(token, LEFT_ASSOC)         &amp;&amp; 
                           cmpPrecedence(token, stack.peek()) &lt;= 0) ||   
                          (isAssociative(token, RIGHT_ASSOC)        &amp;&amp;   
                           cmpPrecedence(token, stack.peek()) &lt; 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() &amp;&amp; !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&lt;String&gt; stack = new Stack&lt;String&gt;();  
  
          // 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 = "((?&lt;=[&lt;=|&gt;=|==|\\+|\\*|\\-|&lt;|&gt;|/|=])|(?=[&lt;=|&gt;=|==|\\+|\\*|\\-|&lt;|&gt;|/|=]))";
      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"); }         
          }
      }
  }  
  </code></pre>
  
  <p>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.</p>
  
  <p>compiler says:</p>
  
  <pre><code>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)* 
  </code></pre>
  
  <p>I think it has something to do with the <code>Double d1 = Double.valueOf( stack.pop() );</code> cause it still pops another two values, where I only need one for a solving a unary operator. any help?</p>
  
  <pre><code>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&lt;String, int[]&gt; OPERATORS = new HashMap&lt;String, int[]&gt;();  
      static   
      {  
         // Map&lt;"token", []{precendence, associativity}&gt;      
          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&lt;String&gt; out = new ArrayList&lt;String&gt;();  
          Stack&lt;String&gt; stack = new Stack&lt;String&gt;(); 
                  //if token is an unary minus
          for (String token : inputTokens)   
          {
                      if( ((token == "-") &amp;&amp; (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&lt;String&gt; out = new ArrayList&lt;String&gt;();  
          Stack&lt;String&gt; stack = new Stack&lt;String&gt;();  
  
          // 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() &amp;&amp; isOperator(stack.peek()))
                  {                      
                      if ((isAssociative(token, LEFT_ASSOC)         &amp;&amp; 
                           cmpPrecedence(token, stack.peek()) &lt;= 0) ||   
                          (isAssociative(token, RIGHT_ASSOC)        &amp;&amp;   
                           cmpPrecedence(token, stack.peek()) &lt; 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() &amp;&amp; !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&lt;String&gt; stack = new Stack&lt;String&gt;();  
  
      // 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 = "((?&lt;=[&lt;=|&gt;=|==|\\+|\\*|\\-|\\_|&lt;|&gt;|/|=])|(?=[&lt;=|&gt;=|==|\\+|\\*|\\-|&lt;|&gt;|/|=]))";
      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"); }           
          }
      }   
  } 
  </code></pre>