fork(91) download
copy 
  1. /* A Java program to evaluate a given expression where tokens are separated 
  2.    by space.
  3.    Test Cases:
  4.      "10 + 2 * 6"            ---> 22
  5.      "100 * 2 + 12"          ---> 212
  6.      "100 * ( 2 + 12 )"      ---> 1400
  7.      "100 * ( 2 + 12 ) / 14" ---> 100    
  8. */
  9. import java.util.Stack;
  10.  
  11. class EvaluateString
  12. {
  13.     public static int evaluate(String expression)
  14.     {
  15.         char[] tokens = expression.toCharArray();
  16.  
  17.          // Stack for numbers: 'values'
  18.         Stack<Integer> values = new Stack<Integer>();
  19.  
  20.         // Stack for Operators: 'ops'
  21.         Stack<Character> ops = new Stack<Character>();
  22.  
  23.         for (int i = 0; i < tokens.length; i++)
  24.         {
  25.              // Current token is a whitespace, skip it
  26.             if (tokens[i] == ' ')
  27.                 continue;
  28.  
  29.             // Current token is a number, push it to stack for numbers
  30.             if (tokens[i] >= '0' && tokens[i] <= '9')
  31.             {
  32.                 StringBuffer sbuf = new StringBuffer();
  33.                 // There may be more than one digits in number
  34.                 while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
  35.                     sbuf.append(tokens[i++]);
  36.                 values.push(Integer.parseInt(sbuf.toString()));
  37.             }
  38.  
  39.             // Current token is an opening brace, push it to 'ops'
  40.             else if (tokens[i] == '(')
  41.                 ops.push(tokens[i]);
  42.  
  43.             // Closing brace encountered, solve entire brace
  44.             else if (tokens[i] == ')')
  45.             {
  46.                 while (ops.peek() != '(')
  47.                   values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  48.                 ops.pop();
  49.             }
  50.  
  51.             // Current token is an operator.
  52.             else if (tokens[i] == '+' || tokens[i] == '-' ||
  53.                      tokens[i] == '*' || tokens[i] == '/')
  54.             {
  55.                 // While top of 'ops' has same or greater precedence to current
  56.                 // token, which is an operator. Apply operator on top of 'ops'
  57.                 // to top two elements in values stack
  58.                 while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
  59.                   values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  60.  
  61.                 // Push current token to 'ops'.
  62.                 ops.push(tokens[i]);
  63.             }
  64.         }
  65.  
  66.         // Entire expression has been parsed at this point, apply remaining
  67.         // ops to remaining values
  68.         while (!ops.empty())
  69.             values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  70.  
  71.         // Top of 'values' contains result, return it
  72.         return values.pop();
  73.     }
  74.  
  75.     // Returns true if 'op2' has higher or same precedence as 'op1',
  76.     // otherwise returns false.
  77.     public static boolean hasPrecedence(char op1, char op2)
  78.     {
  79.         if (op2 == '(' || op2 == ')')
  80.             return false;
  81.         if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-'))
  82.             return false;
  83.         else
  84.             return true;
  85.     }
  86.  
  87.     // A utility method to apply an operator 'op' on operands 'a' 
  88.     // and 'b'. Return the result.
  89.     public static int applyOp(char op, int b, int a)
  90.     {
  91.         switch (op)
  92.         {
  93.         case '+':
  94.             return a + b;
  95.         case '-':
  96.             return a - b;
  97.         case '*':
  98.             return a * b;
  99.         case '/':
  100.             if (b == 0)
  101.                 throw new
  102.                 UnsupportedOperationException("Cannot divide by zero");
  103.             return a / b;
  104.         }
  105.         return 0;
  106.     }    
  107.  
  108.     // Driver method to test above methods
  109.     public static void main(String[] args)
  110.     {
  111.         System.out.println(EvaluateString.evaluate("10 + 2 * 6"));
  112.         System.out.println(EvaluateString.evaluate("100 * 2 + 12"));
  113.         System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 )"));
  114.         System.out.println(EvaluateString.evaluate("100 * ( 2 + 12 ) / 14"));
  115.         System.out.println(EvaluateString.evaluate(" ( ( 20 - 10 ) * ( 30 - 20 ) + 10 ) * 2"));
  116.         System.out.println(EvaluateString.evaluate(" ( ( 20 - 10 ) * ( 30 - 20 ) / 10 + 10 ) * 2"));
  117.     }
  118. }
Success #stdin #stdout 0.06s 381248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
22
212
1400
100
220
40
https://ideone.com/NEYfnD
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!